DOUG LLOYD: Kaya sa CS50, namin sakop isang pulutong ng mga iba't ibang mga istraktura ng data, right? Nakita namin ang array, at naka-link mga listahan, at hash talahanayan, at sumusubok, stack at queue. Makikita rin namin malaman ang kaunti tungkol sa mga puno at tambak, ngunit talagang ito ang lahat ng end lang up na mga pagkakaiba-iba sa isang tema. May tunay ay mga uri ng apat na pangunahing mga ideya na lahat ng iba pa ay maaaring pasingawan sa. Ang mga array, naka-link na listahan, hash talahanayan, at sumusubok. At tulad ng sinabi ko, may mga pagkakaiba-iba sa mga ito, ngunit ito ay medyo magkano ang pagpunta sa maikling pangungusap lahat kami ay pagpunta sa makipag-usap tungkol sa ganitong klase sa mga tuntunin ng C. Ngunit kung paano gawin ang mga ito ang lahat ng mga panukalang-batas up, di ba? Pinag-usapan natin ang tungkol sa mga kalamangan at kahinaan ng bawat isa sa hiwalay na mga video sa mga ito, ngunit may isang pulutong ng mga numero nagsisimula pa itinapon sa paligid. May isang pulutong ng mga pangkalahatang saloobin sa pagkuha itinapon sa paligid. Subukan at pagsamasamahin Ipaalam ito sa isang lugar lamang. Timbangin ni ang mga kalamangan laban Ipaalam ang kahinaan, at isaalang-alang na istraktura ng data maaaring tamang data istraktura para sa iyong partikular na sitwasyon, kahit anong uri ng data na iyong pag-iimbak. Huwag kang hindi kinakailangang laging kailangan upang gamitin ang mga sobrang mabilis insertion, pagtanggal, at lookup ng isang trie kung talagang hindi pag-aalaga tungkol sa pagpasok at pagtanggal Sobra. Kung kailangan mo lamang ng mabilis na random access, marahil ng isang array ay mas mahusay. Kaya ni distill na ipaalam. Makipag-usap tungkol sa bawat isa sa apat na mga Ipaalam pangunahing uri ng mga istruktura ng data na namin ang uusapang tungkol sa, at makita lamang kapag sila ay maaaring maging mahusay, at kapag sila ay maaaring hindi mabuti. Kaya simulan na may mga array ipaalam. Kaya insertion, na ang uri ng masama. 

Insertion sa dulo ng isang array ay OK, kung kami ay pagbuo ng isang array na pumunta kami. Ngunit kung kailangan namin upang ipasok elemento sa gitna, sa tingin bumalik sa insertion uri, mayroong isang pulutong ng paglilipat upang magkasya ang isang elemento sa doon. At kaya kung kami ay pagpunta sa ipasok kahit saan ngunit sa pagtatapos ng isang array, na malamang ay hindi kaya mahusay. 

Katulad nito, pagtanggal, maliban kung hindi namin ang pagtanggal mula sa dulo ng isang array, ay hindi kaya mahusay na kung marahil din hindi namin nais na mag-iwan na walang laman gaps, na kung saan ay karaniwang hindi namin. Gusto naming alisin ang isang sangkap, at pagkatapos ay ang uri ng mga gawing maginhawa muli. At kaya pagtanggal ng mga elemento mula sa isang array, hindi rin kaya malaki. 

Lookup, bagaman, ay malaki. Mayroon kaming random access, pare-pareho ang oras lookup. Sabihin lang namin pitong, at kami ay pumunta sa array paglilipat pitong. Sabihin namin 20, na may pumunta sa array paglilipat 20. Wala kaming upang umulit sa kabuuan. Iyan ay medyo mabuti. 

Ang mga array ay din medyo madali upang ayusin. Sa bawat oras na usapan natin ang tungkol sa isang pag-uuri algorithm, tulad ng pagpili ng uri, uuri, bubble uri, sumanib uri, palagi naming ginagamit array na gawin ito, dahil array ay medyo madali na uri-uriin, kamag-anak sa mga istraktura ng data nasaksihan namin sa ngayon. 

Sila rin ay relatibong maliit. May hindi isang pulutong ng dagdag na espasyo. Itakda mo lang tabi mismo ng tulad sa marami bilang na kailangan mo upang i-hold ang iyong data, at iyon ang medyo marami ito. Kaya ito ay medyo maliit at mahusay na paraan. Ngunit ang isa pang downside, bagaman, ay na sila ay naayos na sa laki. Mayroon kaming upang magpahayag nang eksakto kung paano malaking gusto namin ang aming array na, at lamang kami makakuha ng isa pagbaril sa ito. Hindi namin maaaring maging at pag-urong ito. 

Kung kailangan namin sa paglaki o pag-urong ito, kami kailangan na idedeklara ng isang buong bagong array, kopyahin ang lahat ng mga elemento ng unang array sa ikalawang array. At kung miscalculated namin na time, kailangan namin upang gawin itong muli. Hindi kaya malaki. Kaya array ay hindi magbibigay sa amin ng kakayahang umangkop sa may variable na numero ng mga elemento. 

Sa pamamagitan ng isang listahan ng mga link, insertion ay medyo madali. Tak lang namin papunta sa harap. Pagbura ay din medyo madali. Mayroon kaming upang mahanap ang mga elemento. Na may kasangkot ang ilang mga paghahanap. 

Ngunit sa sandaling iyong natagpuan ang elemento naghahanap ka ng, ang lahat ng kailangan mong gawin ay baguhin ang isang pointer, marahil dalawa kung mayroon kang isang naka-link list-- isang doble naka-link na listahan, rather-- at pagkatapos ay maaari mo lamang libre ang mga node. Hindi mo na kailangang i-shift ang lahat ng bagay sa paligid. Baguhin mo lamang ng dalawang mga payo, kaya na medyo mabilis. 

Lookup ay masama bagaman, right? Sa order para sa amin upang makahanap ng isang sangkap sa isang listahan ng mga link, kung isa-isa o doble-link, kami ay may sa linear paghahanap na ito. Mayroon kaming upang magsimula sa simula at ilipat sa dulo, o magsimula sa dulo ilipat sa simula. Wala kaming anymore random access. Kaya kung anong ginagawa namin sa isang pulutong ng mga paghahanap, marahil isang listahan ng mga link na ito ay hindi lubos na mabuti para sa amin. 

Ang mga ito ay din tunay mahirap upang ayusin, i-right? Ang tanging paraan na maaari mong talagang ayusin ang isang listahan ng mga link ay upang ayusin ito bilang ka bumuo ng mga ito. Ngunit kung ayusin mo ito bilang ka tayuan ito, ikaw ay hindi na paggawa ng mabilis na mga pagpapasok anymore. Hindi ka lamang tacking mga bagay-bagay papunta sa harap. Mayroon kang upang mahanap ang tamang lugar upang ilagay ito, at pagkatapos ang iyong insertion nagiging lamang tungkol sa bilang masamang ng pagpasok sa isang array. Kaya naka-link na listahan ay hindi kaya malaki para sa pagbubukod-bukod ng data. 

Sila rin ay medyo maliit, laki-matalino. Doble link listahan bahagyang mas malaki kaysa sa isa-isa na naka-link na listahan, na kung saan ay bahagyang mas malaki kaysa sa array, ngunit ito ay hindi isang malaking halaga ng nasayang na espasyo. Kaya kung space ay sa isang premium, ngunit hindi isang tunay malubha premium, maaaring ito ang tamang paraan upang pumunta. 

Hash talahanayan. Insertion sa isang hash table ay medyo tapat. Ito ay isang prosesong may dalawang hakbang. Unang kailangan namin upang patakbuhin ang aming data sa pamamagitan ng isang hash upang makakuha ng isang hash code, at pagkatapos ay ipasok namin ang elemento sa hash table sa na lokasyon hash code. 

Pagbura, katulad ng sa listahan ng mga link, ay madali sa sandaling mahanap mo ang element. Mayroon kang upang mahanap muna ito, ngunit pagkatapos ay kapag tinanggal mo ang mga ito, ikaw lang ang kailangan upang makipagpalitan ng isang pares ng mga payo, kung gumagamit ka ng hiwalay na chaining. Kung gumagamit ka ng probing, o kung ikaw ay hindi gamit ang pagdudugtong sa lahat sa iyong talahanayan ng hash, pagtanggal ay aktwal na talagang madali. Ang kailangan mo lang gawin ay sirain ang data, at pagkatapos ay pumunta sa lokasyon na iyon. At sa pag-aakala na hindi mo walang anumang mga banggaan, Makikita mo na tanggalin nang masyadong mabilis. 

Ngayon, lookup ay kung saan bagay makakuha ng isang maliit na mas kumplikado. Ito ay sa average na mas mahusay kaysa sa naka-link na mga listahan. Kung gumagamit ka ng chaining, ikaw pa rin magkaroon ng isang listahan ng mga link, na nangangahulugan na ikaw pa rin ang search ay kapinsalaan sa isang naka-link na listahan. Ngunit dahil ikaw ay pagkuha ng iyong naka-link listahan at malakas ito sa higit sa 100 o 1,000 o n elemento sa iyong talahanayan ng hash, ikaw ay naka-link na listahan ay ang lahat ng isa nth ang laki. Ang mga ito ang lahat ng malaki mas maliit. N mong nai-link na listahan sa halip ng isang naka-link na listahan ng mga laki n. 

At kaya ito real-world constant kadahilanan, na kung saan kami ang karaniwang huwag makipag-usap tungkol sa oras kumplikado, ito ang tunay na gumawa ng isang pagkakaiba dito. Kaya lookup ay pa rin linear hanapin kung gumagamit ka ng chaining, ngunit ang haba ng listahan ikaw ay naghahanap sa pamamagitan ng ay napaka, napaka-ikling pamamagitan ng paghahambing. Muli, kung pag-uuri ay ang iyong layunin dito, hash talahanayan marahil hindi ang tamang paraan upang pumunta. Gamitin lang ang isang array kung pag-uuri ang tunay na mahalaga sa iyo. 

At maaari silang tumakbo ang gamut ng laki. Ito ay mahirap na sabihin kung ang isang hash table ay maliit o malaki, dahil talagang ito ay depende sa kung paano malaki ang iyong mga talahanayan hash ay. Kung ikaw lamang ang pagpunta sa pag-iimbak limang mga sangkap sa iyong talahanayan ng hash, at mayroon kang isang hash table na may 10,000 na mga elemento sa loob nito, marahil ikaw ay pag-aaksaya ng maraming espasyo. Ihambing ang pagiging maaari mo ring may tunay compact hash talahanayan, ngunit ang makakakuha ng mas maliit na ang iyong talahanayan hash, ang mga na ang bawat isa sa mga naka-link na mga listahan makakakuha. At kaya may tunay na walang paraan upang tukuyin ang eksakto ang laki ng isang hash table, ngunit ito ay maaring ligtas upang sabihin ito ay sa pangkalahatan magiging mas malaki kaysa sa isang naka-link listahan sa pag-iimbak ng parehong data, ngunit mas maliit kaysa sa isang trie. 

At pagsusubok ay ang ika-apat na ng mga kaayusan na pakikipag-usap namin tungkol sa. Pagpasok sa isang trie ay mahirap unawain. May isang pulutong ng mga dynamic memory laang-gugulin, lalo na sa simula, bilang ikaw ay simula upang bumuo. Ngunit ito ay pare-pareho ang panahon. Ito ay ang mga sangkap ng tao lamang dito na ginagawang mas mahirap hawakan. Ang pagkakaroon upang makaharap null pointer, malloc space, pumunta doon, posibleng malloc espasyo mula doon muli. Ang uri ng pananakot kadahilanan ng payo sa mga dynamic na memory laang-gugulin ang sagabal sa malinaw. Ngunit sa sandaling iyong na-clear ito, insertion talaga pagdating medyo simple, at tiyak na ito ay pare-pareho ang panahon. 

Pagbura ay madali. Ang kailangan mo lang gawin ay mag-navigate sa pababa ng pares ng mga payo at libre ang mga node, kaya na medyo magandang. Lookup ay medyo mabilis din. Ito ay batay lamang sa mga haba ng iyong data. Kaya kung ang lahat ng iyong data ay limang string ng character, halimbawa, ikaw ay nag-iimbak ng limang karakter string sa iyong trie, ito ay tatagal lamang ng limang mga hakbang upang mahanap kung ano ang iyong hinahanap. Five ay lamang ng isang pare-pareho na kadahilanan, sa gayon muli, insertion, pagtanggal, at lookup narito ang lahat ng pare-pareho ang oras, mabisa. 

Isa pang bagay ay na ang iyong trie ay tunay na uri ng na pinagsunod-sunod, di ba? Sa pamamagitan ng kabutihan ng kung paano namin hindi pagpasok elemento, sa pamamagitan ng pagpunta sulat sa pamamagitan ng sulat ng key, o digit sa pamamagitan ng digit ng key, kadalasan, nagtatapos up ang iyong trie pagiging uri ng pinagsunod-sunod habang binubuo mo ang mga ito. Ito ay hindi talagang gumagawa ng kahulugan upang isipin ang tungkol sa pag-uuri sa parehong paraan na sa tingin namin tungkol ito sa array, o naka-link na listahan, o hash talahanayan. Ngunit sa ilang mga kahulugan, ang iyong trie ay inayos bilang ka pumunta. 

Downside, siyempre, ay na mabilis na nagiging malaking isang trie. Mula sa bawat kantong point, maaari ka have-- kung ang iyong key ay binubuo ng mga numero, ikaw ay may 10 iba pang mga lugar na maaari kang pumunta, na ay nangangahulugan na ang bawat node naglalaman ng impormasyon tungkol sa mga data na nais mong i-store sa na node, kasama ang 10 mga payo. Kung saan, sa CS50 IDE, ay 80 bytes. Kaya ito ay hindi bababa sa 80 bytes para ang bawat node na iyong nilikha, at na hindi kahit na bilangin data. At kung ang iyong nodes ay mga titik sa halip ng mga numero, ngayon ikaw ay may 26 mga payo mula sa bawat lokasyon. At 26 beses 8 ay marahil 200 bytes, o isang bagay na tulad ng. At mayroon kang capital at lowercase-- mo maaaring makita kung saan ako pupunta sa mga ito, right? Ang iyong nodes ay maaaring makakuha ng talagang malaki, at sa gayon ang trie mismo, sa pangkalahatan, maaari makakuha ng talagang malaki, masyadong. Kaya kung ang lugar ay sa isang mataas na premium sa iyong sistema, maaaring hindi ang karapatan na paraan upang ang isang trie pumunta, kahit na ang iba pang mga benepisyo dumating sa play. Ako Doug Lloyd. Ito ay CS50.