>> DAVID Malan: Të gjithë të drejtë.
Mirë se vini përsëri në CS50.
Ky është fillimi i javës së 8.
Dhe kujtojnë se problemi set 5 përfundoi me pak e një sfidë.
Pra, duke supozuar që ju të mbulohen të gjithë tuaj Fellows mësimdhënies dhe fotografitë e AK-së
në dosjen card.raw, ju jeni të drejtë për të gjetur tani të gjithë atyre njerëzve, dhe
një fitues me fat do të ecin në shtëpi me një prej këtyre gjërave, mocioni brishtë
pajisje që ju mund të përdorni për finale Projektet, për shembull.
>> Kjo, çdo vit, të çon në pak e creepiness.
Dhe kështu ajo që kam menduar unë do të bëj është pjesa me ty disa nga shënimet që kanë
shkuar mbrapa dhe me radhë mbi lista stafi i vonë.
Për shembull, vetëm natën e kaluar kuotë, quajtur ato, prej njërit prej te personeli
anëtarë, "Unë vetëm kishte një trokitje studentore në derën time për të marrë një foto me mua.
Vertetes, unë po ju them ". Filloi mjaft përshkrues dhe pastaj ne lëvizëm
mbi të, një orë apo më shumë më vonë, "Kam një Studenti duke pritur për mua pas seksionit
dhe ai kishte të gjithë emrat tanë dhe fotot në disa fletë të letrës. "të gjithë të drejtë.
Pra organizuar, por jo gjithçka që mërzitur ende.
>> Pastaj, "Unë isha jashtë qytetit këtë fundjavë, dhe kur kam marrë përsëri, pati një në
tim
. gjumi "[Qeshura]
DAVID Malan: Next citim nga një staf anëtar, "erdhi një student në shtëpinë time në
Somerville në orën 4 këtë mëngjes. "Next Stafi, "mori unë në hotelin tim në San
Francisco dhe një student është duke pritur për mua në hollin me tre DSLRs. "
Lloji i kameras.
"Unë nuk jam edhe në stafin këtë semestër, por një student hynë në shtëpinë time këtë
mëngjes dhe regjistruar të gjithë gjë me xham Google. "Dhe pastaj së fundi,
"Të paktën 12 njerëz ishin padurim në pritje për mua kur dola nga tim
limo, dhe pastaj unë
u zgjova. "Të gjithë të drejtë.
Pra, në mesin e fotografive, si ju mund të kujtojnë, janë ky shoku këtu, të cilët ju
mund të dinë si banane Milo, i cili jeton me Lauren Carvalho, kokën tonë
mësimdhënies anëtar.
Milo, Milo, vijnë këtu djalosh.
Milo.
Mind you, ai është i veshur me Google qelqi, në mënyrë ne do të ju tregojnë të gjithë këtë pas.
Pra, kjo është Milo në qoftë se ju do të donte për të të marrë një fotografi me vete pas.
Nëse ju dëshironi të shikoni jashtë në audiencë atje.
OK.
Kjo është pamjet e mirë.
E pra, Milo banane.
Oh, nuk e bëjmë këtë.
>> [Qeshura]
>> OK.
Pra, me një fjalë pastaj në çfarë shtrihet përpara, sepse si ne të fillojnë të tranzicionit,
këtë javë në mënyrë specifike, nga C në një command line mjedisit në PHP dhe
Dhe SQL JavaScript dhe HTML dhe CSS në një web-bazuar mjedis, ne do të jetë
pajisjen me të gjitha më shumë njohuri për
projekte të mundshme përfundimtare.
Drejt këtij qëllimi, ka një kurs Tradita e mbajtjes së seminareve të cilat
janë mbi tema tangjencial të rrjedhës.
Shumë të lidhura me programimin dhe për të zhvillimit app dhe kështu me radhë, por
nuk hulumtohen domosdoshmërisht nga syllabus vetë rrjedhës së.
>> Pra, nëse ju mund të jenë të interesuar në njërën ose më shumë prej seminareve këtij viti,
regjistrohen në cs50.net/seminar.
Ka seminare të vjetra në cs50.net/seminars.
Dhe kështu në listën e largët për këtë vit janë Apps Amazing Web me Ruby on
Binarët, e cila është një alternativë gjuhë të PHP.
Gjuhësi kompjuterike.
Futja te iOS, e cila është platformë që është përdorur për iPhone dhe
Zhvillimi i iPad.
JavaScript për Apps Web, ne do të mbulojë se, por në këtë seminar, ju do të shkoni
në më shumë detaje.
>> Brishtë lëvizje, kështu që ne do të vërtetë kanë disa nga miqtë tanë nga Motion brishtë,
Kompania vetë, të na bashkohen.
Nesër, në fakt, për të siguruar një duart-në seminar, qoftë
me interes për ju.
Meteor.js, një teknikë alternativë për duke përdorur JavaScript jo ne nje shfletues,
por në një server.
Node.js, e cila është shumë e në atë mënyrë si edhe.
Sleek Dizajn Android.
Android qenit një alternativë shumë të popullarizuara për iOS dhe Windows Phone
dhe platforma të tjera të lëvizshme.
Dhe Mbrojtjes Web Sigurimit ne forum.
>> Pra, në fakt, në qoftë se ju do të donte për t'u angazhuar në këtë, më lejoni të
të bëjë shënimin e kësaj.
Ne jemi shumë të lumtur të them se miqtë tanë në kërcim
Lëvizje, e cila është një fillimin -
kjo pajisje me të vërtetë sapo erdhi nga disa muaj më parë -
ka dhuruar mirësjellje 30 pajisje të tilla në klasë për sa më shumë studentë, nëse
ju dëshironi për të marrë hua hardware drejt përfundimit semestrin dhe e përdorin atë për
një projekt përfundimtar aktuale.
Ato mbështesin një numër të gjuhëve.
Asnjë prej tyre C, asnjëri prej tyre nuk PHP, në mënyrë realizojnë një ose më shumë prej këtyre seminareve
mund të provojë të interesit.
Dhe të gjithë prej tyre do të filmohet në Ngjarja që ju nuk jeni në gjendje
për të marrë pjesë në person.
Orari të shpallet nëpërmjet email si ne ngrij dhoma.
>> Dhe së fundi, në qoftë se ju shkoni në projects.cs.50.net, kjo është një website
ne ruajtjen e çdo vit që ne ftojmë folks nga komuniteti, fakultetit,
departamentet, stafi, dhe të dyja në një jashtë CS50 ndaj
propozojnë ide të projektit.
Gjërat e interesit ndaj grupeve studentore.
Gjërat në interes të departamenteve.
Pra, do të kthehet atje, nëse ju jeni duke luftuar me pasiguri si në atë që ju
veten do të donte për të trajtuar.
>> Pra, koha e kaluar ne kemi prezantuar një ndoshta Të dhënat struktura më komplekse sesa ne do
shihet në javët e fundit.
Ne do të qenë goxha e vargjeve duke përdorur për fat të mirë, si një e dobishme nëse
simplistic dhënat strukturë.
Pastaj ne kemi prezantuar këto, të cilat sigurisht janë të lidhura listat.
Dhe çfarë ishte një nga motivet për futjen e këtij strukturën e të dhënave?
Po?
Çfarë është ajo?
>> Audienca: Madhësia Dinamik.
>> DAVID Malan: Madhësia Dinamik.
Pra, ndërsa në rrjet, ju duhet të e di madhësinë e saj më parë kur
ju ndajë atë.
Në listën e lidhur, ju nuk e bëni duhet ta dini se.
Ju vetëm mund të malloc, ose më në përgjithësi, akordojë një shtesë
nyje, kështu që të flasin, çdo herë që doni të futur më shumë të dhëna.
Dhe nyja e ka paracaktuar asnjë kuptim.
Kjo është vetëm një term gjenerik përshkruar disa lloj enë që ne jemi
përdorur në strukturën tonë të të dhënave për të ruajtur disa pika të interesit, e cila në këtë
Rasti ndodhë që të jetë integers.
>> Por ka gjithmonë një kompromis.
Pra, ne të merrni madhësive dinamike e të dhënave Struktura, por nuk kemi çfarë çmimi paguajnë?
Çfarë është downside i listave të lidhura?
Po?
>> Audienca: Kërkon më shumë memorie.
>> DAVID Malan: Kjo kërkon më shumë kujtesës, si saktësisht?
>> Audienca: [padëgjueshme].
>> DAVID Malan: Pikërisht.
Pra, tani ne kemi marrë deri pointers memorie shtesë që ne më parë
nuk ka nevojë, sepse avantazh nga një grup, sigurisht, është se
çdo gjë është e puqur, mbrapa te mbështetur te pasme, e cila
ju jep juve akses të rastit.
Sepse vetëm duke përdorur kllapa katrore simbol, ose më teknikisht pointer
aritmetike, shtesë shumë e thjeshtë, ju mund të hyni në ndonjë
elemente në kohë konstante.
Dhe në fakt, kjo është lloj i nënkuptuar në një tjetër çmim që ne jemi duke paguar me një
lista e lidhura.
>> Çfarë ndodh në kohën drejtimin e diçka si Search, nëse unë dua të
gjeni disa vlera dhe brenda i një liste të lidhur?
Çfarë koha ime kandidon të bëhet?
Madhe O i n.
Nëse është e renditura për të?
Çfarë ndodh nëse struktura e të dhënave të renditura?
Mund të bëj më mirë se madhe O i n per kërkimin?
Jo, sepse në rastin më të keq ajo mund shumë mirë të zgjidhet, por numri
ju jeni në kërkim për të mund të jetë i madh.
Ajo mund të jetë numri 100, i cili mund të ndodhë që të jetë mbi të gjitha
Mënyra më në fund.
Dhe për shkak se ju mund të hyni vetëm një linked Lista në këtë zbatim nga
Mënyra e nyjeve të saj të parë, ju jeni ende lloji i nga fat.
Ju duhet të kaloj nëpër gjithë gjë nga e para për të kaluar në mënyrë që të gjeni
se vlera e madhe si 100.
Ose për të përcaktuar nëse është e jo edhe atje.
>> Pra, ne nuk mund të bëjë atë në një algoritëm të dhënave strukturë që duket si ky?
Ne nuk mund të bëni kërkimin binar, sepse kërko binar kërkohet që kemi pasur
qasje të rastit.
Ne vetëm mund të brishtë nga lokacioni në vend pa pasur nevojë për të ndjekur
këto crumbs bukë në formë të gjitha këto pointers.
>> Tani, si e kemi zbatuar këtë?
E pra, në qoftë se ne të shkuar tek ekrani këtu, në qoftë se ne mund të shpejt reimplement këto të dhëna
Struktura -
dorëshkrimit ime nuk është e gjitha që e madhe këtu, por ne do të përpiqemi.
Struct typedef Pra, çfarë bëri dhe unë doni të telefononi këtë gjë deri këtu?
Nyja.
Kështu që unë do të na marrë filluar.
Dhe tani, ajo ka nevojë të jetë brenda Struktura e të dhënave për këtë formë individuale
të lidhura listë?
Sa shumë fusha?
>> Pra dy.
Njëra është mjaft e lehtë.
Pra, int n.
Dhe ne mund të telefononi asgjë n ne duam, por ajo duhet të jetë një int qoftë se ne jemi
zbatimin e një listë e lidhur për ints.
Dhe tani çfarë bën dytë fushë duhet të jetë?
Struct nyje *.
Pra, nëse unë bëj struct nyje *, dhe atëherë unë Kjo gjithashtu mund të telefononi çdo gjë që unë dua,
por vetëm të jetë i qartë unë do të thërrasë ajo ardhshëm, siç kemi qenë duke bërë.
Dhe atëherë unë do të mbyll e mia formatimin e teksteve kaçurrel.
>> Dhe tani, si kohë e kaluar, I vënë nyje këtu poshtë.
Por në qoftë se unë jam deklaruar kjo është si një nyje, pse nuk kam qenë aq mërzit
fjalëshumë këtu në shpalljen struct * nyjen e ardhshëm, në krahasim
* të vetëm nyjen e ardhshëm?
Po?
>> Audienca: [padëgjueshme].
>> DAVID Malan: Pikërisht.
Saktësisht.
Sepse C vërtetë ju merr fjalë për fjalë dhe sheh vetëm përkufizimin e nyjes
Mënyra më poshtë këtu, ju nuk mund të referohen atë deri këtu.
Pra, ne kemi këtë lloj të përparësisë Deklarata këtu, e cila është pa dyshim
më shumë fjalëshumë.
Struct nyje, që do të thotë ne tani mund të hyni në atë
brendësi të strukturës dhënave.
>> Dhe si një mënjanë, sepse kjo është duke u bërë një pak më shumë subjektive tani,
yll teknikisht mund të shkoni këtu, ajo mund të shkoni këtu, ajo mund të
shkojnë edhe në mes.
Ne kemi miratuar, në stil udhëzues për kurs, konventë e vënë
yll të drejtë tjetër të të dhënave lloji, e cila në këtë rast,
do të jetë nyje struct.
Por të kuptojë në një shumë të teksteve dhe referencat online, ju mund të vërtetë
shohin atë në anën tjetër.
Por vetëm të kuptojë se të dy të vërtetë do të punoni dhe ju duhet të jetë thjesht
konsistente.
>> Dakord.
Kështu që ishte shpallja jonë e nyjeve struct.
Por pastaj kemi filluar duke bërë më shumë gjëra të sofistikuara.
Për shembull, ne kemi vendosur për të futur diçka si një tabelë hash.
Kështu që këtu është një tabelë hash të n madhësisë, indeksuar nga 0 në krye të majtë të n
minus 1 në pjesën e poshtme të majtë.
Kjo mund të jetë një hash Tabela për asgjë.
Por ajo që llojet e gjërave nuk flasim lidhje me përdorimin e një tabelë hash për të?
Ruajtjen çfarë?
>> Emra.
Ne mund të bëjmë emra si ne e bëmë herën e fundit.
Dhe me të vërtetë, ju mund të ruajë asgjë.
Dhe ne do të shohim këtë përsëri në PHP dhe në JavaScript.
Një tabelë hash është një lloj e bukur zvicerane Thikë Ushtria që ju lejon për të ruajtur
pretty much çdo gjë që ju dëshironi në brendësi të ajo me shoqërimin me çelësat vlerave.
Keys me vlera.
>> Tani, në këtë rast të thjeshtë, tonë Çelësat janë vetëm numra.
Ne jemi duke zbatuar një hash Tabela si një rrjet.
Dhe kështu çelësat janë 0, 1, 2, dhe kështu me radhë.
Dhe kështu që ne, si qenie njerëzore, vendosi fundit Javën që ju e dini se çfarë, në qoftë se ne jemi
shkuar në dyqan emrave, le të vetëm në mënyrë arbitrare, por mjaft të arsyeshme,
supozojmë se Alice, një Një emër, thjesht do të indeksohen në 0.
Dhe Bob, një emër B, do të indeksohen në 1, dhe kështu me radhë.
Pra, kemi pasur një hartë në mes të inputeve, cilat janë vargjet, dhe hash
vende, të cilat janë numra.
>> Kështu që procesi është i njohur përgjithësisht si një funksion hash, dhe ju mund të vërtetë
zbatojë atë në kodin.
Në qoftë se unë të kërkuar për të zbatuar një funksion hash që e bën pikërisht atë që ne
përshkruhet vetëm nga hera e fundit, unë mund deklarojë një funksion që merr, si
input për shembull -
dhe le ta bëjmë këtë në këtë Ekran mbi këtu.
Nëse unë të kërkuar për të implementuar një hash funksion, unë mund të them
diçka si kjo.
>> Ajo do të kthehet një int.
Ajo do të quhet hash, dhe kjo është do ta pranojnë si argument një
string, ose ne mund të jetë më e duhur tani, dhe thonë * char, ne do të thërrasë atë s.
Dhe pastaj gjithë ky funksion ka për të bërë, në fund të fundit, po kthehet një int.
Tani, si e bën atë që mund të mos jetë aq e qartë.
Unë jam duke shkuar për të zbatuar këtë pa ndonjë formojnë i gabimit kontrolluar tani.
Unë jam vetëm duke shkuar për të thonë verbërisht, kthehen çdo gjë që është në kllapa 0 s, minus,
le të themi, kryeqyteti pikëpresje.
>> Thyer tërësisht.
Kjo nuk është e përsosur, sepse një, çfarë nëse s është i pavlefshëm?
Gjëra të këqija do të ndodhë.
Dy, çfarë nëse shkronja e parë në këtë emri nuk është një letër kryeqyteti?
Kjo nuk do të kthehet qoftë edhe jashtë.
Ajo mund të jetë me shkronja të vogla apo jo një letër në të gjitha.
Pra krejtësisht vend për përmirësim këtu, por kjo është ideja themelore.
>> Ajo që ne e përshkroi javën e kaluar verbalisht si vetëm një proces i hartës për Alice
0 dhe Bob në 1 mund të shprehet siguri më formulaically si një C
funksionojnë këtu.
Bëri thirrje përsëri hash, merr një varg si input, dhe pastaj disi bën diçka
me atë input për të prodhuar një prodhim.
Jo ndryshe nga përshkrimi tonë kuti e zezë që ne kemi bërë gjatë.
Unë nuk e di se si kjo mund të jetë duke punuar nën kapuç.
>> Për set Problem 6, njëra nga sfidat është për ju të vendosni se çfarë
do të hash funksioni juaj të jetë?
Çfarë do të jetë brenda që e zezë kuti, dhe me sa duket, ajo do të jetë një
pak më shumë interesante se ky, dhe patjetër më të prirur për të gabimit
kontrolluar se kjo veçanti zbatimi.
>> Por problemet mund të lindin, e drejtë?
Në qoftë se ne kemi një strukturë të dhëna të tilla si kjo një, çfarë është një nga problemet
ju mund të kandidojë në kalimin e kohës si ju futur emrat e më shumë në
tabelë hash?
Ju merrni goditjet, e drejtë?
Çfarë nëse ju keni Alice dhe Aaronin, dy njerëz emrat e të cilëve ka ndodhur
për të filluar me A?
Kjo ngre pyetjen, ku ju vënë dytë një emër të tillë?
>> E pra, ju mund të vetëm vënë atë me naivitet Bob ku i takon, por pastaj është Bob
lloj i dehur nëse ju përpiqeni të shëno emrin e tij të ardhshëm dhe
nuk ka dhomë për të.
Kështu që ju mund të vënë Bob Charlie ku është, dhe ju mund të imagjinoni këtë shumë shpejt
delegimin në një grimë e një rrëmujë.
Diçka lineare në fund, ku ju vetëm duhet të kërkoni të gjithë gjë
kërkoni për Alice apo Bob ose Aaron apo Charlie.
>> Pra, në vend që kemi propozuar, në vend të vetëm linearisht probing për hapësira të hapura
dhe plopping emrat atje, ne propozoi një qasje njohës.
Një tabelë hash zbatuar ende me një array e indekseve, por tipi i të dhënave
Indekset ato tani ishin pointers.
Pointers për çfarë?
Pointers në listat e lidhura.
>> Sepse kujtojnë se është një listë e lidhur me të vërtetë vetëm një tregues për një nyje, dhe
nyjë ka një fushë tjetër, dhe se Nyja ka një fushë tjetër, dhe kështu me radhë.
Kështu që ju tani mund të mendoni për këtë grup në Ana e majtë e një tabelë hash si
duke çuar në listën e lidhur.
Avantazhi i cili është në qoftë se ju merrni një Përplasja mes Alice dhe Aaronit,
çfarë do të bëni me Personi i dytë i tillë?
Ju vetëm të bashkëngjitni atë apo të saj për të fundi, ose madje edhe fillimi
e atij listën e lidhur.
>> Dhe në të vërtetë, le të vetëm hajvan përmes se për vetëm një sekondë.
Ku do të bëjë më kuptim?
Nëse unë futur Alice dhe ajo përfundon deri në vendndodhja e parë, atëherë unë të përpiqet për të
insert emrin e Aaronit, dhe ka padyshim një përplasje, duhet të kam vënë
atë në fillim e listës së lidhur?
Kjo është në atë vend të parë, apo në fund?
>> Audienca: [padëgjueshme].
>> DAVID Malan: OK.
Kam dëgjuar fillimi.
Pse në fillim?
>> Audienca: [padëgjueshme].
>> DAVID Malan: OK.
Është alfabetike, kështu që është e bukur.
Kjo është një pronë e mirë.
Ajo do të shpëtojë mua disa kohë potencialisht.
Kjo nuk do të më lejoni të bëjë kërkimin binar, por unë mund të paktën të jetë në gjendje për të thyer jashtë
i një lak në qoftë se unë të kuptojë, mirë, unë jam rruga e kaluara ishin Aaroni do të jetë në këtë
renditura listën e lidhur.
Unë nuk duhet të humbim kohë e mia në kërkim të gjithë rrugën deri në fund.
Pra, kjo është e arsyeshme.
Pse tjetër që ju mund të dëshironi të futni Emri colliding në
fillimi i listës?
Çfarë është ajo?
>> Audienca: [padëgjueshme].
>> DAVID Malan: Ajo mund të marrë një kohë të gjatë për të marrë në fund të listës.
Dhe në fakt, më të gjatë dhe më të gjatë.
Emrat më shumë se ju futur fillojnë me A, më se
zinxhir është duke shkuar për të marrë.
Më gjatë që lidhet lista do të merrni.
Pra, ju jeni me të vërtetë vetëm humbur kohën tuaj.
Ndoshta ju jeni më të mirë jashtë ruajtur Ora konstante futje, Big O e 1,
gjithmonë duke vënë emrin në colliding fillimi i listës së lidhur,
dhe jo shqetësuese sa më shumë rreth klasifikim.
>> Cila është përgjigja më e mirë?
Është e paqartë.
Kjo lloj varet nga ajo shpërndarjes është, çfarë model është
e emrave që ju jeni futur.
Kjo nuk është domosdoshmërisht një përgjigje e qartë.
Por këtu për të, përsëri, është një mundësi të projektimit.
>> Pra, ne pastaj shikoi në këtë gjë, e cila është me të vërtetë mundësi të tjera të mëdha
për p-set 6.
Dhe të kuptojë, në qoftë se ju nuk e keni tashmë, Zamyla zhytet në të dyja këto, hash
tavolina dhe përpiqet, më në detaje.
Dhe walkthrough video është ngulitura në p-set spekulim.
Ky ishte një trie -
T-R-I-E. Dhe çfarë ishte interesante në lidhje me kjo ishte se koha running
të kërkojnë për një emër, si Maxwell Herën e fundit, ishte e madhe O çfarë?
Çfarë është ajo?
>> Audienca: Numri i letrave.
>> DAVID Malan: Numri i letrave.
Kam dëgjuar dy gjëra.
Numri i shkronjave dhe Konstanta kohore.
Pra, le të shkojë me se pari.
Numri i shkronjave.
E pra, kjo strukturë e të dhënave, risjell, është si një pemë, një pemë familjare, secili prej
nyjet e të cilëve janë bërë deri të vargjeve.
Dhe ato vargjeve janë pointers në nyjet e tjera të tilla, apo të tjera të tilla
vargjeve në pemë.
>> Pra, nëse ne të kërkuar për të pastaj të përcaktuar nëse Maxwell është këtu, unë mund të shkoj
të array parë, në krye të pemë, e ashtuquajtura rrënjë, të lartë e
trie, dhe pastaj ndiqni treguesin m, pastaj një akrep, atëherë x,
w, e, l, l.
Dhe atëherë kur unë shoh disa simbol të veçantë, pėrcaktuara këtu si një trekëndësh.
Në kodin e ju do të shihni që ne propozojmë që ju zbatohet si një bool, vetëm duke thënë se po
ose jo, një fjalë ndalet këtu.
>> E pra, pasi ne kemi shkuar në M-A-x-W-E-L-L, ndjehet si shtatë, ndoshta
tetë në qoftë se ne do të shkojmë një të kaluar, tetë hapa për të gjetur Maxwell.
Ose le të thërrasë atë K. Por kujtojnë fundit kohë, kam argumentuar se nëse ka
realisht një gjatësi maksimale në një Fjala, si 40-disa-rastësishëm personazhet, një
Gjatësia maksimale nënkupton një vlerë konstante.
Pra, me të vërtetë, po, kjo është teknikisht e madhe O i 8 ose 7, ose o të vërtetë të madh të K. Por
në qoftë se ka një kapak mbi atë fundme K mund të jetë, kjo është një konstante.
Dhe kështu kjo është e madhe O 1 në fundi i ditës.
>> Jo në botën reale.
Jo kur ju të vërtetë të filloni të shikuar clock tuaj si ekzekutoni programin tuaj.
Është absolutisht do të jetë pak ngadalshme se me të vërtetë konstante
herë me një hap.
Ajo do të jetë shtatë ose tetë hapa, por ende kjo është shumë, shumë më mirë
se një algoritmi si Big O n e asaj varet nga madhësia e asaj që është në
Struktura e të dhënave.
>> Njoftim kokë këtu është që ne mund të futni një milion emrat e më shumë në këtë
Struktura e të dhënave, por sa më shumë hapa ajo është duke shkuar për të na marrë për të gjetur
Maxwell në këtë rast?
Asnjë.
Ai është i sinqertë.
Dhe deri më sot, unë nuk mendoj se ne kemi parë një shembull i një strukture të dhënave ose të një
algorithm se ishte krejtësisht pandikuar nga të jashtëm
sjelljet si kjo.
Por kjo nuk mund të jetë e mahnitshme.
Kjo nuk mund të jetë zgjidhja e vetme për p-set
>> Dhe kjo nuk është.
Kjo nuk është domosdoshmërisht të dhënat Struktura ju duhet të bie për të,
sepse si tabelat hash, tradeoff.
Çfarë është çmimi që ju paguani këtu?
Memory.
Unë do të thotë, kjo është një atrocious shuma e kujtesës.
Dhe ju nuk mund të mjaft të shohin atë këtu, sepse Autori i këtij foto
cunguar padyshim të gjitha vargjeve, dhe ne nuk po shohim shumë e A-së dhe
B-së dhe C dhe Q-së dhe të Y dhe Z-së në këto vargjeve.
Por ata janë atje.
>> Secila prej këtyre nyjeve është një koleksion të tërë e disa 26 apo më shumë bytes, secili prej
e cila përfaqëson një letër.
27 në rastin tonë, kështu që ne mund të mbështesim apostrofat në setin problem.
Pra, kjo është me të vërtetë Struktura e të dhënave, të vërtetë të dendura dhe të gjerë.
Dhe kjo vetëm mund të përfundojnë ngadalësuar gjërat poshtë, ose të paktën të ju kushton një
hapësirë ​​shumë më tepër.
Por përsëri, ne mund të tërheqë krahasimet këtu.
>> Kujtojnë Një ndërsa mbrapa, ne kemi arritur shumë më shumë kohë emocionuese running në klasifikim
kur ne përdorim lloj bashkojë, por çmimi kemi paguar për të arritur n log n për bashkimin
lloj kërkohet që ne të shpenzojnë më shumë çfarë të burimeve?
Më shumë hapësirë.
Ne kishim nevojë për një rrjet të mesme të kopjoni njerëzit në, ashtu si
ne e bëmë këtu në skenë.
Pra, përsëri, asnjë fitues të qartë, por vetëm dizajn subjektive
vendimet për të bërë.
>> Dakord.
Pra, si në lidhje me këtë?
Çdokush që e njohin D-Hall?
OK.
Pra, tre prej nesh bëjnë.
Mather House.
Pra, kjo është për ngrënie Mather së.
Unë do bast të gjithë salla ngrënie të ketë oxhaqet e tabaka si kjo.
Dhe kjo është në të vërtetë përfaqësuesi i diçkaje që kemi
shihet qartë tashmë.
Ne e thirrëm atë fjalë për fjalë një pirg.
Dhe rafte, në aspektin e juaj memorie të kompjuterit, është ku të dhënat shkon
ndërsa funksione janë duke u quajtur.
>> Për shembull, çfarë lloje të gjëra shkojnë në rafte në lidhje me
Paraqitjen e kujtesës kemi diskutuar në javët e fundit?
Çfarë është ajo?
>> Audienca: Thirrje ndaj funksioneve.
>> DAVID Malan: Unë jam i keq.
>> Audienca: Thirrje ndaj funksioneve.
>> DAVID Malan: Telefonata me funksione, por konkretisht, çfarë është brenda secilit prej
ato korniza?
Cilat llojet e gjërave?
Po.
Pra, variablat lokale.
Çdoherë që ne kemi nevojë për disa ruajtje lokale, si një argument, apo int unë, apo int
temp, ose çfarëdo lokale variabël është, ne kemi qenë
vënien se ne pirg.
Dhe ne e quajmë atë një pirg, sepse i kësaj ideje layering.
Vetëm lloj ndeshjeve deri me realitetin, konceptit tij.
>> Por kjo rezulton se një pirg gjithashtu mund të të shihet si një strukturë e të dhënave, një
alternativë për një grup, një alternativë te nje lista e lidhur.
Diçka konceptualisht më interesante që mund të jetë ende
zbatohet duke përdorur njërin prej atyre gjëra, por kjo është një lloj i ndryshëm i
Të dhënat struktura mbështetëse, me të vërtetë, vetëm dy operacioneve.
Por ju mund të shtoni në njohës Karakteristika se këta.
Por këto janë bazat -
shtytje dhe pop.
>> Dhe ideja me një turrë është se në qoftë se unë kemi këtu, me ose pa Annenberg
duke e ditur, një tabaka nga dera e ardhshëm me numrin 9 mbi të.
Pra, vetëm një int.
Dhe unë dua të shtyjë këtë mbi të dhënat e strukturë, e cila aktualisht eshte bosh.
Konsideroni këtë pjesën e poshtme të rafte.
Unë do të shtyjë këtë numër 9 onto rafte, dhe tani ajo është e drejtë atje.
>> Por gjëja më interesante në lidhje me një pirg është se në qoftë se unë tani dua të shtyjë
disa vlera të tjera, si 17, dhe unë të shtyjë kjo mbi rafte, unë jam duke shkuar për të bërë
vetmja gjë intuitive, unë jam vetëm duke shkuar për të vënë atë të drejtë ku ne njerëzit
do të jenë të prirur për ta vënë atë, në krye.
Por ajo që është interesante tani po, si mund të shkoj në 9?
Ju e dini, unë nuk bëj pa ndonjë përpjekje.
>> Pra, çfarë është interesante në lidhje me është se një pirg me dashje,
ajo është një strukturë e të dhënave LIFO.
Silly Mënyra e përshkrimit të kaluar në, së pari jashtë.
Pra, numri i fundit në në këtë kohë ishte 17.
Pra, nëse unë dua të pop diçka jashtë të pirg, ajo mund vetëm të jetë 17.
Pra, ka një urdhër i detyrueshëm i Operacionet këtu, ku pika e fundit
ne duhet të jetë i pari njëri jashtë.
Prandaj akronim, LIFO.
>> Pra, pse kjo mund të jetë e dobishme?
Jeni kontekstet e tyre në të cilën ju do të doni një strukturën e të dhënave si kjo?
E pra, kjo është sigurisht e dobishme brendësi të një kompjuter.
Pra, sistemet operative në mënyrë të qartë të përdorin këtë lloj i strukturës së të dhënave për oxhaqet.
Ne gjithashtu do të shohim të njëjtën ide kur vjen puna për të faqeve web.
Pra, këtë javë dhe javën e ardhshme dhe më tej, dhe si ju të fillojë zbatimin web
faqe në një gjuhë të quajtur HTML, ju mund të të përdorni të vërtetë një strukturë të të dhënave si
kjo për të përcaktuar nëse faqja është formatuar si duhet.
Sepse ne do të shohim të gjitha faqet web të ndjekin një lloj hierarkie, një gjurmë
që do të, në fund të ditës, të jetë një Struktura pemë nën kapuç.
Pra, më shumë se në vetëm një grimë.
>> Por tani për tani, le të propozojë për një moment, se si ne mund të shkoni në lidhje me
përfaqëson atë që një pirg është?
Më lejoni të propozojë që ne të zbatojë një pirg me kodin si kjo.
Pra, një pirg do të ketë në brendësi të tij dy gjëra, një grup, i quajtur tabaka,
vetëm të jenë në përputhje me demo.
Dhe secili prej artikujve në atë grup do të jetë një lloj int.
Dhe kapaciteti është me sa duket ajo?
Sepse unë nuk kam shkruar përkufizim të plotë këtu.
>> Kjo është ndoshta maksimale madhësia e vektorit.
Dhe kjo ndoshta është deklaruar si një të mprehtë të përcaktojë në krye të dosjes, disa
lloj i nënkuptuar si konstante nga kapitalizimi i thjeshtë.
Pra, diku kapaciteti është përcaktuar si madhësia maksimale të mundshme.
Ndërkohë, brenda strukturës së të dhënave i njohur si një pirg do
të jetë një numër i plotë i njohur vetëm thjesht si madhësi.
>> Pra, nëse unë për të përfaqësuar këtë tani në pikturë, le të supozojmë se kjo
Kutia e zezë përfaqëson tërë rafte tim.
Brenda saj është dy variablave.
Kështu që unë jam duke shkuar për të nxjerrë I pari si madhësi.
Dhe e dyta unë jam duke shkuar për të nxjerrë si një grup.
>> Por vetëm për të mbajtur gjërat e rregullt, Normalisht unë do të nxjerrë një koleksion si
këtë, por kjo është lloj i bukur në qoftë se ne përputhen me realitetin, ose
përputhen me modelin mendor.
Pra më lejoni të tërheq në vend array vertikalisht, e cila është vetëm, përsëri,
interpretim i artistit.
A me të vërtetë nuk ka rëndësi se çfarë është nën kapuç.
Dhe ne do të themi se, by default, Kapaciteti do të jetë tre.
Pra, kjo do të jetë lokacioni 0, kjo do të jetë lokacioni 1, kjo
do të jetë lokacioni 2.
>> Nëse unë ryshfet me një top stresit, do të dikush donte për të dalë dhe të drejtuar
hipte këtu për vetëm një çast?
OK, pashë dorën tuaj të parë.
Come on up.
Dakord.
Kështu që unë besoj se është Steven.
Come on up.
Dakord.
>> Por supozoni tani ne Rewind për fillestar gjendja e botës ku unë
kanë deklaruar vetëm një pirg, dhe kjo është do të jetë i kapacitetit tre.
Por madhësia nuk është përcaktuar ende.
Tabaka ende nuk është përcaktuar.
Pra, një çift i pyetjeve parë.
Dhe më lejoni t'ju jap mic kështu që ju mund të marrim pjesë më aktivisht në këtë.
>> Pra, çfarë është brenda madhësisë në këtë moment në kohë, nëse të gjitha unë kam bërë është
deklaruar një pirg me një linjë e kodit?
>> STEVEN: Jo shumë.
>> DAVID Malan: OK, jo shumë.
A e dimë se çfarë ka brenda e madhësisë, nuk e dimë se çfarë është brenda
i këtij array këtu?
>> STEVEN: Vetëm Kodi rastit, e drejtë?
Just -
>> DAVID Malan: Po, unë jam duke shkuar për telefononi atë kod, por të rastësishme -
>> STEVEN: Gjërat.
>> DAVID Malan: Gjëra të tilla si random
>> STEVEN: Bits.
>> DAVID Malan: Bits, e drejtë?
Pra vlerat e plehrave, e drejtë?
Pra permutations të 0 dhe 1-shave.
Mbetjet e usages e mëparshme i këtij kujtesës.
Dhe ne nuk të vërtetë e di se çfarë vlerat janë, kështu që ne zakonisht të tërheqë ata
si pikëpyetjesh.
>> Pra, gjëja e parë që ne jemi me sa duket do të duan për të bërë këtu -
dhe më lejoni të jap këtë fushë brenda e ka një emër - tabaka.
Çfarë duhet të kemi sa duket nisja madhësia në qoftë se ne duam të
filloni duke përdorur këtë turrë?
>> STEVEN: Tray është nën 3.
>> DAVID Malan: Pra, OK.
Të jetë i qartë, kapaciteti është deklaruar diku tjetër si tre.
Dhe kjo është ajo që unë e kam përdorur të ndajë array.
Size është duke shkuar për t'iu referuar sa tabaka janë aktualisht në rafte.
>> STEVEN: Zero.
>> DAVID Malan: Pra, ajo duhet të jetë zero.
Pra shkoni përpara, dhe me çdo gisht, të nxjerrë një zero në madhësi.
Dakord.
Deri tani, çfarë është në brendësi të kësaj këtu, ne nuk e dimë.
Këto janë me të vërtetë vetëm vlerat e plehrave.
Pra, ne mund të tërheqë pikëpyetje, por le të mbajtur të bordit të pastër për tani
sepse kjo nuk ka rëndësi çfarë është atje.
Ne nuk kemi nevojë për të nisja array për ndonjë gjë, sepse në qoftë se ne e dimë se
madhësinë e pirg është zero, mirë, ne nuk duhet të jetë në kërkim në çdo gjë në
kjo array gjithsesi në këtë pikë në kohë.
>> Deri tani mendoj se unë të shtyjë Numri 9 onto rafte.
Si duhet ne update strukturën e të dhënave brenda këtij kutinë e zezë?
Çfarë vlerash duhet të ndryshojë?
>> STEVEN: Brenda -
madhësia?
>> DAVID Malan: OK.
Size çfarë duhet të bëhet?
>> STEVEN: Size do të jetë një.
>> DAVID Malan: OK.
Pra, madhësia duhet të bëhen një.
Kështu që ju mund të bëni këtë në disa mënyra.
Më lejoni t'ju jap, tani tuaj gishtit është një gomë.
Dakord.
Pastaj tani gishtin tuaj është një furçë.
Dakord.
Dhe tani çfarë tjetër ka për të ndryshuar, natyrisht, në strukturën e të dhënave?
>> STEVEN: Ne jemi duke shkuar nga fund deri në 9.
>> DAVID Malan: 9.
OK, i mirë.
Pra, ende nuk ka rëndësi se çfarë është në Vendndodhja një apo dy, sepse ata janë
Vlerat mbeturinash, por ne nuk duhet të shqetësojë kërkoni atje, sepse madhësia është
duke na thënë se vetëm elementi i parë është në të vërtetë legjitime.
Deri tani unë të shtyjë 17 onto listës.
Çfarë ndodh me këtë foto?
>> STEVEN: Pra, madhësia do të shkojë për të dy.
>> DAVID Malan: OK.
Ju jeni gomë -
oops.
Ju jeni një gomë.
>> STEVEN: Eraser.
>> DAVID Malan: Ju jeni një furçë.
>> STEVEN: Furçë.
>> DAVID Malan: OK.
Dhe çfarë tjetër?
>> STEVEN: Dhe pastaj ne -
>> DAVID Malan: Ne e shtyu 17.
>> STEVEN: Ne i përmbahemi 17 në krye, kështu që -
>> DAVID Malan: OK, i mirë.
>> STEVEN: - drop atë poshtë.
>> DAVID Malan: Të gjithë të drejtë.
Është marrë lehtë.
Unë nuk jam duke shkuar për t'ju ndihmuar këtë kohë.
Push 22.
>> STEVEN: Done.
Duke u bërë një gomë.
Unë jam duke u bërë një furçë.
Dhe atëherë unë jam vënë 22.
>> DAVID Malan: 22.
Excellent.
Pra, një herë më shumë.
Unë tani jam duke shkuar për të nxitur rafte mbi 26.
>> STEVEN: Ooh.
Oh gosh.
Ju me të vërtetë më kapi off roje.
>> DAVID Malan: Ju nuk e bëri shihni këtë që vjen?
>> STEVEN: Unë nuk e shoh këtë që vjen.
Ne mund të ri-Kapaciteti fillestar?
>> DAVID Malan: Kjo është një pyetje e mirë.
Pra, ne kemi lloj të pikturuar veten në një cep këtu.
Ka të vërtetë nuk është më e mirë për Steven sepse ne kemi ndarë këtë koleksion
statike, kështu që të flasin, brenda i strukturës dhënave.
Dhe ne e kemi të vështirë koduar në thelb ajo që të jenë të madhësisë tre.
Pra, ne nuk mund të vërtetë të rialokuar atë.
>> Ne mund të qoftë se ne kemi shkuar përsëri në të, ne ripërcaktuar tabaka të jetë një tregues se
Ne pastaj të përdorin malloc në kujtesë dorë për të.
Sepse në qoftë se ne e mori kujtimin nga tog nëpërmjet malloc, ne
pastaj mund të lirojë atë.
Por, para se të liruar atë, ne mund të rialokuar një copë të madhe të kujtesës,
update treguesin, dhe kështu me radhë.
Por tani për tani, kjo është me të vërtetë më të mirë ne mund të bëjmë.
Push dhe pop me sa duket janë duke shkuar të duhet të tregojë ndonjë gabim.
>> Kështu për shembull, zbatimi tonë i shtytje mund të kthehen një bool e cila
u kthye parë e vërtetë, vërtetë, vërtetë.
Por hera e katërt, ajo do të ketë të kthimit të rreme, për shembull.
Dakord.
Very well done.
Urime.
Ju keni fituar topin e stresit tuaj sot.
>> [Duartrokitje]
>> STEVEN: Faleminderit.
>> DAVID Malan: Faleminderit.
OK, kështu që kjo nuk duket të jetë shumë më e një hap përpara, e drejtë?
Ne përshkroi këtë strukturën e të dhënave.
Ka qenë imponues, e drejtë?
Sistemet Operative të donte ai.
Me sa duket web mund të bëjë përdorimin e kësaj, dhe aplikacionet e tjera ende.
Por ajo që një kufizim budalla se ne jemi mbështetur në lloj të javës së dy kufijve
ku kemi fiksuar vargjeve size.
>> Pra, nuk janë me të vërtetë një çift i mënyrat që ne mund të zgjidhur këtë.
Ne mund të ndajë array dinamike, jo me e vështirë coding atë si unë e kam
bëhet këtu, por në vend të ri-shpalljes kjo, vetëm të jetë i qartë, si
diçka si kjo.
Int * tabaka jo, duke vendosur në një kapacitet ende.
Por kur unë deklaroj rafte diku tjetër në kodin tim, atëherë unë mund të telefononi malloc,
të marrë një adresë të një copë të kujtesës, dhe unë mund të caktojë
se adresa për tabaka.
>> Dhe pastaj, për shkak se ajo është vetëm një copë e kujtesës, unë mund të vazhdojë të përdorë katror
simbol parantezë në mënyrë të zakonshme.
Sepse përsëri, nuk është lloj i kësaj ekuivalent funksional i vargjeve dhe
chunks e kujtesës që vijnë prapa nga malloc.
Ne mund të trajtojnë njëri-tjetrin si duke përdorur aritmetike apo akrep
simbol kllapa katrore.
Pra, kjo është një qasje.
>> Por si tjetër mund të kemi zbatuar këtë të dhënat e njëjta strukturë, potencialisht?
E drejta?
Unë ndjehem si ne vetëm zgjidhur këtë problem si një javë më parë.
Cili ishte zgjidhje për këtë problem Steven që u zhvillua në?
Listat e lidhura Pra, të drejtë.
>> Nëse problemi është se ne jemi pikturë veten në një cep duke ndarë
në kujtesën e shumë pak përpara se ne pastaj kanë në një farë mënyre merren me të, mirë,
pse jo vetëm të shmangur atë lëshojë krejt?
Pse jo vetëm të deklarojnë tabaka të jetë një tregues për një, Ergo nyjen një listë të lidhura,
dhe pastaj thjesht të ndajë nyje të reja çdo herë Steven nevojshme për të përshtaten një
Numri në strukturën e të dhënave.
>> Pra, fotografia do të duhet të ndryshojë.
Kjo nuk do të jetë aq i pastër dhe si thjeshtë sa vetëm një grup prej tre ints.
Tani ajo do të jetë një tregues për një struct, dhe se struct do të
kanë një int dhe një tregues tjetër.
Ajo do të udhëheqë me anë të atij akrep struct për një tjetër të tillë të
struct një tjetër të tillë.
Pra, fotografia në fakt do të merrni një Messier bit.
Dhe ne do të kemi shigjeta lidhur çdo gjë së bashku.
>> Por kjo është në rregull, të drejtë, sepse ne kemi parë se si ta bëni këtë.
Dhe një herë ju merrni të rehatshme diçka zbatimin si një linked
listë, të cilat ju do të keni të bëni nëse ju të zgjedhin për të zbatuar një tabelë hash me
chaining të veçantë për të vendosur p-6, ju mund të përdorin atë si një bllok ndërtimi, ose një
Përbërës, ose ne Scratch flet, nje Procedura, diçka që ju vendosni, ju
krijuar vet copë tuaj mister që atëherë ju mund të ripërdorimin.
Tradeoffs kështu, por zgjidhjet e mundshme që ne kemi parë në të vërtetë përpara.
>> Pra, mjaft shpesh, ju shihni këtë çdo vit apo dy kur Apple liron
diçka e re, dhe tërë populli çmendur vijë deri jashtë Apple
dyqan për të blerë margjinale e tyre përmirësuar në hardware.
E them këtë, kjo është në rregull, për shkak se Unë jam një nga ata njerëz.
Pra, çfarë lloji i strukturës së të dhënave mund të përfaqësojnë këtë realitet?
>> E pra, le të thërrasë atë një radhë, një linjë.
Pra britanik do të thërrasë atë në mënyrë tipike një Radhë anyway, kështu që kjo është një emër i bukur.
Dhe dy operacione që një radhë do të mbështesë ne do të thërrasë një enqueue
operacion dhe një operacion dequeue, të cilat janë të ngjashme në
shpirt të shtyjë dhe pop.
Është vetëm lloj i ndryshëm në konventë, atë që ne jemi duke bërë thirrje këto.
Por për enqueue diçka do të thotë për të shtuar ose futur atë në strukturën e të dhënave.
Për dequeue do të thotë për të hequr atë.
Por ndërsa një pirg ishte dhënave LIFO strukturë, një radhë eshte nje ne pare,
e parë të të dhënave jashtë strukturës.
>> Nëse ju jeni personi i parë në linjë, ju do të jetë personi i parë për të marrë
jashtë linjës dhe për të blerë pajisjen tuaj të re.
Paramendoni se sa i mërzitur këta njerëz do të jenë të në qoftë se Apple në vend përdoret një pirg, për
shembull, për të zbatuar picking nga lodër tuaj të re.
Pra Rradhët kuptim, sigurisht, dhe Ne mund të mendoj për të gjitha llojet e
aplikacione, me sa duket, për radhët e gjata, sidomos kur ju doni drejtësi.
Pra, si mund të kemi zbatuar këto si një strukturë e të dhënave?
>> E pra, unë propozoj që ne të mund duhet të bëni atë në këtë mënyrë.
Kështu që unë jam duke shkuar për të tani kanë numra.
Pra, ne do të mbani atë të thjeshtë dhe jo të domosdoshmërisht të flasim në aspektin e tabaka.
Vetëm numrat që njerëzit e marrë.
Kapaciteti është duke shkuar për të, përsëri, fix Numri i përgjithshëm i njerëzve që mund të jenë në
kjo linjë, si tre ose çfarëdo të tjera vlera.
>> Por unë propozoj që kam nevojë për të ndiek jo vetem i madhësisë së
radhë, sa gjërat janë në të.
Pra, madhësia është i tanishëm, madhësia e kapaciteteve është madhësia maksimale.
Vetëm përsëri, nomenklaturë nga Konventa.
Pse nuk kam nevojë për një int shtesë brenda e një radhë të mbajnë gjurmët e asaj që është në
e përparme e linjës?
Pse nuk kam nevojë për të bërë se në këtë rast?
>> E pra, sa është kjo foto do të ndryshojë?
Unë ndoshta mund të ripërdorimin më e kësaj tabloje.
Më lejoni të shkojnë përpara dhe të fshijë atë që është këtu.
Ne do të japim këtë një pak Emri i ndryshëm këtu.
Le të heqin qafe e 17, le të shpëtoj i 9, le të heqin qafe e 3.
Dhe le të shtoni një gjë tjetër.
Unë propozoj që unë duhet të mbajnë gjurmët e front i listës, e cila është vetëm
do të jetë një int si edhe.
Dhe ne jemi duke shkuar për të mbajtur atë të thjeshtë.
Nuk ka listë të lidhura tani për tani.
>> Ne do të pranoj që ne jemi duke shkuar për të përplasem kundër këtij kufiri.
Por çfarë unë dua të shoh ndodhë në këtë kohë?
Kështu që mendoj të shkoj përpara dhe e parë person vjen në përputhje, dhe
kjo është numër 9.
Ne nuk kemi topa stresit.
Mund të vjedhin, të themi, dy ose tre njerëz?
Një, dy, tre?
Come on up.
E drejta nga e para, për shkak se ne do të bëjnë këtë të shpejtë.
>> Secili prej jush është tani do të jetë një djalë tifoz në përputhje në Apple.
Ju nuk do të marrë hardware Apple në fund të këtij pse.
Dakord.
Pra, ju jeni numri 9, ju jeni numër 17, numër 22.
Këto janë numrat arbitrare, si Studenti ID apo gjësend.
Dhe në një moment të vetëm, le të fillojmë për të filloni duke shtuar gjëra.
Dhe unë do të drejtuar bordit këtu këtë kohë.
>> Pra, në këtë rast, unë kam initialized përparme të jetë -
Unë në fakt nuk e kujdesit të vërtetë se çfarë front është, sepse madhësia është zero.
Pra, kjo mund edhe të vetëm të jetë një pikëpyetje.
Këto janë të gjitha pikëpyetjet.
Pra, tani ne do të fillojnë të vërtetë shohim disa njerëz të rreshtuar në dyqan.
>> Pra, nëse numri 9, ju jeni i pari atje orën 5 të mëngjesit, të shkojnë përpara dhe vargoj,
ose nate para.
OK.
Deri tani 9 është këtu.
Kështu 9 eshte ne para te lista.
Kështu që unë jam duke shkuar për të shkuar përpara dhe përditësimin e madhësia e këtyre të dhënave aktuale
struktura mos të jetë 0 më, por të jetë 1.
Unë jam duke shkuar për të vënë në 9 front i listës.
Më lejoni të shkojnë përpara dhe të toggle në ekran kështu që ne mund të shohim të kaluarën ne këtu.
>> Dhe tani çfarë dua për të vënë në front?
Unë jam duke shkuar për të mbajtur gjurmët që e përparme e radhës të drejtë tani
është në lokacion 0.
Sepse çfarë është e ardhshëm do të ndodhë?
E pra, tani unë mendoj enqueue 17 si edhe.
Pra, hop në përputhje atje.
Dhe përsëri, lloj i derës për të dyqan do të jetë këtu.
Deri tani unë kam shtuar 17.
Dhe, edhe pse këta njerëz janë të bllokuar ekran, kjo është OK,
sepse ne mund të shohim atë deri këtu.
Më vjen keq.
>> Audienca: Ne mund të lëvizin -
>> DAVID Malan: Jo, kjo është OK.
Është i madh deri atje.
Kështu 17 është tashmë brendësi të radhë.
Unë kam nevojë për të rinovuar të cilat Fushat tani pse?
OK, patjetër madhësia.
Dhe si në lidhje me para?
OK, nr.
Fronti nuk duhet të ndryshojë, sepse Ndryshe nga një pirg, ne
duan të mbajnë drejtësinë.
Pra, nëse 9 doli i pari, ne duam 9 të jenë jashtë parë i vijës
dhe në dyqan.
>> Në fakt, le të shohim se.
Para se të futur 22, le të të shkojnë përpara dhe dequeue 9.
Cili është emri juaj përsëri?
>> Audienca: Jake.
>> DAVID Malan: Jake është duke shkuar për t'u dequeued tashmë.
Pra, ju merrni për të ecur në dyqan.
Dhe pretendojë se dyqan është atje.
Deri tani ajo ka nevojë për - dit-dit-dit!
Çfarë duhet të ndodhë tani?
Vendimi design.
Pra, nuk është një instinkt i keq, por - çfarë është emri juaj përsëri?
>> Audienca: David.
>> DAVID Malan: David.
Pra, çfarë bëri Davidi bëni?
Ai ishte duke u përpjekur për të zgjidhur të rregulluar e të dhënave Struktura dhe lëvizje nga vendndodhja e tij
në vend të ish-Jake.
Dhe kjo është në rregull në qoftë se ne jemi të gatshëm të pranojmë se, si një
detaje zbatimit.
Por së pari, le të rifreskoni të dhënat e strukturën para se të bëjmë këtë.
Sepse unë nuk jam simpati idenë e të gjitha njerëzit e zhvendosur në këtë linjë.
>> Kjo nuk është punë e madhe në qoftë se Davidi e bën atë me një hap, por përsëri, mendoj se përsëri në
kur ne kemi pasur tetë vullnetarë në faza dhe ne kemi bërë si futje
lloj, ku ne kishim për të filluar lëviz gjithë rreth.
Kjo mori shtrenjtë, e drejtë?
Kjo më bën servilizëm rreth Big O e N, O i madh n katror perseri.
Kjo nuk është ndjenjë si një rezultat ideal.
>> Pra, le të vetëm update këtë.
Pra, madhësia e radhë nuk është më 2.
Është tani thjesht 1.
Por unë tani mund të rinovuar diçka Unë nuk update para,
front i listës.
Unë vetëm mund të them, është se vendndodhja 1?
Pra, tani ne kemi vlerën plehrash këtu, Vlera e mbeturinave këtu, dhe Davidi, në
e mesme të këtij mbeturina.
Por Struktura e të dhënave është ende i paprekur.
>> Dhe në fakt, edhe unë nuk kanë nevojë për ndryshuar numrin ish Jake
9, sepse kush kujdeset.
Unë kam informacion të mjaftueshëm tani në madhësi që unë e di se ka një person në
këtë radhë.
Dhe unë e di se ai person është në vend të 1 jo 0.
Unë nuk jam duke numëruar.
Kështu 1 si edhe.
Pra, struktura e të dhënave është ende OK.
>> E pra, çfarë ndodh më pas?
Enqueue Le -
çfarë është emri juaj?
>> Audienca: Callen.
>> DAVID Malan: Callen.
Le të enqueue një Callen, dhe 22 është tashmë në radhë.
Deri tani ajo ka për të ndryshuar këtu?
Fronti nuk do të ndryshojë, natyrisht.
Size do të ndryshojë që të jetë 2 herë.
22 Dhe përfundon këtu, 9 është ende e pranishme, por kjo është një mënyrë efektive
Vlera e mbeturina tani.
Është vetëm një mbetje e kaluara Jake.
>> Kështu që tani se çfarë ndodh në qoftë se Unë dequeue Davidin?
Një operacion i fundit, dequeue David.
Ne mund të zhvendoset, por unë propozoj le të bëjë sa më pak punë që është e mundur.
Tani struktura e të dhënave im shkon mbështetur në madhësi 2-1.
Por e përparme e radhë tani bëhet 2.
Unë nuk kam nevojë për të ndryshuar këto numra vetëm ende, sepse ata janë
vetëm vlerat e plehrave.
>> Por, çfarë ndodh tani?
Supozoni se unë enqueue veten, 26?
Ndjehem si unë i përkas mbi këtu.
Kështu që unë jam duke u enqueued.
Kështu që unë lloj i përkasin këtu.
Dhe edhe pse ju nuk e bëni mjaft vlerësojmë këtë vizualisht në skenë,
sepse ne kemi mjaft hapësirë, unë duhet nuk do të rrimë këtu, pse?
>> Audienca: Ju jeni jashtë caqeve.
>> DAVID Malan: E drejta.
Unë jam jashtë caqeve.
Unë kam indeksuar përtej caqet e këtij koleksioni.
I vërtetë duhet të jetë në njërën nga tri lokacione të mundshme.
Tani, ku është më e natyrshme për të shkuar?
Unë propozoj që ne leveraged një javë një mashtrim.
Operatori mod, përqindje.
Sepse unë jam teknikisht qëndruar në lokacioni 3, por unë bëj 3 kapacitetin mod,
kështu 3, një shenjë qind, 3 -
Kapaciteti është 3.
Çfarë është ajo?
Çfarë është mbetur kur ju ndani me 3 nga 3?
0.
>> Kështu që e vë më ishin Jake ishte, e cila është në të vërtetë e mirë.
Deri tani zbatimi e kjo gjë do të
jetë pak e nje koke.
Është me të vërtetë vetëm një linjë e dhimbje koke, të kodit.
Por të paktën tani nuk ka mbeturina Vlera këtu, por ka dy
ints legjitime këtu.
Dhe unë pretendojnë se tani ne kemi bërë saktësisht se çfarë ne duhet të bëjmë për aq kohë sa
ne të ndryshojë atë që e Jake vlera të ishte 26.
>> Ne tani kemi informacione të mjaftueshme ende për të ruajtur integritetin
i kësaj strukture të dhëna.
Ne jemi ende lloji i jashtë fat kur ne doni të futur katër apo më shumë gjithsej
elemente, por unë mund të paktën të bëjë goxha Përdorimi efikas i kësaj konstante
kohë, në fakt.
Unë nuk duhet të shqetësohen për zhvendosjen e të gjithë, si prirjen e Davidit ishte.
>> Çfarëdo pyetjeje mbi oxhaqet, apo këtë radhë?
>> Audienca: A është arsyeja pse ju keni nevojë për madhësi kështu që ju e dini
ku të ketë një person?
>> DAVID Malan: Pikërisht.
Unë duhet të dini madhësinë e array sepse kam nevojë të dini saktësisht se si
shumë prej këtyre vlerave janë të ligjshme, dhe kështu që unë mund të gjeni se ku për të vënë
personi tjetër.
Saktësisht.
Madhësia është -
në të vërtetë, ne nuk update këtë ende.
Kam shtuar veten në 26.
Madhësia është tani, jo 1, por 2.
Deri tani kjo me të vërtetë më ndihmon të gjeni koka e lista, e cila nuk eshte 0, nuk
1, por është 2.
Front i listës është me të vërtetë numri 22.
Sepse ai doli i pari, kështu që ai duhet të të lejohet në dyqan para meje,
edhe pse shikimi Unë jam duke qëndruar afër ruajtur.
>> Të gjithë të drejtë?
Një raund i duartrokitje për këto guys dhe ne do të le ata nga atje.
>> [Duartrokitje]
>> DAVID Malan: Unë mund të le të ju mbani tabaka.
Ne mund të shohim se çfarë ndodh në qoftë se ju doni, por ndoshta jo.
Dakord.
Kështu që çfarë tani bën që na lënë?
E pra, më lejoni të propozoj që ka një disa struktura të tjera të të dhënave që ne mund të
filloni duke shtuar në kit tonë mjet që do në fakt të jetë mjaft, mjaft e rëndësishme si
ne pikiatë në stuff web.
E cila përsëri, ka disa lloj lidhje te pemeve në formën e
diçka e quajtur DOM, dokument Modeli objekt.
Por ne do të shohim më shumë prej që para se të gjatë.
>> Më lejoni të propozojnë definitionally se ne quajnë pemën tani atë që ju mund të dini si
më shumë nga një pemë familjare, ku ju kanë disa paraardhës në
Rrënjët e pemës.
Një Opar patriarkal ose nje at shumë të lartë të pemës.
Pa bashkëshortin e tyre, në këtë rast.
Por tani ne kemi atë që ne do të thërrasë Fëmijët, të cilat janë nyjet që rri
off fëmijën e majtë apo e djathtë të fëmijës, Shigjetat si përshkruhen këtu.
>> Me fjalë të tjera, në strukturën e të dhënave pemë në kompjuter, një pemë ka zero
ose më shumë nyje.
Në qoftë se ka të paktën një nyje, që është quajtur rrënja.
Është gjërat që vizualisht ne barazim në krye.
Dhe kjo nyje, si çdo nyje të tjera, mund të ketë zero, një, ose dy, ose tre,
ose megjithatë shumë fëmijë Struktura e të dhënave mbështet.
Në këtë rast, rrënja, ruajtjen Vlera e një, ka dy fëmijë, 2 dhe 3,
kështu që ne zakonisht quajmë 2 e majtë fëmijë dhe 3 fëmijë të drejtë.
>> Dhe atëherë kur ne të merrni poshtë për të 5, 6, dhe 7, 6 mund të quhet fëmija mesme.
Nëse ju kanë katër fëmijë, ajo merr konfuze.
Pra, ne të ndaluar përdorimin e atë lloj i shkurtore gojë.
Por kjo është me të vërtetë vetëm një pemë familjare.
Dhe gjethet këtu janë nyjet që vetë nuk kanë fëmijë.
Ata rri off fund të pemës.
>> Pra, si mund të kemi zbatuar një pemë që ka vetëm dy fëmijë maksimalisht?
Ne do të thërrasë atë një pemë binare.
Bi përsëri do të thotë dy, në këtë rast, si me binar.
Dhe kështu që ajo mund të ketë zero, një, ose dy fëmijë maksimalisht.
>> Unë do të propozoj që ne zbatimin nyjen për këtë strukturë me një int n,
dhe pastaj dy pointers, njëri i quajtur la, njëri i quajtur të drejtë.
Por ata janë vetëm e bukur konventat arbitrare.
Dhe çfarë është e bukur tani, veçanërisht nëse ju lloj luftuan konceptualisht me
recursion, ose mendonin se nuk ishte me të vërtetë një zgjidhje për çdo gjë,
veçanërisht nëse ju mund të dalë jashtë kujtesës.
Tani që ne jemi duke folur rreth të dhënave Strukturat dhe algoritme që lejojnë
na të kaloj dhe të manipuluar ato, rezulton se recursion vjen përsëri në
një shumë më bindëse nëse nuk është mënyra më e bukur.
>> Pra, kjo unë propozoj është zbatimi Kërko i një funksioni.
Duke pasur parasysh dy inpute -
kështu që mendoj se për këtë si një kuti e zezë.
Duke pasur parasysh dy inpute, N, një int, dhe një kursori te nje peme, nje treguesi te nje
, nyja apo me të vërtetë rrënja e një peme, unë Pretendimi se ky funksion mund të kthehen
vërtetë apo e rreme, se vlera n është brenda e kësaj peme.
>> Çfarë është brenda këtij kutinë e zezë?
E pra, katër degë.
Vetëm kontrollon parë.
Nëse pema është i pavlefshëm, vetëm të kthimit të rreme.
Nëse nuk ka nyje, nuk ka n, nuk ka asnjë numër, vetëm të kthimit të rreme.
Nëse pse, n, vlera që ju jeni në kërkim per, eshte me pak sesa peme shigjete n, dhe
vetëm të jetë i qartë, çfarë do të thotë kur Unë shkruaj Pemën dhe pastaj shigjetë
simbol, n?
Saktësisht.
Kjo do të thotë se dereference pointer quajtur pemë.
Shkoni atje, dhe pastaj të merrni brenda e që nyjë dhe të merrni fushën e tij të quajtur n.
Dhe pastaj krahasojnë n aktuale që ishte kaloi në Kërkim kundër saj.
>> Pra, nëse n është më pak se, vlera n në nyjen e pemës vetë, të mirë,
Çfarë do të thotë kjo?
Kjo do të thotë asgjë, në shikim të parë.
E drejta?
Ashtu si kur ju keni një rrjet të Vlerat, ju mund të dëshironi të aplikoni binary
kërkoni si një formë e ndarjes dhe sundo.
Por ajo që supozimi nuk kemi nevojë për të bërë për kërkim binar për të punuar në të gjitha
në librin e telefonit dhe Shembujt më herët?
>> Si të zgjidhet.
Pra, le të përsosin përkufizimin e pemës këtu të mos jetë vetëm një pemë, të cilat mund të
të ketë ndonjë numër të fëmijëve.
Jo vetëm një pemë binare, të cilat mund të kemi 0, 1, ose 2 maksimalisht.
Por si një pemë binare e kërkimit, ose BST, e cila është vetëm një mënyrë e sofistikuar për të thënë një
pemë binare të tillë që çdo nyjë e fëmija i majtë, nëse është i pranishëm, është
më pak se nyja.
Dhe fëmija e drejtë e çdo nyje, nëse është i pranishëm, është më i madh
se nyjen vetë.
>> Pra, me fjalë të tjera, në qoftë se keni qenë për të nxjerrë nga pema, të gjithë numrat janë të
balancuar me kujdes si kjo në mënyrë që nëse ju keni 55 si rrënjë, 33 mund të shkojnë
në të majtë të saj, sepse ajo është më pak se 55 vjeç.
77 mund të shkoni në të djathtë të saj, sepse kjo është më e madhe se 55 vjeç.
Por tani vini re, të njëjtin përkufizim, kjo është një përkufizim gjithkund rekursive me gojë,
duhet të aplikojë për 33.
Fëmija 33 së majtë duhet të jetë më pak se ajo, dhe fëmijës së drejtë 33, 44, duhet të jetë
më të mëdha se ajo.
>> Pra, kjo është një pemë binare kërko, dhe Unë propozoj, duke përdorur një grimë të vogël e
recursion, ne tani mund të gjeni n.
Pra, nëse n është më pak se n vlerës që është Nyja e tanishëm, unë jam duke shkuar për të shkuar
përpara dhe vë bast, kështu që të flasin, dhe vetëm të kthehen çdo gjë që përgjigja është e
kërkoni për n më Fëmija majtë peme.
Vini re përsëri, ky funksion vetëm pret një yll nyjeve, një
kursori te nje nyje.
Pra, me siguri unë vetëm mund të bëjë pemë shigjeta majtë, e cila do të çojë
mua për një tjetër nyje.
Por çfarë është ajo nyja?
>> Mirë, sipas këtij deklaratës, majtë është vetëm një tregues, në mënyrë që vetëm
do të thotë që unë jam duke kaluar me funksionin e kërkimit një tregues të ndryshëm, përkatësisht
një që përfaqëson Pema e fëmijës tim të majtë.
Pra, në këtë rast, akrep në 33, në qoftë se kjo është input tonë mostër Ndërkohë, nëse
n është më e madhe se n vlerës në Nyja e tanishme në pemë, atëherë unë jam i
do të shkojnë përpara dhe vë bast në tjetrin drejtimi dhe vetëm thonë, unë nuk bëj
e di nëse kjo vlerë është n në pemë, por unë e di në qoftë se ajo është, kjo është poshtë mia
Dega e drejtë, kështu që të flasin.
Pra më lejoni thirrje Recursively të kërkoni, duke kaluar një n përsëri, por duke kaluar në një
tregues për fëmijën tim të djathtë.
>> Me fjalë të tjera, në qoftë se unë jam aktualisht në 55 dhe unë jam duke kërkuar për 99, unë e di se 99
është më i madh se 55 vjeç, kështu që ashtu si unë grisi javët libër telefoni më parë dhe ne
shkoi drejtë, në mënyrë të ngjashme jemi ne do të shkojnë drejtë këtu.
Dhe unë nuk e di nëse kjo është në të djathtën time fëmijë, dhe kjo nuk është, 77 është atje, por
Unë e di se është në atë drejtim.
Kështu që unë e quaj kërkimin për fëmijën time të djathtë, 77, dhe le figurë kërkimit nga
99 atje, nëse në këtë arbitrare Shembulli është në të vërtetë atje.
>> Tjetër, çfarë është rasti i fundit?
Nëse pema është i pavlefshëm është një rast.
Nëse n është më pak se nyja e tanishme Vlera është një tjetër rast.
Nëse n është më e madhe sesa e tanishme Vlera Nyja është një rast i tretë.
Çfarë është rasti i katërt dhe i fundit?
Unë mendoj se ne jemi nga e rasteve, e drejtë?
Ajo duhet të jetë se n eshte ne nyja aktuale që unë jam në.
>> Pra, nëse unë jam në kërkim për 55 në këtë pikë në tregimin, që dege i
pemë do të kthehen vërtetë.
Pra, çfarë është interesante këtu është se ne në fakt, ndryshe nga javët e kaluara, ne lloj
i kemi dy raste bazë.
Dhe ata nuk kanë për të të jenë të gjitha në krye.
Lartë është një rast bazë, sepse nëse pemë është null, nuk ka asgjë për të bërë.
Kthehen vetëm një koduar vështirë Vlera e rreme.
>> Dega e poshtme është lloj i Default, të cilit, nëse ne kemi për të kontrolluar
null, ne kemi kontrolluar nëse ajo duhet të jetë u largua, por kjo nuk duhet të jetë, ne kemi
kontrollohet nëse ajo duhet të jetë e drejtë, por ajo nuk duhet të jetë, në mënyrë të qartë se duhet të jetë
drejtë ku jemi.
Kjo është një çështje bazë.
Pra, ka dy raste gjithkund rekursive sandwiched atje në mes.
Por unë mund të ketë shkruar kjo në asnjë mënyrë.
Unë vetëm mendova se lloj i ndjerë natyrore që së pari të kontrolloni për një gabim të mundshëm,
atëherë kontrolloni majtë, atëherë kontrolloni drejtë, atëherë supozojmë se ju jeni në nyjen
ju jeni në të vërtetë duke kërkuar për të.
>> Pra, pse kjo mund të jetë e dobishme?
Pra, ajo rezulton jashtë -
dhe më lejoni të hidhen në një ngacmues këtu se është në internet.
Ne jemi duke shkuar për të filluar përdorimin jo një gjuha e programimit në fillim, por një
gjuha markup.
Një gjuhë markup duke qenë një që është të ngjashme në frymë të programimit
gjuhë, por kjo nuk do të ju jap Aftësia për të shprehur veten logjikisht.
Ajo vetëm ju jep mundësinë për të shprehin veten strukturalisht.
>> Ku nuk ju duan të vënë diçka në faqe, web faqe?
Çfarë ngjyre ju doni të bëni atë?
Font size Çfarë bëni ju doni të bëni atë?
Fjalët Çfarë bëni ju në të vërtetë doni në faqen e internetit?
Pra, kjo është një gjuhë markup.
Por atëherë ne shumë shpejt do të prezantoj JavaScript, e cila është një e plotë
gjuhë programimi.
Shumë i ngjashëm sintaksore në dukje me C, por ajo do të ketë disa
bukur, më të fuqishme, më shumë karakteristika përdorues miqësore.
>> Dhe një nga frustrimet në këtë Pika në semestrin është se ne do të
shpejti zbatojë speller në shumë më pak rreshta të kodit duke përdorur gjuhë të tjera
C sesa vetë lejon, por për arsye të Ne së shpejti do të kuptojnë.
Kjo do të jetë i parë faqe të tilla web.
Ajo do të jetë plotësisht underwhelming, e parë që ne bëjmë.
Ajo thjesht do të thotë, përshëndetje bota.
Por në qoftë se ju kurrë nuk kam parë atë përpara, kjo është HTML,
HyperText Markup Language.
>> Nëse ju shkoni në një opsion të caktuar në menu shumica e ndonjë shfletues, në ndonjë web faqe në
internet, ju mund të shihni HTML se disa njerëz shkroi
krijuar atë web faqe.
Dhe kjo ndoshta nuk do të duken si shkurtër ose si i zoti si kjo.
Por kjo do të ndjekin modelin e këtyre kllapa hapura dhe ul dhe
Letrat dhe potencialisht numrat.
>> Unë mendova se do të ju jap një ngacmues të asaj që ju do të jetë në gjendje të bëjë
pas marrjes CS50.
Lermë të shkoj cs.harvard.edu / Rob, homepage vetë tonë Rob Bowden-së.
Ai e bëri këtë për ne.
Pra, ju së shpejti do të jetë në gjendje të bëjë këtë.
Dhe gjithashtu, çfarë keni dëgjuar këtë mëngjes -
çfarë keni dëgjuar këtë mëngjes -
>> [Brejtësi DANCE MUSIC]
>> - You'll jetë në gjendje për ta bërë këtë.
Që na pret të mërkurën.
Ne do të shohim ju pastaj.
>> [Brejtësi DANCE MUSIC]
DAVID Malan: Në CS50 e ardhshëm -