Doug LLOYD: Tako je u CS50 smo pokriveni puno različitih struktura podataka, zar ne? Vidjeli smo polja i povezane liste, i hash tablice, i napad, masa i redova. Također ćemo naučiti nešto o drveću i hrpe, ali stvarno to sve samo kraj gore bitak varijacije na temu. Tu stvarno su ovi vrsta četiri osnovna ideja da je sve ostalo može svesti na. Polja, povezani popisi, hash tablice, i napad. I kao što sam rekao, ne postoji su varijacije na njih, ali to je prilično koliko će sažeti sve ćemo razgovarati o tome u ovom razredu u odnosu na C. Ali kako to oni sve mjere gore, zar ne? Razgovarali smo o pro i kontra svakog u zasebne videa na njih, ali ima puno brojeva dobivanje bačena okolo. Postoji mnogo općenito misli dobivanje bačena okolo. Pokušajmo i učvrstiti je na jednom mjestu. Idemo vagati prednosti protiv kontra, i uzeti u obzir koja struktura podataka bi mogao biti pravi podaci Struktura za Vašu situaciju, bez obzira na vrstu podataka ste pohranu. Vi ne moraju uvijek treba koristite super brzi umetanja, brisanja, i pretraživanja od Trie ako stvarno ne brinuti se o umetanje i brisanje previše. Ako vam je potrebna samo brzo slučajnim pristup, možda niz je bolje. Tako ćemo destilirati to. Razgovarajmo o svakom od četiri glavne vrste struktura podataka da smo razgovarali o tome, i samo vidjeti kad bi moglo biti dobro, a kad oni ne bi mogli biti tako dobri. Tako ćemo početi s polja. Dakle umetanje, to je vrsta loše. 

Umetanje na kraju niza je u redu, ako gradimo niz kako idemo. Ali ako moramo umetnuti elemente u sredini, mislim natrag na umetanje vrsta, tu je mnogo prebacivanja da stane element tamo. I tako, ako ćemo umetnuti nigdje, ali kraj niza, to vjerojatno nije tako velika. 

Slično tome, brisanje, osim ako smo brisanje s kraja niza, vjerojatno i nije tako velik ako ne želimo ostaviti prazne praznine, što obično nemamo. Želimo ukloniti element i onda nekako bi ga opet lagodan. I tako brisanje elemenata iz niz, također nije tako velika. 

Potraži, iako je super. Imamo slučajni pristup, vremenska konstanta pretraživanja. Mi samo reći sedam, a idemo na polja preseljenja sedam. Kažemo 20, s pokretu na Niz preseljenje 20. Mi ne moramo ponoviti preko. To je vrlo dobro. 

Nizovi su također relativno lako riješiti. Svaki put kad smo razgovarali o sortiranjem algoritam, kao što su odabir vrste, umetanje vrsta, mjehurić sortirati, spajanje vrsta, uvijek koristiti nizove to učiniti, jer polja su prilično lako vrsta, u odnosu na strukture podataka smo do sada vidjeli. 

Oni su također relativno mali. Nema puno dodatnog prostora. Vi samo staviti na stranu točno koliko što vam je potrebno da držite svoje podatke, i to je prilično zadovoljni. Dakle, oni su prilično male i učinkovito na taj način. Ali još jedna mana, ipak, da su fiksne veličine. Moramo proglasiti točno kako Veliki želimo da naša niz biti, a mi samo dobiti jedan metak u njega. Ne možemo rasti i smanjiti. 

Ako trebamo rasti ili ga smanjiti, mi morati proglasiti posve novi niz, kopirati sve elemente Prvi niz u drugi niz. A ako smo pogrešno da vrijeme, moramo to učiniti opet. Ne tako velika. Dakle polja ne daju nam fleksibilnost da ima varijabilnu broj elemenata. 

S popisa povezani, umetanje je prilično jednostavan. Upravo smo sklepati na pročelju. Brisanje je prilično jednostavan. Moramo pronaći elemente. To uključuje neki koji traži. 

No, nakon što ste pronašli element tražiš, sve što trebate učiniti je promijeniti pokazivač, eventualno dva ako imate je povezani list-- dvostrano povezana lista, rather-- a onda možete samo osloboditi čvor. Ne morate da pomak sve oko. Vi samo promijeniti dva pokazivača, tako da je prilično brzo. 

Potraži je loše ipak, zar ne? Da bi nam je pronaći element u popisu povezane, bilo pojedinačno ili dvostruko povezani, moramo linearno ga traži. Moramo početi na početku i premjestiti kraj ili početak na kraju pokretu na početak. Nemamo slučajni pristup više. Dakle, ako mi radite puno traženja, možda popis povezana nije toliko dobro za nas. 

Oni su također jako teško sortiranje, zar ne? Jedini način možete stvarno sortirati popis povezan je to riješiti onako kako ga izgraditi. Ali ako to riješiti kao ti izgraditi ga, ti si više ne izradu brzih umetanja više. Vi ne samo letanja stvari na prednji. Morate pronaći Pravo mjesto za staviti, a zatim vaš umetanje postaje samo o loše kao umetanja u nizu. Tako povezani popisi nisu pa super za sortiranje podataka. 

Oni su također prilično male, veličina mudar. Dvostruko povezane liste malo veći od pojedinačno povezanim popisima, koji su nešto veći od polja, ali to nije ogromna količina izgubljenog prostora. Dakle, ako je prostor na premiju, ali ne stvarno intenzivno premija, to može biti pravi način da ide. 

Hash tablice. Ubacivanje u hash tablici je prilično jednostavan. To je proces u dva koraka. Prvo moramo pokrenuti naše podatke preko hash funkcija dobiti hash kod, a onda smo umetnuti element u hash tablicu na toj lokaciji hash code. 

Brisanje, slično povezane liste, je jednostavno jednom kad pronađete element. Morate pronaći prvi, ali onda kada ga izbrisati, vi samo trebate zamijeniti par pokazivača, ako koristite zasebnu ulančavanje. Ako koristite sondiranja, ili ako niste pomoću ulančavanje na sve u svom hash tablici, brisanje je zapravo jako jednostavno. Sve što trebate učiniti je hash podataka, a zatim idite na tom mjestu. I uz pretpostavku da ne imati bilo sudara, ćete biti u mogućnosti to izbrisati vrlo brzo. 

Sada, pretraživanje je mjesto gdje stvari dobiti malo više komplicirano. To je u prosjeku bolje od povezanih liste. Ako koristite ulančavanje, još uvijek imate popis povezani, što znači da još uvijek imaju traži štetu popis povezane. Ali zato ste uzimajući vaše povezani popis i podijelite preko 100 ili 1000 ili n elementi u vašem hash tablici, ti si vezane liste su svi jedno NTH veličini. Svi su znatno manji. Vi nje su povezane liste umjesto jednog povezanog popisa veličine n. 

I tako konstantno to u stvarnom svijetu faktor, koji mi općenito Ne govorimo o složenosti vrijeme to, ne zapravo čine razliku ovdje. Tako je još uvijek linearno pretraživanje Pretražite ako koristite ulančavanje, a duljina popisa ste u potrazi kroz vrlo, vrlo kratko u usporedbi. Opet, ako je vaš sortiranje cilj ovdje, hash tablicu a vjerojatno nije pravi način da ide. Dovoljno je koristiti niz ako sortiranje stvarno važno za vas. 

I oni mogu pokrenuti skala veličine. Teško je reći je li hash tablica je mala ili velika, jer to stvarno ovisi o koliko je velika vaša hash tablica. Ako ste samo ide da se pohrane pet elemenata u vašem hash tablici, i imate hash tablicu s 10.000 elemenata u njemu, vjerojatno ste gubit puno prostora. Kontrast vam se može imaju vrlo kompaktnih hash tablice, ali manji vaše hash tablicu dobiva, duže svaki od tih povezanih popisa dobiva. I tako da stvarno nema načina za definiranje upravo veličina hash tablici, ali to je vjerojatno sigurno reći da je općenito će biti veća nego povezani Popis spremanje istih podataka, ali manji od Trie. 

I napad su četvrti Navedene konstrukcije da smo razgovarali o tome. Umetanje u Trie je složen. Postoji mnogo dinamički dodjela memorije, pogotovo na početku, kao što ste počeli graditi. Ali to je konstanta vrijeme. To je samo ljudski element ovdje, što ga čini zahtjevno. Imajući u susret null pointer, malloc prostor, tamo, možda malloc prostor od tamo opet. Vrsta zastrašivanja faktor upućuje na dinamičke dodjele memorije je zapreka za brisanje. No, nakon što ste ga izbrisani, umetanje zapravo dolazi vrlo jednostavna, i sigurno je konstanta vrijeme. 

Brisanje je jednostavno. Sve što trebate učiniti je ploviti dolje Nekoliko upućuje i slobodnog čvora, tako da je vrlo dobro. Potraži je također prilično brzo. Ona se temelji samo na duljina podataka. Dakle, ako sve svoje podatke je pet nizova znakova, na primjer, da ste spremanje pet niz znakova u vašem Trie, to traje samo pet koraka do pronaći ono što tražite. Pet je samo konstantan faktor, tako da opet, umetanje, brisanje i pretraživanje ovdje su svi vremenska konstanta, učinkovito. 

Druga stvar je da je vaš Trie je zapravo vrsta već razvrstani, zar ne? Zahvaljujući tome smo umetanje elemenata, odlaskom slovo po slovo Ključ ili znamenku po znamenku ključa, obično, vaš Trie završi kao vrsta razvrstani kao što ste ga graditi. To zapravo ne čini smisla razmišljati o razvrstavanju na isti način na koji mislimo o to s polja, ili povezanim popisima, ili hash tablice. No, u nekom smislu, vaše Trie je razvrstani kao i ti ići. 

Loša strana je, naravno, da je Trie brzo postaje ogromna. Iz svakog čvorište, možda have-- ako vaš ključ sastoji od brojki, imate 10 drugi mjesta možete ići, što znači da je svaki čvor sadržava podatke o podacima želite pohraniti u tom čvoru, plus 10 pokazivače. Koji, na CS50 IDE, 80 bajtova. Tako da je najmanje 80 bajtova za svaki čvor koji ste stvorili, i da nije ni računajući podatke. I ako tvoji čvorovi slova umjesto brojki, Sada imate 26 pokazivače iz svakog mjesta. A 26 puta 8 je vjerojatno 200 bajtova, ili nešto slično. A imate kapital i ti lowercase-- može vidjeti gdje idem s ovim, zar ne? Vaša čvorovi mogu dobiti stvarno velika, pa je Trie Sama, u ukupnom poretku, može dobili stvarno velik, previše. Dakle, ako je prostor na visokoj Premija na vašem sustavu, Trie možda nije pravi način da se ići, iako drugih prednosti dolaze u igru. Ja sam Doug Lloyd. Ovo je CS50.