DOUG LLOYD: Deci, în CS50, am acoperit o mulțime de diferite structuri de date, dreapta? Am văzut tablouri, și legat liste și tabele de dispersie, și încearcă, stive și cozi. Vom afla, de asemenea un pic despre copaci și grămezi, dar de fapt toate aceste doar termina a fi variații pe o temă. Există într-adevăr sunt acestea un fel de patru idei de bază că totul se poate fierbe în jos pentru a. Tablouri, liste legate, tabele de dispersie, și încearcă. Și cum am spus, nu variații pe ele, dar acest lucru este destul de mult va rezuma tot ceea ce vom vorbi despre în această clasă în ceea ce privește C. Dar cum toate aceste măsuri, nu? Am vorbit despre argumente pro și contra de fiecare în clipuri video separate pe ei, dar există o mulțime de numere obtinerea aruncat în jurul. Există o mulțime de generală gânduri obtinerea aruncat în jurul. Să încercăm și consolida l în doar un singur loc. Să cântărească avantajele împotriva contra, și ia în considerare care structură de date ar putea fi date drept structura pentru situatia dumneavoastra particulara, orice fel de date ce stocarea. Tu nu neapărat nevoie întotdeauna să utilizați super rapid de inserare, ștergere, și căutare a unui trie dacă într-adevăr Nu-mi pasă inserarea și ștergerea prea mult. Dacă aveți nevoie doar de repede aleatoare acces, poate un tablou este mai bine. Deci, haideți să distila asta. Hai sa vorbim despre fiecare dintre cele patru tipuri majore de structuri de date pe care le-am vorbit despre, și doar vedea cand acestea ar putea fi bun, și atunci când acestea s-ar putea să nu fie atât de bun. Așa că haideți să începem cu tablouri. Deci inserție, asta e un fel de rău. 

Inserție, la sfârșitul unei matrice este OK, dacă ne construim un tablou ca mergem. Dar dacă avem nevoie pentru a introduce elemente în centru, cred că înapoi la inserție sortare, există o mulțime de trecerea pentru a se potrivi un element acolo. Și așa, dacă vom introduce oriunde, dar la sfârșitul anului o matrice, care, probabil, nu e atât de mare. 

În mod similar, ștergere, cu excepția cazului în suntem ștergerea din sfârșitul unei matrice, este, probabil, de asemenea, nu atât de mare dacă nu vrem să plece lacune goale, care de obicei nu avem. Vrem să eliminați un element, și apoi un fel de a face confortabil din nou. Și astfel ștergerea elemente din o matrice, de asemenea, nu atât de mare. 

Căutare, deși, este mare. Noi avem acces aleator, căutare constantă de timp. Noi spunem doar șapte, și vom merge pentru matrice relocare șapte. Noi spunem 20, cu Du-te la matrice relocare 20. Noi nu trebuie să itera peste. Asta e destul de bun. 

Arrays sunt, de asemenea, relativ ușor pentru a sorta. De fiecare dată când am vorbit despre o sortare algoritm, cum ar fi de selecție fel, fel de introducere, cu bule de sortare, îmbinare fel, am întotdeauna folosit matrice a face acest lucru, deoarece matrice sunt destul de ușor de sortare, în raport cu structurile de date am văzut până acum. 

Sunt, de asemenea, relativ mică. Nu este o mulțime de spațiu suplimentar. Trebuie doar anularea exact la fel de mult ca ai nevoie de a organiza datele tale, și asta e destul de mult. Astfel încât acestea sunt destul de mici și eficient în acest mod. Dar un alt dezavantaj, deși, este că acestea sunt stabilite în mărime. Trebuie să declare exact cum mare dorim oferta noastră să fie, si ajungem o singura lovitura la ea. Nu putem crește și reduce o. 

Dacă avem nevoie să crească sau micsora aceasta, ne-am Trebuie să declare o serie complet nouă, copia toate elementele prima matrice în a doua matrice. Și dacă ne-am calculat greșit că timp, trebuie să o facem din nou. Nu atât de mare. Deci, tablouri, nu ne dau flexibilitatea de a avea un număr variabil de elemente. 

Cu o listă legată, inserare este destul de ușor. Tocmai am tac pe față. Eliminarea este, de asemenea, destul de ușor. Trebuie să găsim elemente. Care implică unele căutarea. 

Dar, odată ce ați găsit elementul sunteți în căutarea pentru, tot ce trebuie să faci este schimba un pointer, eventual două dacă aveți un legat list-- un dublu Lista legate, rather-- și apoi puteți elibera doar nodul. Nu trebuie să transfere totul în jur. Doar vă schimbați doi pointeri, așa că e destul de rapid. 

Căutare este rău, nu? Pentru ca noi să găsească o element dintr-o listă legată, dacă individual sau de două ori legate, trebuie să-l căuta liniară. Trebuie să începem de la început și muta la sfârșitul, sau de a începe de la capăt în mișcare la început. Noi nu avem acces aleator mai. Deci, dacă facem o mulțime de cautare, poate o listă de legat nu este chiar atât de bine pentru noi. 

Sunt de asemenea, foarte greu pentru a sorta, nu? Singurul mod în care poți sorta într-adevăr o listă legată este să-l sorta cum îl construiască. Dar, dacă-l rezolve în timp ce construi o, nu mai ești face inserții rapide mai. Nu ești doar tacking lucrurile pe față. Trebuie să găsiți cele mai locul potrivit să-l puneți, și apoi inserarea dvs. devine aproape la fel de rău ca introducerea într-o matrice. Deci, listele nu sunt legate de atât de mare pentru sortarea datelor. 

Sunt, de asemenea, destul de mici, de dimensiuni înțelept. Lista legate de două ori ușor mai mare decât liste individual legate, care sunt puțin mai mari decât tablouri, dar nu este o cantitate mare de spațiu irosit. Deci, dacă spațiul este la o primă, dar Nu o primă foarte intens, aceasta ar putea fi modul corect de a merge. 

Tabele de dispersie. Inserare într-un tabel hash este destul de simplu. Este un proces în două etape. În primul rând avem nevoie pentru a rula datele noastre prin o funcție hash pentru a obține un cod hash, și apoi ne-am introduce elementul în Tabelul hash la codul hash locație. 

Eliminarea, similar cu lista legate, este ușor odată ce ați găsit elementul. Trebuie să-l găsiți în primul rând, dar atunci când îl ștergeți, trebuie doar să facă schimb de un cuplu de indicii, dacă utilizați înlănțuirea separată. Dacă utilizați sondare, sau dacă nu sunteți folosind înlănțuirea la toate în tabelul hash, ștergere este de fapt foarte simplu. Tot ce trebuie să faceți este să hash date, și apoi du-te la acea locație. Și presupunând că nu nici coliziuni, vei putea să ștergeți foarte repede. 

Acum, căutare este în cazul în care lucrurile obține un pic mai complicat. E, în medie, mai bine decât liste legate. Dacă utilizați inlantuire, aveți în continuare o listă legată, ceea ce înseamnă că încă au căutare detrimentul o listă legată. Dar pentru că sunteți luați legat dvs. Lista și divizarea peste 100 sau 1000 sau n elemente în tabelul hash, ești Listele sunt legate una n-lea dimensiunea. Sunt toți în mod substanțial mai mici. Ați legate n liste loc de o listă legată de dimensiune n. 

Și așa această lume reală constantă factor, care noi, în general nu vorbesc despre în complexitate timp ea, de fapt, nu face o diferență aici. Deci căutare este încă liniară căutare dacă utilizați inlantuire, dar lungimea listei vă căutați prin este foarte, foarte scurt prin comparație. Din nou, în cazul în care sortarea este dvs. Scopul aici, hash masă a probabil, nu modul corect de a merge. Doar folosi un array dacă sortare este foarte important pentru tine. 

Și ei pot rula gama de dimensiuni. E greu de spus dacă o tabel hash este mic sau mare, pentru că într-adevăr depinde de cât de mare masa ta hash este. Dacă sunteți doar de gând să fie stocarea cinci elemente din tabelul hash, și aveți un tabel hash cu 10.000 de elemente în ea, esti, probabil, pierde o mulțime de spațiu. Contrast ești poate, de asemenea au tabele de dispersie foarte compacte, dar mai mici masa ta hash devine, cu atât mai mult fiecare dintre aceste liste legate persoanele. Și deci nu este într-adevăr nici o modalitate de a defini exact, ca dimensiune a unui tabel hash, dar este, probabil, în condiții de siguranță să spun este, în general va fi mai mare decât un legat Lista stocarea aceleași date, dar mai mică decât un trie. 

Și încearcă sunt a patra dintre aceste structuri care am vorbit despre. Introducerea într-un trie este complex. Există o mulțime de dinamică alocare de memorie, mai ales la început, cum începi să construiască. Dar e timpul constant. E doar elementul uman aici care face dificil. Având de a întâlni pointer null, malloc spațiu, du-te acolo, spațiu posibil malloc de acolo din nou. Un fel de factor de intimidare indicii în alocare de memorie dinamică este obstacol pentru a șterge. Dar, odată ce ați a reușit să respingă, inserție de fapt, vine destul de simplu, și cu siguranță este constanta de timp. 

Ștergerea este ușor. Tot ce trebuie să faceți este să mergeți în jos un câteva indicii și gratuit nodul, așa că e destul de bun. Căutare este, de asemenea, destul de rapid. Este numai pe baza lungime de datele. Deci, dacă toate datele dumneavoastră este cinci șiruri de caractere, de exemplu, te stocarea cinci șiruri de caractere în trie-ul, este nevoie de doar cinci pași pentru găsi ceea ce căutați pentru. Cinci este doar un factor constant, astfel încât din nou, inserare, ștergere, și căutare aici sunt toate constantă de timp, în mod eficient. 

Un alt lucru este că trie este de fapt, un fel de deja sortate, nu? În virtutea cum suntem Elemente inserarea, mergând scrisoare prin scrisoarea cheie, sau cifră cu cifră a cheii, de obicei, trie-ul sfârșește prin a fi un fel de sortate ca se va construi. Ea nu face cu adevărat sens să se gândească la sortarea în același mod în care ne gândim cu tablouri, sau liste legate, sau tabele de dispersie. Dar într-un fel, dumneavoastră trie este sortate ca te duci. 

Dezavantajul, desigur, este că un trie devine rapid foarte mare. Din fiecare punct de joncțiune, s-ar putea have-- dacă cheia este format din cifre, aveți 10 alte locuri poti sa te duci, care înseamnă că fiecare nod conține informații despre datele pe care doriți să stocați la acel nod, plus 10 indicii. Care, pe IDE CS50, este de 80 bytes. Deci, este de cel puțin 80 de bytes pentru fiecare nod pe care le creați, Și asta nu e chiar de numărare a datelor. Și dacă nodurile tale sunt litere în loc de cifre, acum ai 26 de indicii din orice locație. Și de 26 de ori 8 este, probabil, 200 bytes, sau ceva de genul asta. Și aveți de capital și vă puteți lowercase-- vezi unde am de gând cu asta, nu? Nodulii poate obține cu adevărat mare, și astfel trie în sine, în general, poate obține cu adevărat mare, prea. Deci, dacă spațiul este o mare premium pe sistemul dvs., un trie nu ar putea fi modul corect de a du-te, chiar dacă alte beneficiile sale intra in joc. Sunt Doug Lloyd. Acest lucru este CS50.