[Powered by Google Translate] [Secțiunea 6: mai puțin confortabilă]
[Nate Hardison] [Universitatea Harvard]
[Acest lucru este CS50.] [CS50.TV]
Bine. Bine ați venit la secțiunea 6.
În această săptămână, vom vorbi despre structuri de date în secțiune,
primul rând pentru că problema aceasta saptamana setat pe spellr
face o grămadă de explorare diferite structuri de date.
Există o mulțime de moduri diferite pe care le puteți merge cu set de probleme,
și structurile de date pe care le cunoașteți mai multe despre, mai multe lucruri interesante pe care le puteți face.
>> Deci, să începem. În primul rând vom vorbi despre stive,
datele stack și coada de structuri care le vom discuta despre.
Stive și cozile sunt foarte utile atunci când vom începe să vorbim despre graficele,
care noi nu vom face atât de mult de acum.
Dar ei sunt foarte bine pentru a înțelege una dintre cele mai mari structuri de date fundamentale ale CS.
Descrierea din caietul de sarcini set de probleme,
dacă îl trage în sus, vorbește despre stive fi înrudit cu
gramada de tăvi de luat masa pe care le au în cantina la săli de mese
în cazul în care atunci când personalul de mese vine si pune tăvile de luat masa afară după ce le-am curățat,
ei stiva-le una peste alta.
Și apoi, când copiii vin în pentru a obține produse alimentare,
ei trageți tăvile de pe, în primul rând de sus o, apoi cea de sub ea, apoi cea de mai jos care.
Deci, într-adevăr, în primul rând că tava de personalul de mese pus jos este ultima care se decolat.
Ultima faptul că personalul pus pe mese este prima care se ia off pentru cină.
În spec. set de probleme, pe care le puteți descărca dacă nu ați făcut deja,
vorbim despre modelarea unei dumneavoastra Structura de date stivă folosirea acestui tip de struct.
>> Deci, ceea ce am ajuns aici, acest lucru este similar cu ceea ce a fost prezentat în curs,
cu excepția cazului în curs am prezentat acest lucru cu Ints ca spre deosebire de char * s.
Acest lucru se întâmplă să fie o stivă care stochează ce?
Daniel? Ce am stocarea în această stivă?
[Daniel] Coarde? Suntem >> stocarea șiruri în această stivă, exact.
Tot ce trebuie să aibă, în scopul de a crea o stivă este o matrice
cu o capacitate deosebită, care, în acest caz,
Capacitatea este de gând să fie în toate capacele, deoarece este o constantă.
Și apoi, în plus față de matrice, tot ce avem nevoie pentru a urmări este dimensiunea actuală a matrice.
Un lucru de remarcat aici că e un fel de cool
este că noi creăm structura de date stivuite pe partea de sus a unui alt structurii de date, matrice.
Există mai multe moduri diferite de a pune în aplicare stive.
Noi nu-l va face destul de încă, dar sperăm că după ce face problemele legate de-listă,
veți vedea cum puteți implementa cu ușurință o stivă pe partea de sus a unei liste legate, de asemenea.
Dar pentru moment, vom lipi de tablouri.
Deci, din nou, tot ce avem nevoie este o matrice, iar noi trebuie doar să urmăriți dimensiunea matrice.
[Sam] Ne pare rău, de ce ai spus stiva e pe partea de sus a siruri de caractere?
Pentru mine se pare ca siruri de caractere sunt în stivă.
[Hardison] Da. Suntem crearea, ne luând în structura noastră de date matrice -
E o întrebare foarte bună. Deci, întrebarea este de ce, pentru oamenii care se uită acest lucru online,
de ce ne spun că stiva este pe partea de sus a siruri de caractere,
deoarece aici se pare ca siruri de caractere sunt în interiorul stivei?
Care este total caz.
Ceea ce am fost referindu-se la faptul că a fost avem o structură de date matrice.
Avem o serie de char * s, această matrice de siruri de caractere,
și vom adăuga la faptul că, în scopul de a crea structura de date stivuite.
>> Deci, o stivă este puțin mai complexă decât o matrice.
Putem folosi o matrice pentru a construi un stack.
Deci, asta e în cazul în care spunem că stiva este construit pe partea de sus a unei matrice.
De asemenea, așa cum am spus mai devreme, putem construi o stivă pe partea de sus a unei liste legate.
În loc de a folosi un tablou de a deține elemente noastre,
am putea folosi o listă legat de a deține elemente noastre și de a construi în jurul valorii de stiva asta.
Să mergem printr-o serie de exemple, se uită la un cod,
pentru a vedea ce se intampla de fapt aici.
Pe stânga, am aruncat ce struct stiva va arăta în memorie
în cazul în care capacitatea au fost definite pentru a fi # patru.
Avem nostru de patru-element de matrice char *.
Avem strings [0], siruri de caractere [1], siruri de caractere [2], siruri de caractere [3],
și apoi că spațiul ultima pentru întreg dimensiunea noastră.
Are acest sens? Bine.
Aceasta este ceea ce se întâmplă dacă ceea ce fac eu pe dreapta,
care va fi codul meu, este să declare doar un struct, o struct stivuite numit uri.
Aceasta este ceea ce primim. Acesta stabilește această amprentă în memorie.
Prima întrebare aici este ceea ce sunt conținutul acestui struct stiva?
Chiar acum sunt nimic, dar nu sunt în totalitate nimic.
Sunt acest tip de gunoi. Nu avem nici o idee ce e în ele.
Când ne-am declara e coșul de fum, suntem aruncat doar ca pe partea de sus în jos de memorie.
E un fel de declarare int i, și nu-l inițializarea.
Tu nu știi ce e acolo. Puteți citi ce e acolo,
dar nu ar putea fi super util.
Un lucru pe care doriți să vă amintiți întotdeauna să faceți este să inițializeze tot ce trebuie să fie inițializat.
În acest caz, vom inițializa dimensiunea sa fie zero,
pentru că o să se dovedesc a fi foarte important pentru noi.
Am putea merge mai departe și a inițializa toate indicatoarele, toate s char *,
să fie o valoare ușor de înțeles, probabil nul.
Dar nu e totul necesar ca facem asta.
>> Acum, cele două operațiuni principale de pe stivele sunt?
Amintește cineva de la prelegere ce faci cu stive? Da?
[Stella] Împingerea și popping? Exact >>.
Împingerea și popping sunt cele două operațiuni principale de pe stive.
Și ce împinge face? Se pune ceva >> pe partea de sus
de stiva, apoi popping-l ia de pe.
[Hardison] Exact. Deci, împingând împinge ceva pe partea de sus a stivei.
E ca și cum personalul de mese a pune o tava de servit masa în jos pe tejghea.
Și popping este de a lua o tavă de mese de pe stivă.
Să se plimbe prin câteva exemple de ceea ce se întâmplă
când ne împinge lucrurile în stivă.
Dacă ar fi să împingă șirul "Hello" pe stivă nostru,
aceasta este ceea ce diagrama noastră ar arăta ca acum.
Vezi ce se întâmplă?
Am împins în primul element al array noastre siruri de caractere
si am marit numarul nostru de a fi dimensiunea 1.
Deci, dacă ne uităm la diferența dintre cele două diapozitive, aici a fost de 0, aici e înainte de împingere.
Aici este după împingere.
Înainte de a împinge, după împingere.
Și acum avem un element din stivă nostru.
E șirul "Bună ziua", și asta e tot.
Orice altceva în matrice, în gama noastră siruri de caractere, este încă gunoi.
Noi nu l-am inițializat.
Să spunem că împinge un alt șir pe stivă nostru.
Mergem să împingă "lumea" de pe acest timp.
Deci, puteți vedea "lumea" aici merge pe partea de sus a "hello",
și numărul de dimensiunea merge pana la 2.
Acum putem împinge "CS50", și că voi merge pe partea de sus din nou.
Dacă ne întoarcem, puteți vedea cum ne împinge lucrurile pe partea de sus a stivei.
Și acum ajungem la pop.
Când ne-am mi-a venit ceva de pe stivă, ce sa întâmplat?
Oricine vezi diferența? E destul de subtil.
[Student] dimensiune. Da >>, dimensiunea sa schimbat.
>> Ce altceva ți-ar fi așteptat să se schimbe?
[Student] siruri de caractere, prea. Corect >>. Siruri de caractere prea.
Se pare că, atunci când faci în acest fel,
pentru ca nu suntem copierea elementelor în stivă nostru,
noi de fapt, nu trebuie să faci nimic, putem folosi doar dimensiunea
pentru a ține evidența numărului de lucruri în gama noastră
astfel încât atunci când ne pop din nou, din nou, am decrement doar dimensiunea noastră de până la 1.
Nu e nevoie de a merge de fapt și să suprascrie nimic.
Un fel de funky.
Se pare că am de obicei, lasa doar lucrurile în pace, pentru că e mai puțin de lucru pentru noi să facem.
Dacă noi nu trebuie să ne întoarcem și să suprascrieți ceva, atunci de ce o faci?
Așa că atunci când am pop de două ori de pe stivă, tot ceea ce face este descreste marimea de cateva ori.
Și din nou, aceasta este doar pentru că nu suntem copierea lucruri în stivă nostru.
Da? Dă-i drumul.
[Student, neinteligibil] >> Și apoi ce se întâmplă atunci când vă împinge ceva nou?
Când vă împinge ceva nou, unde se duce?
În cazul în care se duce, Vasile? Într-siruri de caractere >> [1]? Corect >>.
De ce nu a mers in siruri [3]?
[Vasile] Pentru că ați uitat că există ceva în șiruri [1] și [2]?
[Hardison] Exact. Stivă noastră, în esență, "a uitat" că a fost exploatație pe nimic
în șiruri [1] sau siruri de caractere [2], asa ca atunci cand apasam "woot",
se pune doar că în element la siruri de caractere [1].
Sunt acolo orice întrebări referitoare la modul de executare a lucrărilor, la un nivel de bază?
[Sam] Deci, acest lucru nu este dinamică în nici un fel, în ceea ce privește cantitatea
sau în ceea ce privește mărimea stivei?
[Hardison] Exact. Aceasta este - punctul a fost că acest lucru nu a fost un stack dinamic growning.
Aceasta este o stivă care pot organiza, la cele mai multe, patru * e char, la cele mai multe patru lucruri.
Dacă ar fi să încercăm și împinge un lucru cincea, ce crezi că ar trebui să se întâmple?
[Elevii, neinteligibile]
[Hardison] Exact. Există o serie de lucruri care ar putea întâmpla.
S-ar putea, eventual, SEG vina, in functie de ceea ce am fost -
exact cum am fost de punere în aplicare back-end.
S-ar putea suprascrie. Aceasta ar putea avea ca buffer overflow care am vorbit despre în clasa.
Care ar fi cel mai evident care ar putea fi suprascrise
în cazul în care am încercat să împingă un lucru in plus pe stivă nostru?
Deci, te-a menționat un buffer overflow.
Care ar putea fi lucrul care ar fi scris peste sau călcat pe
dacă am revărsat accidental prin încercarea de a împinge un lucru suplimentar?
[Daniel, neinteligibil] Posibil >>.
Dar inițial, ceea ce s-ar putea întâmpla? Ce se întâmplă dacă am încercat să împingă o patrulea lucru?
S-ar putea suprascrie dimensiunea, cel puțin cu această schemă de memorie pe care le-am luat.
>> În caietul de sarcini set de probleme, care este ceea ce am de gând să fie de punere în aplicare astăzi,
ceea ce vreau să fac este doar întoarcă fals.
Metoda noastră push este de gând să returneze o valoare boolean,
și că valoarea Boolean va fi adevărată dacă reușește împingere
și fals dacă nu putem împinge nimic mai mult, deoarece stiva este plin.
Să plimbi printr-un pic de cod, care chiar acum.
Iată funcția noastră împingere.
Funcția noastră Apasă pentru un teanc este de gând să ia în șir pentru a pune pe stiva.
Se va întoarce true dacă șirul a fost împins cu succes
pe stivă și fals în caz contrar.
Orice sugestii cu privire la ceea ce ar putea fi un lucru bun primul de a face aici?
[Sam] Dacă dimensiunea este egal cu capacitatea de a reveni apoi fals?
[Hardison] Bingo. Frumos de locuri de muncă.
În cazul în care dimensiunea este capacitatea, vom reveni fals.
Noi nu putem pune nimic mai mult în stivă nostru.
În caz contrar, dorim să punem ceva pe partea de sus a stivei.
Care este "partea de sus a stivei," initial?
[Daniel] Marimea 0? Marimea 0 >>.
Care este partea de sus a stivei după e un singur lucru în stivă? Missy, știi?
[Missy] One. Dimensiune >> este una, exact. Vă păstrați adăugarea la dimensiunea,
și de fiecare dată când pui în element nou la dimensiunea indicelui în matrice.
O putem face cu acest tip de o linie, în cazul în care are sens.
Deci, ne-am luat gama noastră siruri de caractere, vom accesa la pagina de index dimensiunea,
și suntem doar de gând pentru a stoca * nostru char acolo.
Observați cum nu exista nici copierea șir întâmplă pe aici,
nici alocarea dinamica a memoriei?
Și apoi Missy adus ceea ce avem acum de făcut,
pentru că ne-ați stocat în șir locul adecvat în matrice,
și ea a spus că a trebuit să incrementa dimensiunea de una, astfel încât suntem gata pentru următoarea împingere.
Astfel încât să putem face asta cu s.size + +.
În acest moment, ne-am împins în gama noastră. Care e ultimul lucru pe care trebuie să facem?
[Student] Înapoi adevărat. Înapoi >> adevărat.
Deci e destul de simplu, un cod destul de simplu. Nu prea mult.
Odată ce v-ați înfășurat capul în jurul valorii de modul în care funcționează stivă,
acest lucru este destul de simplu pentru a pune în aplicare.
>> Acum, următoarea parte din aceasta este popping un șir de pe stivă.
Am de gând să dea voi ceva timp pentru a lucra la acest bit un pic.
E aproape, în esență opusul a ceea ce am făcut aici, în împingere.
Ceea ce am făcut este de fapt - Hopa.
Am pornit un aparat aici, iar în aparat,
Am tras în sus problema set 5 caietul de sarcini.
Dacă vom mări aici, putem vedea eu sunt la cdn.cs50.net/2012/fall/psets/pset5.pdf.
Ați baieti descărcat acest cod care este situat aici, section6.zip?
Bine. Dacă nu ați făcut acest lucru, asta chiar acum, foarte repede.
O voi face în fereastra terminalul meu.
De fapt am făcut-o aici. Da.
Da, Sam? >> Am o întrebare despre ce ai spus paranteze s.string 's dimensiune a = str?
Ce este str? Este definit ca undeva înainte, sau - oh, în str. char *?
[Hardison] Da, exact. Asta a fost argumentul. >> Oh, bine. Scuze.
[Hardison] Suntem specificând șirul de a împinge inch
Altă întrebare care ar putea veni ca nu am vorbi despre aici a fost
am luat de la sine că am avut această variabilă numită s
care a fost în domeniul de aplicare și accesibile pentru noi.
Am luat de la sine că e fost acest struct stiva.
Deci, uită înapoi la acest cod împinge,
puteți vedea că facem lucruri cu acest șir care s-au trecut în
dar apoi dintr-o dată, suntem accesarea s.size, cum ar fi, în cazul în care au venit de la e?
În codul care ne vom uita puțin în secțiunea arhiva
și apoi lucrurile pe care le veți face în problema ta seturi,
ne-am facut topul nostru struct o variabilă globală
astfel încât să putem avea acces la aceasta în toate funcțiile noastre diferite
fără a fi nevoie să treacă în jurul valorii de manual și se trece prin referire,
face tot ceea ce fel de lucruri să-l.
Ne inseala doar un pic, dacă vreți, pentru a face lucrurile mai frumos.
Și asta e ceva ce facem noi aici, pentru că e pentru distractie, e mai ușor.
De multe ori, veți vedea oameni fac acest lucru în cazul în care acestea au o mare structură de date
care este operat pe cadrul programului lor.
>> Să ne întoarcem pe la aparatul.
Credeți toată lumea obține succes section6.zip?
Toată lumea se dezarhivati ​​folosind section6.zip UnZip?
Dacă te duci în secțiunea 6 director -
Aah, peste tot -
si tu lista ce e aici, vezi că ai trei variante diferite de fișiere. c..
Ai o coadă, un SLL, care este individual-linked listă, precum și un stack.
Dacă vă deschideți stack.c,
puteți vedea că am luat acest struct definite pentru noi,
struct exacta pe care tocmai am vorbit despre în diapozitive.
Avem variabila noastră globală pentru stivă,
avem funcția noastră împingere,
și apoi ne-am luat funcția noastră pop.
Voi pune codul pentru împinge înapoi pe diapozitiv aici,
dar ceea ce mi-ar place ca voi să faceți este, la cele mai bune de capacitatea dumneavoastră,
du-te și pune în aplicare funcția pop.
După ce l-am implementat, puteți compila acest lucru cu a face stivă,
și apoi executați executabil stivă rezultantă,
și care se va desfășura în întregime acest cod de test aici care este în principal.
Și principal are grija de a face, de fapt PUSH și POP apeluri
și asigurându-vă că totul merge prin toate dreapta.
De asemenea, acesta inițializează mărimea stack-ului chiar aici
astfel încât să nu trebuie să vă faceți griji cu privire la inițializarea asta.
Puteți presupune că acesta a fost corect inițializat
de momentul în care accesați-l în funcția de pop.
Are vreun sens?
Deci, aici vom merge. Nu e codul de împingere.
Eu voi da băieți 5 sau 10 minute.
Și, dacă aveți orice întrebări în timp ce sunteți interimar de codificare,
vă rugăm să cereți-le cu voce tare.
Deci, dacă ajungi la un punct sensibil, doar cere.
Lasă-mă să știu, să toată lumea știe.
Lucrați cu vecinul tău.
[Daniel] Noi doar punerea în aplicare a pop acum? Doar >> pop.
Deși aveți posibilitatea să copiați punerea în aplicare a împinge, dacă doriți
astfel ca testarea va funcționa.
Pentru că e greu pentru a testa lucruri intra in -
sau, e greu pentru a testa lucruri popping dintr-o stivă în cazul în care nu există nimic în stivă pentru a începe cu.
>> Ceea ce este pop ar trebui să fie revenirea? Elementul din partea de sus a stivei.
Ar trebui să obțineți elementul de pe partea de sus a stivei
și decrement apoi dimensiunea stivei,
și acum ți-ai pierdut elementul pe partea de sus.
Și apoi te vei întoarce elementul pe partea de sus.
[Student, neinteligibil]
[Hardison] Deci, ce se întâmplă dacă faci asta? [Student, neinteligibil]
Ce se întâmplă este termină accesați probabil, fie
un element care nu a fost inițializat încă, astfel încât dumneavoastră de calcul
a în cazul în care este ultimul element este oprit.
Deci, aici, dacă observați, în apăsare, suntem accesarea siruri de caractere de la elementul s.size
pentru că este un index nou.
E partea de sus a noua stivă.
Întrucât, în pop, s.size va fi spațiul următor,
spațiu care este pe partea de sus a tuturor elementelor din stack-ul tău.
Deci, elementul cel mai de sus, nu este la s.size,
ci, mai degrabă, e sub ea.
>> Un alt lucru de făcut atunci când - în pop,
te trebuie să descrește dimensiunea.
Dacă vă amintiți înapoi la diagrama micul nostru chiar aici,
într-adevăr, singurul lucru pe care am văzut intampla atunci cand am sunat pop
a fost faptul că această dimensiune a scăzut, în primul rând la 2, apoi la 1.
Apoi, când am împins un element nou pe, el ar merge pe la fața locului propriu-zis.
[Vasile] Dacă s.size este 2, atunci nu ar merge la elementul 2,
si apoi ai vrea să pop ca element de off?
Deci, dacă ne-am dus sa - >> Deci să ne uităm la acest lucru din nou.
Dacă aceasta este stiva noastră în acest moment
și numim pop,
la care indicele este elementul cel mai de sus?
[Vasile] La 2, dar o să pop 3. Corect >>.
Deci, asta e în cazul în care dimensiunea noastră este 3, dar vrem să pop element la index 2.
E ca un fel tipic de afara de cel pe care le au cu zero indexarea matrice.
Deci, tu vrei să pop al treilea element, dar al treilea element nu este la indexul 3.
Și motivul pentru care nu trebuie să faci asta minus 1 atunci când suntem împingându
este că acum, observați că elementul cel mai de sus,
dacă ar fi să împingă altceva pe stivă în acest moment,
ne-am dori să-l împingă la indexul 3.
Și doar așa se întâmplă că dimensiunea și indicii linia de sus atunci când sunteți împingându.
>> Cine are un teanc de lucru punere în aplicare?
Ai un stack de lucru unul. Nu v-ați pop lucru încă?
[Daniel] Da. Așa cred.
Programul >> funcționează și nu SEG faulting, este imprimarea?
Are imprima out "de succes" atunci când îl rulați?
Da. Asigurați-stack, executați-l, în cazul în care se imprimă "de succes" si nu merge braț,
atunci totul e bine.
Bine. Să mergem pe la aparatul foarte repede,
și vom merge prin asta.
Dacă ne uităm la ceea ce se întâmplă pe aici cu pop,
Daniel, care a fost primul lucru pe care ai făcut-o?
[Daniel] Dacă s.size este mai mare decât 0.
[Hardison] Ok. Și de ce ai făcut asta?
[Daniel] Pentru a vă asigura că a fost ceva în interiorul stivei.
[Hardison] Corect. Doriți să testați pentru a vă asigura că s.size este mai mare decât 0;
în caz contrar, ce vrei sa se intample?
[Daniel] nul de returnare? Rentabilitatea >> null, exact.
Deci, dacă s.size este mai mare decât 0. Atunci ce vom face?
Ce facem dacă stiva nu este gol?
[Stella] Tu descreste marimea? Tu >> descreste marimea, bine.
Deci, cum ai făcut asta? >> S.size--.
[Hardison] Mare. Și apoi ce-ai făcut?
[Stella] Și apoi i-am spus retur s.string [s.size].
[Hardison] Mare.
În caz contrar, te vei întoarce null. Da, Sam?
[Sam] De ce nu are nevoie de a fi s.size + 1?
[Hardison] Plus 1? Da >>. >> Am înțeles.
[Sam] M-am gândit că tu iei 1 din,
atunci ai de gând să fie returnarea nu una care au cerut.
[Hardison] Și asta a fost doar ceea ce am vorbit despre această problemă cu toată 0 indicilor.
Deci, dacă ne apropia din nou aici.
Dacă ne uităm la tipul ăsta de aici, puteți vedea că, atunci când ne pop,
suntem popping element la index 2.
>> Așa că am reduce dimensiunea noastră în primul rând, apoi dimensiunea noastră coincide indexul nostru.
Dacă noi nu descreste marimea prima, atunci avem de a face dimensiunea -1 și apoi decrementare.
Mare. Toate bune?
Orice întrebări cu privire la acest lucru?
Există un număr de moduri diferite de a scrie aceasta, de asemenea.
De fapt, putem face ceva, chiar - ce putem face cu o linie.
Putem face o întoarcere de o linie.
Deci, putem de fapt, înainte de a descreste ne întoarcem prin a face asta.
Deci, pune - înainte de a s.size.
Asta face linia cu adevarat dens.
În cazul în care diferența dintre - marimea si. S.size--
este faptul că această postfix - ei o numesc postfix, deoarece - vine dupa s.size--
înseamnă că s.size este evaluat în scopul de a găsi indicelui
așa cum este în prezent, atunci când această linie este executat,
și apoi acest lucru - se întâmplă după ce linia este executat.
Dupa element la s.size indicele este accesat.
Și asta nu e ceea ce ne dorim, pentru ca vrem sa se intample prima descreștere.
Othewise, vom fi accesarea matrice, în mod eficient, în afara limitelor.
Vom fi accesarea elementului de mai sus, de fapt cea pe care am dori să o accesați.
Da, Sam? Este mai rapid >> sau de a folosi memorie RAM mai puțin pentru a face într-o singură linie sau nu?
[Hardison] Sincer, într-adevăr depinde.
[Sam, neinteligibil] >> Da, depinde. Puteți face trucuri compilatorului
pentru a obține compilatorului să recunoască faptul că, de obicei, îmi imaginez.
>> Deci, am menționat un pic despre asta optimizare compilator
pe care le puteți face în compilarea,
si asta e genul de lucru pe care un compilator ar putea fi în măsură să dau seama,
ca oh, hei, poate că eu pot face acest lucru într-o singură operație,
spre deosebire de încărcare variabilă în mărime de la RAM,
decrementarea ea, stocarea-l înapoi, și apoi încărcarea înapoi din nou
pentru a procesa restul de această operațiune.
Dar de obicei, nu, acest lucru nu este genul de lucru
care va face programul mult mai rapid.
Orice întrebări mai multe stive?
>> Deci, împingându-și popping. Dacă vreți să încercați ediția hacker,
ceea ce am făcut în ediția hacker este, de fapt dispărut
și a făcut acest teanc să crească dinamic.
Provocarea nu este în primul rând aici, în funcție de împingere,
să dau seama cum de a face ca matrice să crească
cum vă păstrați apăsarea mai multe elemente și mai mult pe la stiva.
E de fapt, nu prea mult cod suplimentar.
Doar un apel la - va trebui să vă amintiți pentru a primi apeluri la malloc acolo în mod corespunzător,
și dau apoi cand ai de gând să sun realloc.
Asta e o provocare distractiv dacă ești interesat.
>> Dar, pentru moment, să trecem mai departe, și hai să vorbim despre cozile.
Derulați pe aici.
Coada este un frate apropiat al stivei.
Deci, în stivă, lucrurile care au fost puse în ultima
au fost primele lucruri care urmează să fie apoi preluate.
Am luat acest ultimul, primul ieșit, sau LIFO, prin care se dispune.
Întrucât, în coadă, cum te-ai astepta de la atunci când sunteți în picioare, în linie,
prima persoană pentru a obține în linie, primul lucru pentru a intra în coada de așteptare,
este primul lucru care devine preluate din coada.
Cozile sunt, de asemenea, adesea folosite atunci când avem de-a face cu grafice,
ca și cum am vorbit despre scurt cu stive,
și cozile sunt, de asemenea, la îndemână pentru o grămadă de alte lucruri.
Un lucru care vine de multe ori încearcă să mențină, de exemplu,
o listă de elemente de sortat.
Și tu poți face acest lucru cu o matrice. Puteți menține o listă sortată de lucruri într-o matrice,
dar în cazul în care devine complicat este atunci va trebui să găsească întotdeauna
locul potrivit pentru a insera următorul lucru.
Deci, dacă aveți o serie de numere, 1 la 10,
și apoi doriți să extindeți că la toate numerele de la 1 100,
și vei primi aceste numere în ordine aleatorie și încearcă să mențină totul
sortate ca te duci prin, vei sfârși având de a face o mulțime de schimbare.
Cu anumite tipuri de cozi și anumite tipuri de structuri de date care stau la baza,
puteți să vă păstrați de fapt destul de simplu.
Nu trebuie să adăugați ceva și apoi remaniere totul de fiecare dată.
De asemenea, nu trebuie să faci o mulțime de deplasare a elementelor interne din jur.
Când ne uităm la o coadă, veți vedea că - de asemenea, în queue.c în secțiunea cod -
struct că am dat de tine este cu adevărat similară cu struct pe care v-am dat pentru un teanc.
>> Există o singură excepție de la acest lucru, și că o singură excepție
este că avem acest număr întreg suplimentară numită cap,
și capul de aici este pentru a ține evidența capul cozii,
sau primul element din coada.
Cu o stivă, noi am fost capabil de a urmări elementul care am fost pe punctul de a prelua,
sau partea de sus a stivei, folosind doar dimensiunea,
întrucât, cu o coadă, avem de a face cu capete opuse.
Încercăm să tac lucruri pe la final, dar apoi lucrurile se întoarcă de pe front.
Atât de eficient, cu capul, avem indicele de începutul cozii,
și dimensiunea ne dă indicele de sfârșitul cozii de așteptare
astfel încât să putem prelua lucruri din cap și se adaugă lucruri pe coada.
Întrucât, cu stivă, am fost doar vreodată de-a face cu partea de sus a stivei.
Am avut niciodată pentru a accesa partea de jos a stivei.
Am adăugat doar lucrurile la început și a luat lucrurile de pe partea de sus
asa ca nu am nevoie de acel câmp suplimentar în interiorul nostru struct.
Asta face, în general, un sens?
Bine. Da, Charlotte? [Charlotte, neinteligibil]
[Hardison] Asta-i o mare problema, iar asta a fost una care a venit în curs.
Poate mers pe jos prin câteva exemple de ce va ilustra
nu vrem să folosiți șiruri [0] ca șef al cozii.
>> Deci, ne imaginăm că avem coadă nostru, vom numi coadă.
La început, când am doar o instanțiat,
când ne-am tocmai a declarat, nu am inițializat nimic.
E tot gunoiul. Deci, desigur, vrem să ne asigurăm că vom inițializa
atât dimensiunea și domeniul cap să fie 0, ceva rezonabil.
Am putea merge mai departe și, de asemenea, null la elementele din coadă noastră.
Și pentru a face acest potrivi diagramă, observăm că acum coada noastră poate deține doar trei elemente;
întrucât stiva noastră ar putea deține patru, coada noastră poate deține doar trei.
Și asta e doar pentru a face potrivi diagrama.
Primul lucru care se întâmplă aici este că redați șirul "hi".
Și la fel cum am făcut și cu stiva, nimic teribil de diferit aici,
am arunca șir pe la siruri de caractere [0] și va incrementa dimensiunea noastră de 1.
Noi redați "la revedere", acesta este pus pe.
Deci, acest lucru arata ca o stivă pentru cea mai mare parte.
Am pornit la drum aici, element nou, element nou, dimensiunea ține merge în sus.
Ce se întâmplă în acest moment atunci când vrem să dequeue ceva?
Atunci când vrem să dequeue, care este elementul pe care dorim să dequeue?
[Vasile] Coarde [0]. Zero >>. Exact dreapta, Vasile.
Dorim să scape de primul șir, aceasta, "hi".
Deci, ceea ce a fost un alt lucru care a schimbat?
Observați atunci când mi-a venit ceva de pe stivă, am schimbat doar dimensiunea,
dar aici, ne-am luat o pereche de lucruri care schimbărilor.
Nu numai schimbarea dimensiunea, dar schimbările cap.
Acest lucru se întoarce la punctul de Charlotte mai devreme:
de ce avem acest cap, precum și?
Are sens acum, Charlotte? Cam >> de.
[Hardison] Natură? Deci, ce sa întâmplat atunci când am dequeued?
Ce a capului face asta acum este interesant?
[Charlotte] Oh, pentru că sa schimbat - în regulă. Înțeleg.
Deoarece capul - în cazul în care capul este îndreptat la schimbările în ceea ce privește locația.
Nu mai e întotdeauna un index de zero. >> Da, exact.
Ce sa întâmplat a fost în cazul dequeueing elementul de mare
a fost făcut și nu am mai avut acest domeniu cap
pentru ca am fost sunat mereu acest șir la 0 indicele capul cozii noastre,
atunci vom avea de a schimba restul cozii în jos.
Ne-ar trebui să treacă "la revedere" de la siruri de caractere de la [1] la siruri de caractere [0].
Și siruri de caractere [2] până la siruri de caractere [1].
Și vom avea de a face acest lucru pentru intreaga lista de elemente,
matrice întreaga de elemente.
Și când facem acest lucru cu o matrice, care devine cu adevărat costisitoare.
Deci, aici, nu e mare lucru. Noi avem doar trei elemente din gama noastră.
Dar dacă am avea o coadă de o mie de elemente sau un milion de elemente,
și apoi dintr-o dată, vom începe a face o grămadă de dequeue cheamă pe toți într-o buclă,
lucrurile sunt într-adevăr de gând să încetinească, deoarece schimbă totul în jos în mod constant.
Știi, schimba cu 1, schimbare de 1, schimbare de 1, schimbare de 1.
În schimb, vom folosi acest cap, o numim "pointer", chiar dacă nu e chiar un pointer
în sens strict, nu e un tip de pointer.
Nu e un * int sau un char * sau ceva de genul asta.
Dar e îndreptat sau care indică capul cozii noastre. Da?
>> [Student] Cum dequeue știe să pop doar off tot ceea ce este de la cap?
[Hardison] Cum dequeue știe cum să pop de pe orice e la cap? Corect >>, da.
Ce >> se uită la ce este doar câmpul este setat la cap.
Deci, în acest caz în primul rând, dacă ne uităm aici,
capul nostru este 0, 0 index. Corect >>.
[Hardison] Deci doar spune bine, bine, elementul de la indexul 0, șirul "hi",
este elementul de la capul de coada noastră.
Deci, vom dequeue tipul ăla.
Și care va fi elementul care se returnata apelantului.
Da, Saad? Deci, capul >> stabilește în esență - în cazul în care ai de gând să-l Indicele?
Asta e începutul de ea? Da >>. Bine >>.
[Hardison] Asta e din ce în ce nou început pentru gama noastră.
Deci, atunci când dequeue ceva, tot ce trebuie să faceți este să accesați elementul de la indexul q.head,
și care va fi elementul pe care doriți să dequeue.
De asemenea, trebuie să descrește dimensiunea.
Vom vedea într-un pic în cazul în care lucrurile devin un pic mai complicat cu acest lucru.
Noi dequeue, și acum, dacă ne redați din nou,
în cazul în care ne redați?
În cazul în care nu elementul următor merge în coada noastră?
Spune că vrem să redați șirul "CS".
În care indicele va merge? [Elevii] Coarde [2]. Doi >>.
De ce 2 și nu 0?
[Vasile] Pentru că acum capul este 1, astfel că e la fel ca la începutul listei?
[Hardison] Corect. Și ce denotă sfârșitul listei?
Ceea ce am fost utilizați pentru a desemna sfârșitul cozii noastre?
Capul este capul cozii noastre, începutul cozii noastre.
Care este sfârșitul cozii noastre? [Studenții] Size. Dimensiune >>, exact.
Deci, elemente de noile noastre merg în mărime de la, precum și elementele pe care le luăm desprinde de pe la cap.
Când ne-am redați elementul următor, vom aceasta punerea în mărime de la.
[Student] Înainte de a pune că, în desi, dimensiunea a fost de 1, nu?
[Hardison] Corect. Deci, nu destul de la dimensiunea. + Dimensiune nu, +1, dar capul +.
Pentru ca am mutat totul de suma de cap.
Deci, aici, acum avem o coadă de dimensiune 1, care începe de la indexul 1.
Coada este indicele 2. Da?
>> [Student] Ce se întâmplă când șiruri dequeue [0], precum și șiruri "sloturi de memorie în
doar te golit, practic, sau pur și simplu uitate?
[Hardison] Da. În acest sens, suntem doar le uita.
Dacă am fost stocarea copii ale acestora pentru -
multe structuri de date va stoca adesea copii proprii ale elementelor
astfel încât persoana care administrează structura de date nu trebuie să vă faceți griji
despre unde toate aceste indicii vor.
Structura de date montate pe la tot, pentru a deține toate copiile,
pentru a vă asigura că totul persistă în mod corespunzător.
Cu toate acestea, în acest caz, aceste structuri de date doar, pentru simplitate,
nu sunt de luare de copii de tot ceea ce suntem stocarea în ele.
[Student] Deci, este aceasta o gamă continuă de -? Da >>.
Dacă ne uităm înapoi la ceea ce a fost de definiția acestei structuri, este.
E doar o matrice standard, ca si cum ai văzut,
o serie de * e char.
Face asta -? Da >>, am fost doar întrebam
în cazul în care veți rula în cele din urmă de memorie, într-o anumită măsură,
dacă aveți toate aceste locuri goale în matrice ta?
[Hardison] Da, e un punct bun.
>> Dacă ne uităm la ceea ce sa întâmplat acum la acest punct,
ne-am umplut coadă nostru, se pare ca.
Dar nu am cu adevărat umplut coada noastră
pentru că avem o coadă care este mărimea 2, dar aceasta începe la indicele 1,
pentru că în cazul în care indicatorul nostru central este.
Ca spuneai, ca element de siruri de caractere de la [0], la indexul 0, nu este cu adevărat acolo.
Nu e în coada noastră mai.
Noi pur si simplu nu sa deranjat să meargă și să-l suprascrie atunci când l-am dequeued.
Deci, chiar daca se pare ca ne-am alerga afară de memorie, noi chiar nu avem.
Că la fața locului este disponibil pentru noi de a utiliza.
Comportamentul caz, dacă ar fi să încercăm și primul dequeue ceva
ca "la revedere", care ar pop pa off.
Acum coada noastră începe de la indexul 2 și este de dimensiuni 1.
Și acum, dacă vom încerca să redați ceva nou, să zicem 50,
50 ar trebui să meargă în acest loc, la index 0
deoarece este încă disponibilă pentru noi. Da, Saad?
[Saad] Asta se întâmplă în mod automat?
[Hardison] Aceasta nu se intampla destul de automat. Trebuie să faci matematică
pentru a face să funcționeze, dar în esență, ceea ce am făcut este tocmai am înfășurat în jurul valorii de.
[Saad] Și este în regulă dacă acest lucru are o gaura in mijlocul ei?
[Hardison] Este, dacă putem face matematica funcționeze în mod corespunzător.
>> Și se dovedește că nu e așa de greu de fapt de a face cu operatorul mod.
Deci, doar cum am facut cu Cezar si chestii cripto,
folosind Mod, putem ajunge să-și încheie în jurul valorii de lucruri și să păstreze merge
în jurul valorii de și în jurul și în jurul nostru, cu coadă,
menținându că indicatorul se deplasează în jurul capului.
Observați că dimensiunea este respectând întotdeauna numărul de elemente de fapt, în cadrul coada.
Și e doar indicatorul care ține capul de ciclism prin intermediul.
Dacă ne uităm la ce sa întâmplat aici, dacă ne întoarcem la început,
și te uiți doar ce se întâmplă cu cap
când ne redați ceva, nu sa întâmplat nimic la cap.
Când ne-am enqueued altceva, nu sa întâmplat nimic la cap.
Imediat ce am dequeued ceva, capul se duce de unul.
Noi enqueued ceva, nu se întâmplă nimic la cap.
Când ne-am dequeue ceva, toate dintr-o dată capul se incrementează.
Când ne-am redați ceva, nu se întâmplă nimic la cap.
>> Ce s-ar întâmpla în acest moment, dacă ar fi să dequeue ceva nou?
Orice gânduri? Ce s-ar întâmpla cu capul?
Ce ar trebui să se întâmple la cap
dacă ar fi să dequeue altceva?
Capul este acum la indexul 2,
ceea ce înseamnă că șeful coada este siruri de caractere [2].
[Student] Care returnează 0? Aceasta >> trebuie să revină la 0. Acesta ar trebui să înfășurați în jurul valorii de spate, exact.
Până în prezent, de fiecare dată când am sunat dequeue, am fost adăugând unul la cap,
adăuga unul la cap, adăugați una la cap, adăugați una la cap.
De îndată ce indicatorul capul ajunge la indicele de ultima gama noastră,
atunci trebuie să-l încheie în jurul valorii de înapoi la început, du-te inapoi la 0.
[Charlotte] Ce determină capacitatea de coadă într-o stivă?
[Hardison] În acest caz, tocmai am fost folosind o constantă # definit. Bine >>.
[Hardison] În fișierul în sine. C, poti sa te duci în bălegar și cu un pic
și să-l la fel de mare sau cât de puțin, după cum doriți.
[Charlotte] Deci, atunci când faci o coadă, cum faci calculatorul știu
cât de mare vrei să fie stiva?
[Hardison] Aceasta este o întrebare foarte bună.
Există o serie de moduri. Una este de a defini doar o în față
și spun acest lucru este mergi la a fi o coadă care are 4 elemente sau 50 de elemente sau 10.000.
Alt mod este de a face ceea ce oamenii hacker-ilor editia fac
și de a crea funcții pentru a avea coada ta să crească dinamic, ca mai multe lucruri se adaugă inch
>> [Charlotte] Deci, pentru a merge cu prima opțiune, ceea ce sintaxa folositi
pentru a spune programului ce este dimensiunea cozii?
[Hardison] Ah. Așa că hai să ieșim din asta.
Sunt încă în stack.c aici, așa că am de gând doar pentru a defila până la partea de sus aici.
Poți să vezi asta aici? Aceasta este # define capacitate de 10.
Și acest lucru este aproape exact aceeași sintaxă pe care o avem pentru coadă.
Cu excepția cazului în coada de așteptare, ne-am luat acest domeniu struct în plus aici.
[Charlotte] Oh, m-am gândit capacitatea de a însemnat capacitatea de șir.
[Hardison] Ah. Asta e. >> lungimea maximă a cuvântului. >> Am înțeles.
Da. Capacitatea de aici - asta e un mare punct.
Și acest lucru este ceva care este dificil
pentru că ceea ce am declarat aici este o matrice de char * s.
Un tablou de pointeri.
Aceasta este o serie de caractere.
Aceasta este, probabil, ceea ce ai văzut când ai fost declararea tampoane dvs. pentru dosar I / O,
atunci când ați fost crearea de siruri de caractere manual pe stiva.
Cu toate acestea, ceea ce am ajuns aici este o matrice de char * s.
Deci e un tablou de pointeri.
De fapt, dacă ne zoom înapoi și ne uităm la ceea ce se întâmplă pe aici
în prezentare, veți vedea că elementele reale, datele de caractere
nu este stocată în matrice în sine.
Ce este stocată în gama noastră aici sunt indicii ale datelor caracter.
Bine. Deci am văzut cum dimensiunea cozii este ca doar cu stivă,
dimensiunea respectă întotdeauna numărul de elemente în prezent în coada de așteptare.
După efectuarea 2 enqueues, dimensiunea este 2.
După efectuarea unei dequeue dimensiunea este acum 1.
După ce ați făcut o altă Puneți în coadă dimensiunea este înapoi până la 2.
Deci, cu siguranta dimensiunea respectă numărul de elemente în coada de așteptare,
și apoi capul ține doar de ciclism.
Se pleaca de la 0-1-2, 0-1-2, 0-1-2.
Și de fiecare dată când ne numim dequeue, indicatorul cap se incrementează la indicele următor.
Și dacă capul este pe cale de a trece peste, acesta buclele înapoi în jurul valorii de la 0.
Deci, cu asta, putem scrie funcția dequeue.
Și vom lăsa funcția Puneți în coadă pentru voi să pună în aplicare în schimb.
>> Când ne-am dequeue un element din coadă noastre,
ceea ce a fost primul lucru pe care Daniel a făcut-o când am început să scrie funcția de pop pentru stack-uri?
Lasă-mă să aud de la cineva care nu a vorbit încă.
Să vedem, Saad, îți amintești ce a făcut ca Daniel primul lucru când a scris pop?
[Saad] Nu a fost, a fost - >> El a testat pentru ceva.
[Saad] Dacă dimensiunea este mai mare decât 0. Exact >>.
Și ce a fost asta de testare pentru?
[Saad] Acest lucru a fost de testare pentru a vedea dacă există ceva în interiorul matrice.
[Hardison] Da. Exact. Deci nu poți pop nimic din stivă dacă e goală.
De asemenea, nu puteți dequeue orice, de la o coadă dacă e goală.
Care este primul lucru pe care ar trebui să facem, în funcție de dequeue noastră aici, nu crezi?
[Saad] Dacă dimensiunea este mai mare decât 0? Da >>.
În acest caz, am de fapt doar testat pentru a vedea dacă acesta este 0.
În cazul în care este 0, putem intoarce null.
Dar exact aceeași logică.
Și să continuăm cu asta.
În cazul în care dimensiunea nu este 0, în cazul în care este elementul pe care dorim să dequeue?
[Saad] La cap? Exact >>.
Putem trage doar din primul element din coada noastră
prin accesarea element la cap.
Nebun nimic.
După aceea, ceea ce ar trebui să facem? Ce are să se întâmple?
Care a fost alt lucru despre care am vorbit în dequeue?
Două lucruri trebuie să se întâmple, pentru că coada noastră sa schimbat.
[Daniel] Reducerea dimensiunii. Avem >> pentru a reduce dimensiunea, și de a crește cap? Exact.
Pentru a crește cap, nu putem pur și simplu crește orbește cap, minte.
Noi nu doar putem face queue.head + +.
Trebuie să includă, de asemenea, acest mod de capacitate.
Și de ce nu am modez de capacitate, Stella?
[Stella] Pentru că trebuie să-și încheie în jurul valorii de. Exact >>.
Am Mod de capacitatea pentru că are să-și încheie în jurul valorii de înapoi la 0.
Deci, acum, în acest moment, putem face ceea ce a spus Daniel.
Putem descreste marimea.
Și apoi ne putem întoarce pur și simplu elementul de care a fost la partea de sus a cozii.
Se pare un fel de noduros la început. S-ar putea avea o întrebare. Ne pare rău?
>> [Sam] De ce e mai întâi la partea de sus a cozii? În cazul în care nu a mers?
[Hardison] Ea vine de la patra linie din partea de jos.
După ce am testat pentru a se asigura că coada noastră nu este gol,
am scoate char * în primul rând, am scoate elementul care stă la indicele de cap
de matrice noastre, a noastra matrice siruri de caractere, >> și apelul pe care mai întâi?
[Hardison] Și noi numim prima. Da.
Doar pentru a urmări asta, de ce crezi că am avut de a face asta?
[Sam] Fiecare primul se întoarce doar q.strings [q.head]? Da >>.
Deoarece >> facem asta schimbare de q.head cu funcția mod,
și nu există nici o modalitate de a face acest lucru în termen de retur, de asemenea,.
[Hardison] Exact. Ești la fața locului. Sam e la fața locului în totalitate pe.
Motivul pentru care a trebuit să scot primul element din coada noastră și depozitați-l într-o variabilă
se datorează faptului că această linie în cazul în care am avut doar q.head,
nu e operatorului mod acolo nu este ceva ce putem face
și l-au produce efecte de la cap, fără a - într-o singură linie.
Deci, avem de fapt de a scoate primul element, apoi ajustați capul,
ajusta dimensiunea, și a reveni apoi elementul pe care am scos.
Și acest lucru este ceva pe care le vom vedea mai târziu, veni cu
Lista de preturi legate, după cum am juca în jurul valorii de cu ei.
De multe ori atunci când sunteți eliberarea sau eliminare a listelor legate de
aveți nevoie să vă amintiți urmatorul element, indicatorul următoare a unei liste legate
înainte de a înstrăina actual.
Pentru că altfel vă aruncați informații a ceea ce a mai rămas din lista.
Acum, dacă te duci la aparatul dumneavoastră, deschideți-queue.c-x din asta.
Deci, dacă am deschide queue.c, lasă-mă să mări aici,
veți vedea că aveți un fișier cu aspect asemănător.
Similar cu aspect fișier la ceea ce am avut mai devreme, cu stack.c.
Avem struct nostru pentru coada de definit așa cum am văzut-o pe slide-uri.
>> Avem funcția noastră Puneți în coadă, care este pentru tine să faci.
Și avem funcția dequeue aici.
Funcția dequeue în fișier este pusă în aplicare,
dar voi pune înapoi pe PowerPoint, astfel încât puteți să-l introduceți în, dacă doriți.
Deci, pentru următorii 5 minute sau cam asa ceva, voi lucra la Puneți în coadă
care este aproape opusul a dequeue.
Nu trebuie să se adapteze cap cand esti enqueueing, dar ceea ce nu trebuie să se adapteze?
Dimensiunea. Deci, atunci când Puneți în coadă, capul rămâne neatins, dimensiunea devine schimbat.
Dar aceasta nu ia un pic de - va trebui să joace în jurul valorii de cu mod
să dau seama exact ce indicele element nou ar trebui să fie introdus la.
Deci, voi da voi un pic, pus din nou pe dequeue diapozitiv,
și, ca voi aveti intrebari, le strig, astfel încât să putem
toate vorbesc despre ele ca un grup.
De asemenea, cu dimensiunea nu - atunci când reglați dimensiunea, poți întotdeauna doar -
aveți să mod dimensiunea vreodată? [Daniel] Nu >> Nu trebuie să mod mărimea, dreapta.
Deoarece dimensiunea va fi întotdeauna, dacă Esti - presupunând că sunteți de gestionare lucruri în mod corespunzător,
dimensiunea va fi întotdeauna între 0 și 3.
În cazul în care aveți să mod atunci când faci Puneți în coadă?
[Student] Numai pentru cap. Numai >> pentru cap, exact.
Și de ce trebuie să mod deloc în Puneți în coadă?
Atunci când este o situație în care ar trebui să mod?
[Student] Dacă aveți lucruri la spații, ca la spațiile 1 și 2,
si apoi ai nevoie pentru a adăuga ceva la 0.
[Hardison] Da, exact. Deci, în cazul în care indicatorul este capul de la sfârșitul foarte,
sau în cazul în care dimensiunea plus capul este mai mare, sau mai degrabă, se va incheia in jurul cozii.
>> Deci, în această situație, faptul că avem aici pe diapozitiv chiar acum,
dacă vreau să redați ceva chiar acum,
vrem să redați ceva la index 0.
Deci, dacă vă uitați la care merge 50, si eu sun Puneți în coadă 50,
se duce acolo, la partea de jos. Se merge in 0 index.
Acesta înlocuiește "hi", care a fost deja dequeued.
[Daniel] Nu ai grijă de faptul că, în dequeue deja?
De ce nu-l face nimic cu capul în Puneți în coadă?
[Hardison] Oh, deci nu ești modificarea cap, îmi pare rău.
Dar trebuie să utilizați operatorul mod atunci când accesați
elementul pe care doriți să o redați atunci când accesați
elementul următor din lista de așteptare.
[Vasile] n-am făcut asta, și m-am "succes" pe acolo.
[Daniel] Oh, înțeleg ce vrei să spui.
[Hardison] Deci tu didn't - ai făcut la q.size?
[Vasile] Da. Am schimbat doar fete, nu am făcut nimic cu cap.
[Hardison] Nu trebuie de fapt, pentru a reseta cap să fie ceva,
dar atunci când indicele în matrice siruri de caractere,
de fapt trebuie să mergeți mai departe și se calculează în cazul în care elementul următor este,
deoarece lozie stivă, elementul următor în stiva a fost întotdeauna
la indicele corespunzător dimensiunea.
Dacă ne uităm înapoi la funcția noastră împinge stivă,
am putea plunk mereu în elementul nostru nou dreptul la dimensiunea index.
Întrucât, cu coada, nu putem face asta
pentru că dacă suntem la această situație,
dacă ne enqueued 50 nostru nou șir ar merge chiar la siruri de caractere [1]
care noi nu vreau să fac.
Ne dorim să avem șirul noua du-te la indicele 0.
>> Are cineva - da? [Student] Am o întrebare, dar nu e chiar rude.
Ce înseamnă atunci când cineva solicită doar ceva ca indicatorul pred?
Care este acest nume scurt pentru? Știu că e doar un nume.
[Hardison] indicatorul Pred? Să vedem. În ce context?
[Student] A fost pentru inserare. Pot să vă întreb mai târziu, dacă doriți
pentru că nu e într-adevăr legate, dar eu doar -
[Hardison] Din cod lui David se introduce de la curs?
Putem trage în sus și faptul că vorbesc despre asta.
Vom vorbi despre asta viitoare, odată ce vom ajunge la liste legate.
>> Deci, haideți să uite foarte repede la ceea ce arata ca functia Puneți în coadă.
Care a fost primul lucru pe care oamenii au încercat să facă în linia ta Puneți în coadă? În această coadă?
Similar cu ceea ce ai făcut pentru stiva de împingere.
Ce-ai făcut, Stella?
[Stella, neinteligibil]
[Hardison] Exact. În cazul în care (q.size == capacitate) -
Am nevoie pentru a pune aparat dentar mele în locul potrivit - return false.
Mări un pic. Bine.
Acum, ce e urmatorul lucru pe care am avut de a face?
La fel ca și cu stiva, și introduc la locul potrivit.
Și deci ce era locul potrivit pentru a insera asta?
Cu stiva a fost dimensiunea index, cu aceasta nu e chiar asa.
[Daniel] Am q.head-sau-- q.strings >>? Da >>.
q.strings [q.head + q.size mod CAPACITATE]?
[Hardison] Noi, probabil, doriți să puneți paranteze în jurul valorii de această
astfel încât să ne apropiem corespunzătoare prioritate și, astfel încât este cleart pentru toată lumea.
Și a stabilit care sunt egale? Pentru >> str.? Pentru >> Str. Mare.
Și acum, ce e ultimul lucru pe care trebuie să facem?
La fel cum am facut-o in stiva. Increment >> dimensiunea? Increment >> dimensiunea.
Boom. Și apoi, din moment codul de pornire tocmai sa întors de fals în mod implicit,
vrem să schimbăm acest lucru adevărat, dacă totul merge prin intermediul și totul merge bine.
Bine. Aceasta este o mulțime de informații pentru secțiunea.
Noi nu suntem destul de peste. Vrem să vorbim despre foarte repede singure legate de preturi.
Voi pune asta ca să putem reveni la ea mai târziu.
Dar haideți să ne întoarcem la prezentarea noastra pentru doar câteva mai multe diapozitive.
Deci Puneți în coadă este TODO, acum l-am făcut.
>> Acum, haideți să aruncăm o privire la individual-linked liste.
Am vorbit despre acestea mai mult un pic în curs.
Câți dintre voi au văzut demo-ul în cazul în care am avut oameni
neîndemânatic arătând spre fiecare alte numere și deținerea? >> Am fost în asta.
>> Ce voi credeți? Credeți că, demistificarea Sperăm că aceste pic un pic?
Cu o listă, se pare că avem de a face cu acest tip de pe care vom apela un nod.
Întrucât, cu coada si stiva am avut struct că vom numim coada în stivă,
am avut aceste tipuri de coada nou în coșul de fum,
aici o listă este într-adevăr doar alcătuit dintr-un grup de noduri.
În același mod în care siruri de caractere sunt doar o adunatura de caractere toate aliniate una lângă alta.
O listă legată este doar un nod și un alt nod și un alt nod și un alt nod.
Și, mai degrabă decât zdrobitor toate nodurile împreună și stocarea lor contiguously
regulă lângă altul în memorie,
având în acest pointer lângă ne permite să stocați noduri ori de câte ori, în mod aleatoriu.
Și apoi un fel de sârmă-le pe toate împreună pentru a indica de la una la alta.
>> Și ce a fost marele avantaj că aceasta a avut mai mult de o matrice?
Peste tot stocarea contiguously doar lipite unul lângă celălalt?
Îți amintești? Da? >> Alocare dinamică a memoriei?
>> Alocare dinamică a memoriei, în ce sens?
[Student] În această puteți să vă păstrați acest site este mai mare și nu trebuie să se mute matrice întregul dvs.?
[Hardison] Exact. Deci, cu o matrice, atunci când doriți să puneți un element nou în mijlocul ei,
va trebui să treacă totul pentru a face loc.
Și ca și cum am vorbit despre cu coada,
de aceea ținem că indicatorul cap,
astfel încât să nu ne schimbă în mod constant lucruri.
Pentru că devine scump, dacă v-ați luat-o matrice mare
și ce faci în mod constant aceste insertii aleatorii.
Întrucât, cu o listă, tot ce trebuie să faceți este să arunce pe un nou nod,
ajusta indicii, și ați terminat.
Ce e de rahat despre asta?
În afară de faptul că nu este la fel de ușor de a lucra cu ca o matrice? Da?
[Daniel] Ei bine, cred că e mult mai greu de a accesa un element specific în lista de legat?
[Hardison] Nu poti sari doar la un element arbitrar în mijlocul listei legate.
Cum trebuie să-l facem schimb? >> Trebuie să pas prin întregul lucru.
[Hardison] Da. Trebuie să treacă printr-o la un moment dat, unul la un moment dat.
E un imens - este o durere.
Care e celălalt - există un alt căderea în acest sens.
[Vasile] Nu poți merge înainte și înapoi? Trebuie să mergi o singură direcție?
[Hardison] Da. Deci, cum putem rezolva asta, uneori?
[Vasile] dublu-legate de preturi? Exact >>. Există liste dublu-legate.
Există, de asemenea, - pare rau?
>> [Sam] E la fel ca utilizarea lucru pe care pred -
Mi-am amintit, nu este faptul că ceea ce este chestia pred pentru?
Nu este faptul că, în perioada de două ori și individual?
[Hardison] Să ne uităm la ce anume făcea.
Deci, aici vom merge. Iată lista codurilor.
Aici avem predptr, aici. Asta e ceea ce a fost vorba?
Deci asta a fost - el eliberarea o listă și încearcă pentru a stoca un pointer la el.
Acest lucru nu este de două ori, exemplare individuale legate de liste de.
Putem vorbi mai multe despre aceasta mai târziu, deoarece acest lucru este vorba despre eliberarea lista
și vreau să arate alte lucruri mai întâi.
dar e doar - e amintindu valoarea PTR
[Student] Oh, e indicatorul precedenta? Da >>.
Astfel încât să putem incrementa apoi ptr el însuși înainte de a ne apoi liber ceea ce este predptr.
Pentru că nu putem gratuit ptr si apoi suna ptr = ptr viitoare, nu?
Asta ar fi rău.
Deci, hai sa vedem, înapoi la tipul ăsta.
>> Un alt lucru rău despre preturi este că în timp ce cu o matrice
avem doar toate elementele s-au stivuite unul lângă altul,
aici am, de asemenea, au introdus acest indicator.
Deci, există o bucată suplimentară de memorie pe care avem de a utiliza
pentru fiecare element care ne stocarea în lista noastră.
Primim flexibilitate, dar vine la un cost.
Acesta este dotat cu acest cost de timp,
și vine cu acest cost de memorie prea.
Timpul în sensul că acum trebuie să treacă prin fiecare element în matrice
pentru a găsi cea de la indexul 10, sau că ar fi fost indexurile 10 într-o matrice.
>> Doar foarte repede, atunci când diagrama aceste liste,
de obicei ne ținem pe cap de listă sau indicatorul prima listă
și rețineți că acest lucru este un pointer adevărat.
E doar 4 octeți. Acesta nu e un nod în sine.
Deci, vedeți că nu are nici o valoare int în ea, nici indicatorul viitoare în ea.
E literalmente doar un pointer.
O să indice ceva care este un nod struct real.
[Sam] Un indicator numit nod? Acest lucru este >> - nu. Acesta este un pointer la ceva de tip nod.
Acesta este un pointer la un nod struct. >> Oh, bine.
Diagrama pe codul de stânga, în dreapta.
Ne putem seta la nul, care este o modalitate buna de a incepe.
Când o diagramă, scrii, fie ca nul sau ai pus o linie prin ea place asta.
>> Una dintre cele mai simple moduri de a lucra cu liste,
și vă cerem nu atât PREFIX și adăugați pentru a vedea diferențele dintre cele două,
dar este cu siguranta mai usor precedarea.
Când prefixului, acest lucru este în cazul în care - atunci cand PREFIX (7),
te duci și de a crea struct nod
și vă configurați mai întâi la punctul la ea, pentru că acum, de când l-am prefixate,
o să fie la începutul listei.
Dacă ne PREFIX (3), care creează un alt nod, dar acum 3 vine înainte de 7.
Deci, suntem în esență, împingând lucrurile pe lista noastră.
Acum, puteți vedea că PREFIX, uneori, oamenii o numesc împinge,
pentru ca esti împingând un element nou pe lista ta.
Este, de asemenea, ușor pentru a șterge în fața unei liste.
Deci, oamenii vor apela adesea că pop.
Și în acest fel, aveți posibilitatea să emuleze o stivă utilizând o listă legată.
Hopa. Ne pare rău, acum ne băgăm de adăugare. Deci, aici am prefixate (7), acum ne PREFIX (3).
Dacă ne prefixate altceva pe această listă, în cazul în care vom prefixate (4),
atunci vom avea 4 și apoi 3 și apoi 7.
Deci, atunci am putea pop și scoateți 4, îndepărtați 3, scoateți 7.
Adesea mod mai intuitiv să se gândească la acest lucru este cu adăugare.
Așa că m-am diagrama ce ar arata cu adăugați aici.
Aici, anexate (7) nu arata diferit
pentru că nu există decât un singur element din listă.
Și anexarea (3) îl pune la sfârșitul anului.
Poate puteți vedea chiar acum truc cu append
este că, deoarece știm numai în cazul în care la începutul listei este,
pentru a adăuga la o listă, trebuie să meargă tot drumul prin lista de
pentru a ajunge la final, opri, apoi nodul construi dvs. și tot ce Plunk jos.
Legați toate lucrurile sus.
Deci, cu PREFIX, așa cum ne-am rupt prin acest foarte repede,
Atunci când adauge la o listă, e destul de simplu.
>> Ai face nod nou, implica o anumită alocare de memorie dinamică.
Deci, aici vom face o struct nod folosind malloc.
Deci, suntem folosind malloc, pentru că vom retrase din circuitul agricol de memorie pentru noi pentru mai târziu
pentru că nu vrem acest lucru - vrem această memorie să persiste pentru o lungă perioadă de timp.
Și vom obține un pointer la spațiu în memorie pe care tocmai l-am alocat.
Noi folosim dimensiunea nod, nu ne rezuma câmpurile.
Noi nu generează manual numărul de octeți,
în schimb vom folosi sizeof, astfel încât să știm că vei primi un număr corespunzător de octeți.
Suntem asigurați-vă că pentru a testa apelul nostru malloc reușit.
Acest lucru este ceva ce vrei să faci, în general.
Pe mașinile moderne, în criză de memorie nu este ceva care e ușor
daca nu esti alocarea o grămadă de lucruri și de a face o listă uriașă,
dar dacă sunteți construirea chestii pentru, să zicem, cum ar fi un iPhone sau un Android,
veți face dispun de resurse limitate de memorie, mai ales dacă faci ceva intens.
Deci, este bine pentru a obține în practică.
>> Observați că am folosit un cuplu funcții diferite aici
pe care le-ați văzut că sunt un fel de noi.
Deci, fprintf este la fel ca printf
cu excepția primul argument este fluxul la care doriți să imprimați.
În acest caz, dorim să imprimați șirul eroarea standard
care este diferit de OutStream standard.
În mod implicit se arată în același loc.
Este, de asemenea, imprimă la terminalul, dar poți -
folosind aceste comenzi ați învățat despre tehnicile de redirecționare,
ați învățat despre în filme lui Tommy pentru set de probleme 4, puteți să-l direcționeze
pentru diferite domenii; ieși, apoi, chiar aici, iese programul tău.
E ca și cum, în esență se întorc din principal,
cu excepția vom folosi de ieșire, deoarece aici revenirea nu va face nimic.
Noi nu suntem în principal, astfel încât să nu ieși revenind program ca vrem.
Deci, vom folosi funcția de ieșire și dau un cod de eroare.
Atunci ne-am stabilit aici domeniu nou nod de valoare, câmpul I să fie egal cu I, iar apoi l-am sârmă sus.
Am stabilit indicatorul noul nod de pe lângă punctul la primul,
și apoi primul va indica acum la nod nou.
Aceste linii de cod prima, suntem de fapt, construirea unui nod nou.
Nu în ultimul două linii de această funcție, dar primele.
Puteți trage efectiv într-o funcție, într-o funcție de ajutor.
Asta e ceea ce fac eu de multe ori e, l-am scoate într-o funcție,
Eu îi spun ceva de genul nod construi,
și că păstrează funcția PREFIX destul de mic, e la doar 3 linii de atunci.
Fac un apel la funcția mea nod construi, iar apoi m-am tot sârmă sus.
>> Ultimul lucru vreau să-ți arăt,
și voi lăsa să faci de adăugare și tot ce pe cont propriu,
este cum să itera peste o listă.
Există o grămadă de moduri diferite de a itera peste o listă.
În acest caz, vom găsi lungimea unei liste.
Deci, vom începe cu o lungime = 0.
Acest lucru este foarte similar cu scrierea strlen pentru un șir.
Aceasta este ceea ce vreau să vă arăt, asta pentru bucla chiar aici.
Se pare cam înfricoșat, ea nu e obișnuită int i = 0, i <indiferent, i + +.
În schimb se inițializează variabila n noastră de a fi începutul listei.
Și apoi în timp ce variabila noastră iterator nu este nul, vom continua.
Acest lucru se datorează faptului că, prin convenție, la sfârșitul listei noastre va fi nulă.
Și apoi să incrementeze, mai degrabă decât a face + +,
echivalentul lista legată de + + este n = n-> urmator.
>> Te las să umple golurile de aici pentru că nu mai avem timp.
Dar ține minte acest lucru în timp ce lucra la psets spellr tale.
Lista de preturi legate, dacă punerea în aplicare a unui tabel hash,
vor veni cu siguranță în foarte la îndemână.
Și având această expresie pentru looping peste lucrurile se vor face viața mult mai ușoară, să sperăm.
Orice întrebări, repede?
[Sam] Va voi trimite SLL completat și sc?
[Hardison] Da. Voi trimite slide-uri completate și stiva SLL completat și queue.cs.
[CS50.TV]