[Powered by Google Translate] [Secțiunea 6] [mai confortabil] [Rob Bowden] [Universitatea Harvard] [Acest lucru este CS50.] [CS50.TV] 

Putem merge la sectiunea noastra de intrebari. I-am trimis URL-ul pentru spațiu înainte. Începutul secțiunii de întrebări spun- se pare că nu sunt în totalitate unsick-este o întrebare foarte ușor de doar ceea ce se Valgrind? Ce face Valgrind face? Oricine vrea să spun ce Valgrind face? [Student] Verificări de memorie scurgeri. Da, Valgrind este un verificator de memorie generală. Aceasta, în final, vă spune dacă ai pierderi de memorie, care este cea mai mare parte ceea ce-l utilizați pentru că, dacă doriți să face bine în set de probleme sau dacă doriți să ajunge pe bord mare, trebuie să aveți nici un fel de pierderi de memorie, și, în cazul în care aveți o scurgere de memorie care nu le puteți găsi, De asemenea, ține cont de faptul că de fiecare dată când deschideți un fișier și dacă nu-l închide, că este o scurgere de memorie. 

O mulțime de oameni sunt în căutarea pentru unele nod pe care ei nu sunt eliberându când, de fapt, acestea nu au aproape dicționarul în chiar primul pas. De asemenea, vă spune dacă aveți orice invalidă citește sau scrie, ceea ce înseamnă că, dacă ați încerca și să stabilească o valoare care e dincolo de sfârșitul heap și nu se întâmplă să vină seg dar Valgrind-l prinde, ca nu ar trebui să fie, de fapt scris acolo, și deci cu siguranta nu ar trebui să aibă oricare dintre cele fie. Cum să utilizați Valgrind? Cum să utilizați Valgrind? 

E o problemă generală de un fel de a rula si uita-te la ieșire. De ieșire este copleșitoare de multe ori. Există, de asemenea, în cazul în care erorile de distracție, dacă aveți ceva teribil de greșit se întâmplă într-o buclă, atunci se va spune în cele din urmă, "Calea erori prea multe. Am de gând să se oprească de numărare acum. " E practic de ieșire sub formă de text pe care trebuie să analizăm. În final, el vă va spune orice pierderi de memorie pe care le au, cât de multe blocuri, care poate fi folositoare, deoarece în cazul în care ea este una unfreed bloc, atunci este, de obicei, mai ușor de găsit peste 1.000 de blocuri unfreed. 1000 blocuri unfreed, probabil, înseamnă că nu ești eliberându Lista de preturi dumneavoastră legate corespunzător sau ceva de genul. Asta e Valgrind. 

Acum avem sectiunea noastra de intrebari, care nu aveți nevoie pentru a descărca. Aveți posibilitatea să faceți clic pe numele meu și trageți-le în sus în spațiu. Acum, faceți clic pe mine. Revizia 1 va fi stivă, pe care facem primul. Revizia 2 va fi coadă, și Revizie 3 va fi legat lista individual. Incepand off cu stack nostru. Așa cum se spune aici, un teanc este una dintre cele mai de bază, structuri de date fundamentale ale informaticii. Exemplu foarte prototipic este stiva de tăvi în sala de mese. E practic ori de câte ori sunt introduse într-o stivă, cineva va spune, "Oh, ca un teanc de tăvi." Tu stivă tăvile în sus. Apoi, când te duci pentru a trage o tavă, tava primul care a tras este obtinerea ultima care a fost pus pe stiva. Stivă, de asemenea, ca-l spune aici- avem segmentul de memorie numită stivă. Și de ce este numit stiva? 

Pentru că la fel ca o stivă structura de date, l împinge și apare cadre coșul de fum pe stivă, în cazul în care cadrele stack sunt ca un apel specific al unei funcții. Și ca o stivă, veți avea întotdeauna să se întoarcă de la un apel de funcție înainte de a putea ajunge în jos, în cadre stack mai mici din nou. Nu puteți avea principal de bara de apel foo apel și a reveni la bar direct principal. Este întotdeauna trebuie să urmeze stiva corect împingându-și popping. Cele două operațiuni, cum am spus, sunt de împingere și pop. Acestea sunt termeni universale. Tu ar trebui să știi PUSH și POP, în ceea ce privește stive indiferent ce. Vom vedea cozile sunt un fel de diferite. Ea nu are într-adevăr un termen universal, dar PUSH și POP sunt universale pentru stack-uri. Push este doar pus pe stiva. Pop este scoate stivă. Și vom vedea aici, avem topul nostru typedef struct, așa că avem siruri de caractere char **. Nu te sperie de orice **. Acest lucru se va sfârși prin a fi o serie de siruri de caractere sau o matrice de pointeri la caractere, în cazul în care pointeri la caractere tind să fie siruri de caractere. Aceasta nu trebuie sa fie siruri de caractere, dar aici, ei vor fi siruri de caractere. 

Avem o serie de siruri de caractere. Avem o dimensiune, care reprezintă câte elemente sunt în prezent în stivă, și apoi avem capacitatea, care este cât de multe elemente poate fi pe stiva. Capacitatea ar trebui să înceapă off ca ceva mai mare decât 1, dar dimensiunea este de gând să încep cu 0. Acum, există, în principiu trei moduri diferite de care vă puteți gândi o stivă. Ei bine, există probabil mai multe, dar cele două modalități principale sunt puteți să-l pună în aplicare cu ajutorul unei matrice, sau puteți să-l pună în aplicare folosind o listă de legate. Lista de preturi legate sunt un fel de banale pentru a face stive de la. Este foarte ușor de a face un stack folosind liste legate, Deci, aici, vom face o stivă folosind tablouri, si apoi folosind tablouri, există, de asemenea, două moduri în care se poate gândi despre asta. Înainte, când am spus că avem o capacitate de stivă, astfel încât să putem potrivi un element pe stivă. 

Fel se-ar putea întâmpla este la fel de îndată ce te-a lovit 10 elemente, atunci ați terminat. S-ar putea ști că există o limită superioară de 10 lucruri din lume că nu vei avea mai mult de 10 lucruri pe stack-ul tău, caz în care puteți avea o limită superioară de mărimea stack-ul tău. Sau ai putea avea stack-ul trebuie nelimitat, dar dacă faci o matrice, ceea ce înseamnă că de fiecare dată te-a lovit 10 elemente, atunci ai de gând să trebuie să crească la 20 de elemente, și atunci când te-a lovit 20 de elemente, ai de gând să trebuie să crească la 30 de matrice dvs. de elemente sau 40 de elemente. Ai de gând să nevoie pentru a crește capacitatea, care este ceea ce am de gând să fac aici. De fiecare data cand vom ajunge la dimensiunea maximă a stivei noastre, când ne împinge altceva, ne-am de gând să nevoie pentru a crește capacitatea. Aici, ne-am împinge declarat ca împingere bool (char * str). Str. char * sir este ca suntem împingând pe stivă, și bool spune doar dacă am reușit sau nu. 

Cum putem eșua? Care este singura circumstanță pe care vă puteți gândi de în cazul în care am avea nevoie pentru a reveni fals? Da. [Student] Dacă e plin și suntem folosind o implementare mărginită. Da, așa cum ne definim-a răspuns el dacă e plin și suntem folosind o implementare mărginită. Apoi, vom reveni cu siguranta fals. De îndată ce ne-am lovit 10 lucruri pe care în matrice, nu putem potrivi 11, deci ne întoarcem fals. Ce se întâmplă dacă aceasta este nemarginita? Da. Dacă nu puteți extinde gama pentru un motiv oarecare. Da, deci memoria este o resursă limitată, și în cele din urmă, dacă păstrăm lucrurile împingând pe stiva de peste si peste, din nou, vom încerca să aloce o matrice mai mare pentru a se potrivi capacitate mai mare, și malloc sau orice ne utilizați este de gând să se întoarcă fals. Ei bine, malloc se va intoarce null. 

Amintiți-vă, de fiecare data cand suna vreodată malloc, ar trebui să fie de verificare pentru a vedea dacă acesta returnează null sau altceva, care este o deducere corectitudinea. Deoarece dorim să avem o stivă nelimitat, singurul caz vom fi returnarea fals este dacă vom încerca să creșterea capacității și malloc sau orice returneaza false. Apoi, pop nu ia argumente, și returnează șir care este pe partea de sus a stivei. Oricare ar fi fost cel mai recent împins pe stiva este ceea ce se întoarce pop, și-l elimină, de asemenea, că din stivă. Și observați că returnează null daca nu este nimic pe stiva. Este întotdeauna posibil ca stiva este gol. În Java, daca esti obisnuit cu asta, sau alte limbi, încercând să pop de la o stivă goală ar putea provoca o excepție sau ceva. 

Dar în C, nul este un fel de o mulțime de cazuri cum ne ocupăm de aceste probleme. Revenind nul este cum vom semnifica faptul că stiva era gol. Am furnizat un cod care va testa funcționalitatea stack-ului, punerea în aplicare a împinge și pop. Acest lucru nu va fi o mulțime de cod. Voi-de fapt, inainte de a face asta, aluzie, aluzie- în cazul în care nu ați văzut-o, malloc nu este singura funcție care alocă memorie pe heap pentru tine. Există o familie de funcții alloc. Primul este malloc, pe care ești obișnuit. Apoi, există calloc, care face același lucru ca și malloc, dar va zero, totul pentru tine. Dacă v-ați dorit vreodată pentru a seta totul la zero, după mallocing ceva ar fi trebuit sa folosit doar calloc în primul rând în loc de a scrie o buclă de la zero afară întregului bloc de memorie. 

Realloc este ca malloc si are o multime de cazuri speciale, dar în esență ceea ce face este realloc este nevoie de un pointer care au fost deja alocate. Realloc este funcția pe care doriți să fie atent la aici. Este nevoie de un pointer care au fost deja restituite de la malloc. Să spunem că ai solicita de la malloc un pointer de 10 octeți. Apoi, mai târziu îți dai seama că vrei 20 bytes, deci te sun realloc pe care indicatorul cu 20 de octeți, și realloc va copia în mod automat peste tot pentru tine. Dacă ați sunat doar malloc din nou, ca și cum am avea un bloc de 10 octeți. Acum am nevoie de un bloc de 20 de octeți, deci, dacă am malloc 20 bytes, atunci am să copiați manual peste 10 octeți de la primul lucru în al doilea lucru și apoi gratuit primul lucru. Realloc se va ocupa de asta pentru tine. 

Observați semnătura va fi void *, care se întoarce doar un pointer la blocul de memorie, apoi anulate * ptr. Vă puteți gândi la void * ca un pointer generic. În general, n-ai face cu void *, dar malloc se întoarce un void *, iar apoi este folosit doar ca acest lucru este, de fapt va fi un char *. * Nule anterior, care au fost returnate de către malloc este acum va fi trecut la realloc, și apoi mărimea este noul număr de octeți pe care doriți să le aloce, asa capacitatea de noua ta. Îți dau câteva minute, și fă-o în spațiul nostru. Începeți cu Revizia 1. Te voi opri după ce sperăm despre timp suficient pentru a pune în aplicare împingere, și apoi mă voi da o altă pauză pentru a face pop. Dar de fapt nu este acest cod de mult la toate. Codul este, probabil, cel mai chestii extinderea, extinderea capacității. Bine, nici o presiune pentru a fi complet făcut, dar atâta timp cât te simți ca și cum ești pe drumul cel bun, asta e bine. 

Are cineva orice cod se simt confortabil cu mine trăgând în sus? Da, voi face, dar nimeni nu are nici un cod pot trage în sus? Bine, poți începe, salvați-l, oricare ar fi ea? Mereu uit acel pas. Bine, se uită la apăsare, vrei să explice codul? [Student] În primul rând, am crescut marimea. Cred poate că ar trebui să aibă ca-oricum, am crescut marimea, și văd dacă e mai mică decât capacitatea. Și dacă e mai mică decât capacitatea, am adăuga la matrice pe care o avem deja. Și dacă nu e, am înmulțiți capacitatea de 2, și am realoca matrice siruri de la ceva, cu o dimensiune mai mare capacitate de acum. Și apoi, dacă aceasta nu reușește, eu spun de utilizator și a reveni fals, și, dacă e în regulă, apoi am pus șir în fața noului. 

[Rob B.] De asemenea, observați că am folosit un operator de frumos aici la nivel de bit să se înmulțească cu 2. Amintiți-vă, deviere la stânga este întotdeauna o să fie înmulțită cu 2. Shift dreapta este împărțit la 2, atâta timp cât vă amintiți că acesta înseamnă diviza de 2 ca într-un întreg împărțit la 2. S-ar putea trunchia un 1 aici sau acolo. Dar, schimbare lăsată de 1 este întotdeauna o să fie înmulțit cu 2, dacă nu se reverse în limitele întreg, și atunci nu va fi. Un comentariu parte. Îmi place să fac, acest lucru nu se va schimba de codificare nici un fel, dar îmi place să fac ceva de genul asta. Este de fapt este de gând să facă ceva mai lung. Poate că acest lucru nu este cazul perfect pentru a arăta acest lucru, dar îmi place să-l în segmentul de aceste blocuri de- regulă, în cazul în care acest lucru se întâmplă în cazul în care, apoi am de gând să fac ceva, și apoi funcția se face. Nu am nevoie să defilați, apoi ochii mei tot drumul în jos funcția pentru a vedea ce se întâmplă după altceva. E în cazul în care acest lucru se întâmplă în cazul în care, atunci mă întorc pur și simplu. Ea are, de asemenea, avantajul frumos adăugată de tot dincolo de acest este acum mutat părăsit o dată. Nu mai am nevoie să-dacă vreodată în apropierea liniilor de ridicol de lungi, atunci acele 4 octeți poate ajuta, de asemenea, și ceva mai mult stânga este, mai puțin copleșit-ai simți dacă doriți-bine, am să-mi amintesc Eu sunt în prezent într-o buclă în timp ce în interiorul unui alt interior de o bucla for. Oriunde puteți face acest lucru imediat întoarcere, am facut un fel de ca. E complet opțional și nu este de așteptat în nici un fel. 

[Student] Ar trebui să existe o dimensiune - în stare eșuează? Stare de respingere este aici nu am reușit să realloc, asa da. Observați cum în stare eșuează, probabil, dacă nu vom chestii gratuit mai târziu, suntem mereu de gând să eșueze indiferent de câte ori vom încerca să împingă ceva. Dacă ținem împingerea, ne păstrăm dimensiunea incrementare, chiar dacă noi nu se pune nimic pe stiva. De obicei, noi nu incrementați dimensiunea până la după ce ne-am pus cu succes pe stivă. Ne-ar face, să zicem, fie aici și aici. Și atunci în loc de a spune s.size ≤ capacitate, e mai puțin decât capacitatea, doar pentru că ne-am mutat în cazul în care totul a fost. 

Și ține minte, singurul loc care ne-ar putea reveni, eventual, fals este aici, în cazul în care realloc întors nul, și dacă se întâmplă să vă amintiți eroarea standard, Poate că s-ar putea lua în considerare acest caz o în cazul în care doriți să imprimați o eroare standard, stderr, astfel fprintf în loc de doar imprimarea direct în standard. Din nou, asta nu e o așteptare, dar dacă e vreo eroare, tastați printf, atunci este posibil să doriți să-l imprimați să eroarea standard în loc de afară standard. 

Oricine are ceva de remarcat? Da. [Student] Poti sa te duci peste [neauzit]? [Rob B.] Da, binariness reală de ea sau pur și simplu ceea ce este? [Student] Deci ai înmulți cu 2? [Rob B.] Da, de fapt. În țara binar, avem întotdeauna setul nostru de cifre. Deplasarea acest stânga până la 1 Practic introduce aici, la dreapta. Înapoi la acest lucru, amintindu-doar că totul în binar este o putere a lui 2, astfel încât aceasta reprezintă 2 la 0, 2 la acest 1, 2 la această 2. Prin introducerea unei 0 la dreapta acum, trecem totul peste. Ceea ce folosit pentru a fi de 2 la 0 este acum 2 la 1, este 2 la 2. Partea dreaptă pe care am inserat este în mod necesar va fi 0, ceea ce face sens. Dacă ați înmulțiți vreodată un număr de 2, aceasta nu se va termina ciudat, astfel încât 2 la locul de 0 ar trebui să fie 0, și acest lucru este ceea ce am avertizat despre jumătate înainte de a se dacă nu se întâmplă să schimbe dincolo de numărul de biți într-un număr întreg, atunci acest 1 se va termina prin a merge off. Asta e doar vă faceți griji dacă se întâmplă să fie într-adevăr de-a face cu capacități mari. Dar, la acel moment, atunci ai de-a face cu o serie de miliarde de lucruri, care nu s-ar potrivi în memorie, oricum. 

Acum putem ajunge la pop, care este chiar mai ușor. Ai putea-ți place, dacă se întâmplă să pop o grămadă, și acum ești la jumătate de capacitate din nou. Ai putea realloc pentru a micsora cantitatea de memorie aveți, dar nu trebuie să vă faceți griji cu privire la faptul că, așa cazul realloc doar va fi în creștere de memorie, nu în scădere de memorie, care se va face super-pop usoara. Acum cozi, care urmează să fie ca stive, dar ordinea în care luați lucrurile se inversează. Exemplu prototipic al unei cozi este o linie, deci cred ca daca ai fi limba engleză, mi-ar fi spus un exemplu prototipic al unei cozi este o listă de așteptare. Deci, ca o linie, daca esti prima persoana în linie, vă așteptați să fie prima persoană din linie. Dacă ești ultima persoană în linie, aveți de gând să fie ultima persoană de service. Noi numim acel model FIFO, LIFO întrucât stiva a fost model. Aceste cuvinte sunt destul de universale. 

Ca stive și, spre deosebire de tablouri, cozile de obicei, nu permit accesul la elemente în mijloc. Aici, o stivă, avem de împingere și pop. Aici, se întâmplă să am numit-le Puneți în coadă și dequeue. De asemenea, am auzit i-a chemat schimbare și unshift. Am auzit oameni spun PUSH și POP să se aplice, de asemenea, la cozi. Am auzit insera, elimina, astfel PUSH și POP, dacă este vorba despre stive, sunteți împingându-și popping. Dacă vorbești despre cozile, ai putea alege cuvintele pe care doriți să le utilizați pentru introducerea și îndepărtarea, și nu există un consens asupra a ceea ce ar trebui să fie numit. Dar aici, avem Puneți în coadă și dequeue. Acum, struct arata aproape identic cu struct stiva. Dar noi trebuie să țină evidența cap. Cred că se spune aici, dar de ce avem nevoie de cap? Prototipurile sunt, practic, identice pentru a împinge și pop. Vă puteți gândi la ea ca PUSH și POP. Singura diferență este pop se întoarce în loc de-trecut, se întoarce prima. 2, 1, 3, 4, sau ceva de genul. Și aici e începutul. Coada noastra este complet plin, asa ca nu e patru elemente în ea. Sfârșitul coada noastră este în prezent 2, iar acum mergem pentru a introduce altceva. 

Când vrem să inserați acel altceva, ceea ce am făcut pentru versiunea stivei ne-am extins este blocul nostru de memorie. Care este problema cu asta? [Student] Vă mutați 2. Ceea ce am spus mai devreme despre sfârșitul cozii de așteptare, acest lucru nu are sens să începem la 1, Apoi vrem să dequeue 1, apoi dequeue 3, apoi dequeue 4, apoi dequeue 2, dequeue atunci aceasta. Noi nu putem folosi realloc acum, sau cel puțin foarte, va trebui să utilizați realloc într-un mod diferit. Dar tu, probabil, nu ar trebui să folosească doar realloc. Ai de gând să aibă de a copia manual de memorie. 

Există două funcții de memorie pentru a copia. Nu e memcopy și memmove. Citesc în prezent, paginile man pentru a vedea care dintre ai de gând să doriți să o utilizați. Bine, memcopy, diferența este că memcopy și memmove, o tratează în mod corect cazul în cazul în care sunteți copierea într-o regiune care se întâmplă să se suprapună regiune te de la copierea. Memcopy nu-l ocupe. Memmove face. Vă puteți gândi la problema ca- Să zicem că vreau să copiați acest tip, aceste patru la acest tip de peste. În cele din urmă, ceea ce ar trebui să arate ca matricea după copiere este 2, 1, 2, 1, 3, 4, iar apoi unele chestii la sfârșitul anului. Dar acest lucru depinde de ordinea în care le copia, de fapt, deoarece, dacă nu considerăm faptul că regiunea suntem copierea în suprapune o suntem copiere de la, atunci am putea face ca început aici, copiați 2 în locul vrem să mergem, apoi mutați indicii noastre înainte. 

Acum vom fi aici și aici, și acum vrem să copiați acest tip de peste tipul ăsta și pentru a muta pointeri noastre mai departe. Ceea ce am de gând să sfârșesc prin obtinerea este de 2, 1, 2, 1, 2, 1 în loc de caz 2, 1, 2, 1, 3, 4, deoarece 2, 1 anulate originalul 3, 4. Memmove se ocupă de asta în mod corect. În acest caz, practic doar folosiți întotdeauna memmove pentru că se ocupă în mod corect. În general nu efectua orice rău. Ideea este loc de a porni de la început și copiere în acest fel așa cum am făcut aici, se pornește de la capăt și copiaza in, și, în acest caz, nu poți avea o problemă. Nu este nici o performanță pierdut. Folosiți întotdeauna memmove. Nu vă faceți griji cu privire la memcopy. Și asta e în cazul în care ai de gând să aibă de a memmove separat porțiunea înfășurat în jurul valorii de-a lista de așteptare. Nu vă faceți griji dacă nu este complet terminat. Acest lucru este mult mai dificil decât stivă, împinge, și pop. 

Oricine are orice cod am putea lucra cu? Chiar dacă complet incomplet? [Student] Da, e complet incomplet, totuși. Complet incompletă este bine, atâta timp cât ne-nu te poate salva de revizuire? Am uitat că de fiecare dată singur. Bine, ignorând ceea ce se întâmplă atunci când avem nevoie pentru a redimensiona lucrurile. Ignora complet redimensionare. Explică acest cod. Mă verificare în primul rând, dacă dimensiunea este mai mică decât prima copie a tuturor și apoi după aceea, am insera-am lua capul + dimensiune, și am asigurați-vă că se încadrează în jurul valorii de capacitatea de matrice, și am insera șir nou în această poziție. Apoi am crește dimensiunea și să se întoarcă adevărat. 

[Rob B.] Acest lucru este cu siguranta una dintre acele cazuri în care ai de gând să doriți să fie folosind Mod. Orice fel de caz unde ați ambalaj în jurul valorii de, dacă crezi în jurul valorii de ambalaj, gândul imediat ar trebui să fie Mod. Ca o optimizare rapida / a vă face o linie mai scurtă codul, observați că linia imediat după aceasta este doar marimea + +, astfel încât să îmbinați că în această linie, dimensiune + +. Acum aici, avem cazul în cazul în care nu avem suficientă memorie, așa că sunt în creștere capacitatea noastră de 2. Cred că ai putea avea aceeași problemă aici, dar o putem ignora acum, în cazul în care, dacă nu ați reușit să crească capacitatea dumneavoastră, atunci ai de gând să doriți să scadă capacitatea dvs. de 2 din nou. O altă notă scurtă este la fel ca poti sa faci + =, puteți face, de asemenea, << =. Aproape orice poate merge înainte egal, + =, | =, & =, << =. Char * bloc nou este noul nostru de memorie. Oh, aici. 

Ce cred oamenii despre tipul de blocul nostru nou de memorie? [Student] ar trebui să fie char **. Gândindu-mă la struct noastră până aici, siruri de caractere este ceea ce suntem realocare. Facem un întreg nou de stocare dinamic pentru elementele din coada de așteptare. Ceea ce am de gând să fie atribuirea siruri de caractere dvs. este ceea ce noi te mallocing acum, și atât de nou va fi un char **. O să fie o matrice de siruri de caractere. Atunci ceea ce este cazul în care ne vom întoarce false? [Student] ar trebui să facem char *? [Rob B.] Da, apel bună. [Student] Ce-a fost asta? [Rob B.] Am vrut sa facem dimensiunea char *, deoarece nu mai suntem- aceasta ar fi de fapt o problemă foarte mare pentru că sizeof (char) ar fi de 1. Sizeof * char va fi 4, astfel încât de multe ori atunci când ai de a face cu Ints, aveți tendința să scape cu ea, deoarece mărimea și dimensiunea int * int pe un sistem pe 32 de biți vor fi același lucru. Dar aici, sizeof (char) si sizeof (char *) sunt acum de gând să fie același lucru. 

Care este împrejurarea în care ne întoarcem fals? [Student] Nou este nulă. Da, în cazul în care noul este nul, ne întoarcem fals, și am de gând să arunce aici- [Student] [neauzit] [Rob B.] Da, acest lucru este bine. Ai putea face, fie de 2 ori capacitatea de schimbare sau de capacitatea de 1 și apoi doar stabilit aici, sau orice altceva. Vom face așa cum l-am avut. Capacitatea >> = 1. Și nu sunteți niciodată de gând să trebuie să vă faceți griji cu privire la pierderea locului lui 1 pentru că te-a părăsit decalate cu 1, deci locul lui 1 este în mod necesar un 0, astfel dreptul de deplasare de 1, sunteți încă de gând să fie bine. [Student] Ai nevoie să faci asta înainte de retur? [Rob B.] Da, acest lucru absolut nici un sens. 

Acum presupunem vom ajunge revenirea adevărat până la capăt. Modul în care ne vom face aceste memmoves, trebuie să fim atenți cu modul în care noi le facem. Are cineva orice sugestii despre cum le facem? Iată începutul nostru. În mod inevitabil, vrem să pornim de la început din nou și lucruri de copiere de acolo, în 1, 3, 4, 2. Cum faci asta? În primul rând, trebuie să se uite la pagina de manual pentru memmove din nou. Memmove, ordinea de argumente este întotdeauna importantă. Ne dorim ca destinație primul, al doilea sursă, a treia dimensiune. Există o mulțime de funcții care inversare sursă și destinație. Destinație, sursă tinde să fie în concordanță oarecum. Mutare, pentru ce se întoarce? Aceasta returneaza un pointer la destinație, indiferent de motiv ați putea dori asta. Eu pot citi imaginea, dar vrem să se mute în destinația noastră. 

Ceea ce este destinația noastră va fi? [Student] Nou. [Rob B.] Da, și unde ne copierea de la? Primul lucru pe care se copiază este acest lucru 1, 3, 4. Ce este aceasta-1, 3, 4. Care este adresa acestei 1? Care este adresa pe care 1? [Student] [neauzit] [Rob B.] Meciuri + adresa primului element. Cum ajungem primul element din matrice? [Student] coadă. [Rob B.] Da, q.strings. Amintiți-vă, aici, capul nostru este 1. Darn-l. Cred că e magic- Aici, capul nostru este 1. Am de gând să schimbe culoarea mea. Și aici este siruri de caractere. Acest lucru, putem scrie, fie că așa cum am făcut aici cu capete + q.strings. O mulțime de oameni a scrie, de asemenea, IT & q.strings [cap]. Acest lucru nu este adevărat nici mai puțin eficientă. S-ar putea gândi la ea ca dacă îl dereferencing si apoi obtinerea adresa, dar compilator este de gând să-l traduce ceea ce am avut înainte, oricum, q.strings + cap. Fie modul în care doriți să se gândească la asta. 

Și cum de multe bytes vrem să copiați? [Student] Capacitate - cap. Capacitate - cap. Și apoi ai putea scrie întotdeauna un exemplu să dau seama dacă e bine. [Student] Acesta trebuie să fie împărțit la 2, apoi. Da, așa cred am putea folosi dimensiunea. Avem încă dimensiunea fiind- folosind dimensiunea, avem dimensiune egală cu 4. Dimensiunea noastra este 4. Capul nostru este de 1. Dorim să copiați aceste 3 elemente. Asta e bun-simț verifica marimea - capul este corect 3. Și venind înapoi aici, așa cum am spus mai înainte, în cazul în care am folosit capacitatea, atunci vom avea de a diviza la 2 pentru ca ne-am dezvoltat deja capacitatea noastră, astfel încât în ​​loc, vom folosi dimensiune. Că copii care porțiilor. Acum, avem nevoie pentru a copia cealaltă porțiune, partea care a mai rămas din start. 

Asta o să memmove în ce poziție? [Student] Dimensiune Plus - cap. Da, așa că am deja copiat in marime - octeți cap, și așa mai departe în cazul în care dorim să copiați bytes rămase este nou și apoi dimensiunea minus-bine, numărul de octeți care le-am copiat deja inch Si apoi de unde ne copierea de la? [Student] Q.strings [0]. [Rob B.] Da, q.strings. Am putea face fie & q.strings [0]. Acest lucru este semnificativ mai frecvente decât aceasta. Dacă este doar de gând să fie 0, atunci ai tendinta de a vedea q.strings. Asta e atunci când suntem la copierea. Câte bytes ne-au lăsat să copieze? >> [Elevului] 10. Corect. [Student] Nu trebuie să ne multiplica 5 - 10 ori mai mare de octeți sau ceva de genul? Da, deci acest lucru este în cazul în care-exact ceea ce ne copiere? [Student] [neauzit] Care este tipul de lucru pe care suntem copiere? [Student] [neauzit] Da, așa e char * ca suntem copierea, nu știm unde acestea sunt provin din. Ei bine, în cazul în care acestea sunt arătând spre, cum ar fi siruri de caractere, vom ajunge, împingându-l pe coadă sau enqueuing pe coada. În cazul în care acestea sunt provin din, nu avem nici o idee. Avem nevoie doar de a urmări * e char ei înșiși. Noi nu vrem să copiați dimensiunea - octeți cap. Dorim să copiați dimensiunea - cap char * s, deci vom multiplica acest lucru prin sizeof (char *). Same aici, cap de * sizeof (char *). 

[Student] Ce [neauzit]? Acest drept aici? [Student] Nu, mai jos, care, dimensiunea - cap. [Rob B.] Acest drept aici? Pointer aritmetică. Cum aritmetică indicatorul se va lucra este se multiplică în mod automat în funcție de mărimea tipul care am de-a face cu. La fel ca aici, noi + (dimensiune - cap) este exact echivalent cu & [size - cap] nou până când ne așteptăm ca să funcționeze corect, deoarece dacă avem de-a face cu o serie int, atunci nu ne facem indicele de int- sau în cazul în care este de dimensiunea de 5 și doriți elementul patra, apoi am indicele în int matrice [4]. Ai tăcerea: nu-[4] Dimensiunea * de int. Că se ocupă în mod automat, și acest caz, este literalmente echivalent, astfel încât suportul sintaxa este doar de gând să fie convertite la acest lucru ca de îndată ce vă compilați. Asta e ceva ce trebuie să fie atent de faptul că atunci când sunt adăugați dimensiunea - cap adăugați nu un octet. Te adăugarea unei char *, care poate fi unul octeți sau orice altceva. 

Alte întrebări? Bine, dequeue va fi mai ușor. Îți dau un minut să pună în aplicare. Oh, și cred că acest lucru este în cazul în care aceeași situație ce caz Puneți în coadă, dacă suntem enqueuing nul, Poate că vrem să-l ocupe, poate că nu. Noi nu-l va face din nou aici, dar la fel ca stiva cazul nostru. Dacă ne redați nul, ne-am putea dori să-l ignore. Oricine are unele cod pot trage în sus? [Student] Am doar dequeue. Versiunea 2 este faptul că-în regulă. Vrei să explice? [Student] În primul rând, vă asigurați că nu e ceva în coada de așteptare și că dimensiunea este merge în jos de 1. Ai nevoie să faci asta, și apoi vă întoarceți capul și apoi mutați capul sus 1. Ok, deci nu este un caz colț trebuie să ia în considerare. Da. [Student] În cazul în care capul este la ultimul element, atunci nu vrei cap la punctul in afara de matrice. 

Da, deci imediat în calitate de șef ajunge la capatul gama noastră, când am dequeue, capul nostru ar trebui să fie modded inapoi la 0. Din păcate, nu putem face asta într-un singur pas. Cred că modul în care aș repara probabil că este acest lucru este mergi la a fi un char *, ceea ce ne revin, indiferent de numele tău este variabilă vrea să fie. Apoi ne-am dori sa modez cap de capacitatea noastră și a reveni apoi retras. O mulțime de oameni aici, s-ar putea do- acesta este cazul, veți avea văd oameni fac în cazul în cap este mai mare decât capacitatea, nu capul - capacitate. Și asta e doar de lucru în jurul valorii de ceea ce este MOD. Capacitatea de cap = mod este mult mai curat a unui ambalaj în jurul valorii de cap mai mare decât în ​​cazul în care capacitatea de cap - capacitate. 

Întrebări? Bine, ultimul lucru pe care l-am lăsat este lista noastră de legat. S-ar putea fi folosite la unele dintre comportament lista de legat, dacă ai făcut-o legat de preturi din tabele de dispersie, dacă ai făcut un tabel hash. Vă recomandăm cu tărie fac un tabel hash. Este posibil să fi făcut deja un trie, dar incearca sunt mult mai dificil. În teorie, sunt asimptotic mai bine. Dar uita-te doar la bord mare, și încearcă niciodată face mai bine, și le iau mai multa memorie. Totul despre Incearca sfârșește prin a fi mai rău pentru mai mult de lucru. E ceea ce soluție David Malan lui este întotdeauna este el mesaje întotdeauna soluția lui trie, și să vedem unde în prezent este. Ceea ce era sub, David J? E # 18, astfel că nu e teribil de rău, și că va fi una dintre cele mai bune încearcă vă puteți gândi sau unul din cele mai bune încearcă o trie. Nu este chiar soluția lui original? Mă simt ca soluții trie tind să fie mai mult în acest interval de utilizare RAM. 

Du-te la partea de sus foarte, și folosirea RAM este în cifre unice. Du-te jos spre partea de jos, și apoi începe să vedeți încearcă în cazul în care veți obține utilizarea RAM absolut masiv, și încearcă sunt mai dificil. Nu în întregime în valoare de ea, ci o experiență educațională în cazul în care ai făcut-o. Ultimul lucru este lista noastră de legat, și aceste trei lucruri, stive, cozi, și liste legate, orice lucru viitor mai faci în informatică se va presupune că avea familiaritate cu aceste lucruri. Acestea sunt doar atât de fundamentală pentru tot. 

Legat de preturi, iar aici am o listă individual legat va fi punerea în aplicare noastră. Ce înseamnă individual legată înseamnă, spre deosebire de două ori legat? Da. [Student] Se indică numai indicatorul următoare, mai degrabă decât de indicii, ca cel ce o precede și unul după ea. Da, astfel încât în ​​format de imagine, ce-am făcut? Am două lucruri. Am imagine și imagine. În formatul de imagine, liste de unu noastre legate, în mod inevitabil, avem un fel de pointer la capul listei noastre, și apoi, în cadrul listei noastre, avem doar pointeri, și poate că acest puncte de la zero. O să fie desenul tipic al unei liste individual legat. O listă dublu legat, poti sa te duci înapoi. Dacă îți dau orice nod în listă, atunci puteți obține în mod necesar la orice alt nod în listă în cazul în care este vorba de o listă de două ori legat. Dar dacă am să te nodul treilea listă și este o listă legată individual, nici o cale de ai vreodată de gând să ajungă în prima și a doua noduri. Și nu există beneficii și dezavantaje, și un o evidentă se va duce in sus dimensiune mai, și va trebui să urmăriți în cazul în care aceste lucruri sunt orientate acum. Dar ne pasă doar de separat legat. 

Câteva lucruri pe care le vom avea să pună în aplicare. Nodul typedef struct, int i: struct nod * următor; nod. Asta ar trebui să fie arse typedef în mințile voastre. Test 1 ar trebui dori dea un typedef unui nod listă legată, și ar trebui să fie în măsură să noteaza imediat că se fără să se mai gândească la asta. Cred că cateva intrebari, de ce avem nevoie de struct aici? De ce nu putem spune * nod? [Student] [neauzit] Da. Singurul lucru care definește un nod ca un lucru este typedef în sine. Dar, ca de la acest punct, atunci când suntem un fel de parsare prin intermediul acestei definiții nod struct, nu ne-am terminat typedef noastră încă, deci din moment typedef nu sa terminat, nod nu exista. Dar struct nod face, iar acest nod aici, acest lucru ar putea fi numit, de asemenea, nimic altceva. Acest lucru ar putea fi numit nr. Ar putea fi numit nod lista de legat. Ar putea fi numit nimic. Dar acest nod struct trebuie să fie numit același lucru ca și acest nod struct. Ceea ce voi numiti acest lucru trebuie să fie, de asemenea, aici, și, de asemenea, astfel încât răspunde al doilea punct de discuție care este motivul pentru-o de multe ori, când veți vedea struct și typedefs de struct, veți vedea struct anonime în cazul în care veți vedea doar typedef struct, punerea în aplicare a struct, dicționar, sau orice altceva. 

De ce aici avem nevoie să spunem nod? De ce nu poate fi o struct anonim? Este aproape același răspuns. [Student] Trebuie să se refere la acesta în struct. Da, în cadrul struct, trebuie să se refere la struct sine. Dacă nu dau struct un nume, dacă e un struct anonim, nu se poate referi la ea. Si nu in ultimul rand, acestea nu ar trebui să fie oarecum simplă, și acestea ar trebui să vă ajute să realizeze daca scrii asta în jos că faci ceva greșit dacă aceste felul de lucruri care nu fac sens. Nu în ultimul rând, de ce face acest lucru trebuie să fie struct nod *? De ce nu poate fi struct nod doar următoare? [Student] Pointer la struct următoare. Asta e inevitabil ceea ce ne dorim. De ce ar putea fi niciodată nod struct viitoare? De ce trebuie să fie struct nod * următor? Da. [Student] E ca o buclă infinită. Da. [Student], ar fi totul într-o singură. Da, doar că de modul în care ne-ar face dimensiunea sau ceva. Dimensiunea unei structuri este de fapt + sau - un tipar aici sau acolo. Este practic va fi suma dimensiunilor de lucruri în struct. Acest drept aici fără a schimba ceva, este dimensiunea va fi ușor. Mărimea nod struct va fi dimensiunea i mărimea + de viitor. Dimensiunea lui i va fi 4. Dimensiunea de lângă va fi 4. Mărimea nod struct va fi 8. Dacă nu avem *, de gândire de sizeof, apoi sizeof (i) va fi 4. Mărimea nod struct următoarea va fi dimensiunea i mărimea + struct nod de lângă Dimensiunea + de + i dimensiunea de nod struct următoare. Ar fi o recursivitate infinita de noduri. Acesta este motivul pentru acest lucru este modul în care lucrurile trebuie să fie. 

Din nou, memoreze cu siguranță că, sau cel puțin se înțelege suficient faptul că puteți fi în măsură să Motivul prin ceea ce ar trebui să arate. Lucrurile pe care le vom dori să pună în aplicare. Dacă lungimea lista- ai putea trișa și să păstreze în jurul valorii de un Durata globală sau ceva, dar noi nu vom face asta. Vom conta lungimea listei. Ne-am conține, așa că e practic ca o căutare, așa că avem o listă legată de numere întregi pentru a vedea dacă acest întreg este în lista de legat. PREFIX se va insera la începutul listei. Append este de gând să introduceți la sfârșitul anului. Insert_sorted se va insera în poziția sortate în listă. Un fel de Insert_sorted presupune că niciodată nu ați utilizat PREFIX sau adăugați în moduri proaste. 

Insert_sorted atunci când sunteți de punere în aplicare insert_sorted- Să presupunem că avem lista noastră legată. Aceasta este ceea ce arata ca in prezent, 2, 4, 5. Vreau să inserați 3, atâta timp cât lista de sine este deja sortat, e ușor să găsiți în cazul în care face parte 3. Am încep de la 2. Bine, 3 este mai mare de 2, așa că vreau să continui. Oh, 4 este prea mare, așa că știu 3 este de gând să meargă în între 2 și 4, și trebuie să stabilească indicii și toate chestiile alea. Dar dacă nu ne-am folosi strict insert_sorted, ca să spunem doar că prefixului 6, apoi lista mea de legat este de gând să devină asta. Se face acum nici un sens, asa ca pentru insert_sorted, puteți presupune doar că lista este sortată, chiar dacă există operații care poate provoca aceasta să nu fie sortate, iar asta e tot. Găsiți un utill inserați-Deci, acestea sunt principalele lucruri ai de gând să trebuie să pună în aplicare. 

Pentru moment, să ia un minut pentru a face lungime și conține, și acestea ar trebui să fie relativ rapid. Apropie ora închiderii, astfel încât oricine are ceva de lungime sau conține? Ei vor să fie aproape identice. [Student] Lungime. Să vedem, revizuire. Bine. Vrei să explice? [Student] pot crea doar un nod pointer și inițializa-l la primul, care este variabila noastră globală, și apoi am verifica pentru a vedea dacă este nulă, așa că am nu primesc un defect segment și pentru a reveni 0 dacă e cazul. În caz contrar, am bucla prin, urmărirea în termen de număr întreg de câte ori am accesat urmatorul element al listei și în același operație incrementului accesa, de asemenea, faptul că elementul real, si apoi fac continuu verificare pentru a vedea dacă este nulă, și, dacă este nulă, atunci va abandona și returnează doar numărul de elemente le-am accesat. 

[Rob B.] Are cineva vreun comentariu pe nimic? Acest lucru arata corectitudinea bine înțelept. [Student] Nu cred că ai nevoie de nod == null. Da, așa că, dacă nodul == 0 intoarce null. Dar dacă nodul == null atunci acest oh-, există o problemă de corectitudine. A fost doar te-am întoarce, dar nu e în sfera de aplicare chiar acum. Ai nevoie doar de int i, deci i = 0. Dar dacă nodul este nul, atunci i este în continuare va fi 0, și am de gând să se întoarcă 0, deci acest caz este identic. Un alt lucru comun este de a păstra declarația din interiorul nod de buclă pentru. Ai putea spune-oh, nu. Să păstrați-l ca asta. Mi-ar pune, probabil, int i = 0 aici, apoi nod * nod = prima aici. Și acest lucru este, probabil, modul în care-a scăpa de asta acum. Acesta este, probabil, cum mi-ar fi scris. Ai putea, de asemenea, se uită la el, ca asta. Această structură de buclă chiar aici ar trebui să fie aproape la fel de natural pentru tine, ca pentru int i = 0 i este mai mică decât lungimea de matrice i + +. Daca asta e modul în care repeta peste o matrice, acesta este modul în care repeta peste o listă legată. 

Acest lucru ar trebui să fie a doua natura la un moment dat. Cu asta în minte, acest lucru este mergi la a fi aproape același lucru. Ai de gând să doriți să itera peste o listă legat. Dacă nodul-am nici o idee despre ceea ce se numeste valoarea. Nodul i. În cazul în care valoarea de la acel nod = i întoarcă adevărat, și asta e tot. Observați că singurul mod de a reveni vreodată fals este, dacă am repeta peste intreaga lista legate și nu se mai întorc adevărat, Deci asta ce face asta. Ca o parte notă-ne, probabil, nu va primi să adăugați sau adauge. 

Rapidă ultima nota. Dacă vedeți cuvântul cheie static, așa că hai să spunem static int count = 0, atunci vom face numărătoarea + +, vă puteți gândi la ea ca practic o variabilă globală, chiar dacă am spus acest lucru nu este modul în care vom pune în aplicare lungime. Eu fac asta aici, și apoi conta + +. Orice fel putem introduce un nod în lista noastră de legat suntem incrementarea numărului nostru. Punctul de acest lucru este ceea ce înseamnă cuvântul cheie static. Dacă aș fi avut doar count int = 0, care ar fi o variabilă regulat vechi globale. Ce înseamnă static int count este că acesta este o variabilă globală pentru acest fișier. Este imposibil pentru un alt fișier, cred ca de PSET 5, în cazul în care ați început. Aveți atât speller.c, și aveți dictionary.c, și dacă declară doar o chestie la nivel mondial, apoi nimic în speller.c pot fi accesate în dictionary.c și vice-versa. Variabilele globale sunt accesibile de către orice fișier. C, dar variabilele statice sunt accesibile doar din interiorul fișierul propriu-zis, astfel încât interiorul corector ortografic sau în interiorul dictionary.c, acest lucru este un fel de cum mi-ar declar variabila mea pentru dimensiunea matrice meu sau dimensiunea de numărul meu de cuvinte în dicționar. Din moment ce nu vreau să declare o variabilă globală care oricine are acces la, Am într-adevăr numai pasă de el pentru propriile mele scopuri. 

Lucru bun despre acest lucru este, de asemenea, întregul coliziune chestii nume. În cazul în care un alt fișier încearcă să utilizeze o variabilă globală numită count, lucrurile merg foarte, foarte greșit, Deci, acest frumos păstrează în condiții de siguranță lucruri, și doar tu poți accesa, și nimeni altcineva nu poate, iar dacă altcineva declară o variabilă globală numită count, atunci nu va interfera cu variabila statica numita numărătoarea. Asta e ceea ce este static. Acesta este un fișier variabilă globală. 

Întrebări cu privire la ceva? Toate set. Pa. [CS50.TV]