[Powered by Google Translate] [Nedēļa 6]
[David J. Malan] [Hārvarda]
[Tas ir CS50.] [CS50.TV]
>> Tas ir CS50, un tas ir sākums 6 nedēļām,
tāpēc jaunu instrumentu pāris tagad ir pieejami, lai jūs varētu izmantot,
no kuriem pirmais ir sauc CS50 stils.
Izredzes ir, ja jūs esat līdzīgi man, vai kādu no mācību līdzcilvēkiem,
Jūs, iespējams, redzējuši programmu, kuras stils izskatās mazliet kaut kas līdzīgs šim.
Varbūt jūs sākat griešana daži stūri vēlu naktī, vai jūs ar to nodarboties vēlāk,
un tad TF vai CA nāk pār darba laikā.
Tad tas ir grūti, lai mēs lasītu.
Nu, šis kods ir sintaktiski pareizs, un tas būs apkopot, un tas patiešām darbojas.
Bet tas noteikti nav 5 par stilu.
>> Bet tagad, ja mēs iedziļināties šajā direktorijā šeit-
un ievēroju, ka man ir conditions2.c-
un es palaist šo jauno komandu, style50, par šo failu conditions2.c, Enter,
pamanīt, ka tas mani informēja, ka tā ir bijusi stilizēti.
Gedit pamanīja, ka fails ir mainīts uz diska,
un ja es noklikšķiniet papildināšanas, visas jūsu problēmas ir tagad automatizēta.
[Aplausi]
Tas ir viens no lietām, ko mēs darīja šīs nedēļas nogalē.
Apzināties, ka tas ir nepilnīgs, jo tur ir daži kodu
ka tas vienkārši nebūs spējīgs Stylize perfekti,
bet saprotu, tas ir tagad līdzeklis, jūs varat izmantot
ja tikai uzkopt kādu no vairāk errantly novietot cirtaini lencēm un tamlīdzīgi.
>> Bet vairāk pārliecinoši tagad ir CS50 Pārbaudīt.
Ar CS50 pārbaudi, jūs faktiski var veikt tādas pašas pareizības pārbaudes
uz savu kodu, ka mācību stipendiātiem spēj.
Tas ir komandrindas lietderība, kas nāk tagad ierīces
tiklīdz jūs darīt update50 kā vienu
4 PSET specifikācijas, un jūs to izmantot galvenokārt kā šis.
Jūs palaist komandu check50.
Tad jūs iet uz komandrindas argumentu, vai vispār sauc par slēdzi vai karogs.
Vispār, lietas, kas ir defises sauc slēdzis
līdz komandrindas programmu, tā c nosaka
pārbaudēs, kuras vēlaties, lai palaistu.
>> Testi, kas jūs vēlaties, lai palaistu identificē unikāli ar šīs virknes,
2012/pset4/resize.
Citiem vārdiem sakot, tas ir tikai patvaļīgi, bet unikāls virkne
ka mēs izmantojam, lai unikāli identificētu PSET 4 ir pareizības pārbaudes.
Un tad jūs norādāt kosmosa atdalītas failu sarakstu, kas jūs vēlaties, lai augšupielādēt
līdz CS50 Check analīzei.
Piemēram, ja es iet manā risinājums šeit resize.c-
ļaujiet man atvērt lielāku termināla logs-
un es iet uz priekšu un palaist teiksim check50-c 2012/pset4/resize,
un tad es iet uz priekšu un norādīt nosaukumus failiem,
resize.c, un pēc tam hit Enter, tas saspiež,
tā attēli, tā pārbauda, ​​un es vienkārši nav viss ķekars testu.
In sarkanu viens pie augšējā kreisajā saka, ka resize.c un bmp pastāv.
Tas bija tests. Tas bija jautājums, mēs jautāja.
Un tas ir neapmierināti, jo atbilde bija nepatiesa.
Balts teksts zem tā saka paredzams bmp.h pastāvēt, un tas ir vienkārši mana vaina.
Es aizmirsu augšupielādēt to, tāpēc man ir nepieciešams augšupielādēt abus failus,
resize.c un bmp.h.
Bet tagad paziņojums visiem citiem testiem ir dzeltenā krāsā, jo tie ir ne veikt,
un tā smiley sejas ir vertikāls, jo viņš nav ne apmierināts, ne skumji,
bet mums ir labot šo jautājumu ar sarkanu pirms tie pārējie pārbaudes darbosies.
>> Ļaujiet man noteikt šo.
Ļaujiet man tālināt un atkārto to, šoreiz ar bmp.h arī
uz komandrindas, Enter, un tagad, ja viss noritēs labi,
tas notiek, lai pārbaudītu un pēc tam atgriezties rezultāts-turiet savu elpu-
viss zaļš, kas nozīmē, es esmu dara patiešām labi uz 4 PSET līdz šim.
Jūs varat redzēt un secināt no aprakstošu tekstu šeit
ko tieši tas ir mūsu pārbaudīta.
Mēs vispirms testē vēl failus pastāv?
Mēs tad testē dara resize.c apkopotu?
Tad mēs testē tas nav mainītu 1x1 pikseļu BMP, ja n, mainīt izmērus faktors, ir 1.
Tagad, ja jums nav ne jausmas, ko n ir, jūs, kad jūs pikējošais 4 PSET,
bet tas vienkārši ir veselība pārbaudītu, lai pārliecinātos, ka tu esi ne izmērus
attēls vispār, ja izmainīsiet koeficients ir 1.
Ja turpretim, tas maina 1x1 pikseļu uz 1x1 pikseļu BMP uz 2x2 pareizi
ja n ir 2, tad līdzīgi, raktuves veido atbilstoši.
>> Īsāk sakot, tas ir domāts, lai, vienu, veikt šķērsošanas pirkstiem
no vienādojumu labi, pirms jūs iesniedzat savu PSET.
Jūs zināt, tieši to, ko jūsu TF drīz zināt
kad jūs iet par to iesniedzot kādu no šīm problemātiskajām komplekti,
un arī pedagoģiskās motivācija tiešām ir likt
iespēja sev priekšā tā, ka tad, kad jūs zināt a priori
ka tur ir bugs jūsu kodu un testi, kas netiek nodotas,
Jūs varat nodot efektīvāku laika uzreiz atrisināt šīs problēmas
nevis zaudēt punktus, saņemt atgriezenisko saiti no jūsu TF,
un tad iet, "Ahh," kā es ir izpētījuši, ka no.
Tagad vismaz tur instruments, lai palīdzētu jums atrast to.
Tas nav gatavojas norādīt, kur kļūda ir, bet tas jums pateiks
kāda ir simptomātiska no tā.
>> Tagad saprotam testi ne vienmēr ir pilnīgs.
Tieši tāpēc, ka jums ekrāns pilns ar zaļo smiley sejas
nenozīmē, ka jūsu kods ir ideāls, bet tas nozīmē,
ka tā ir nodota dažus testus, ko nosaka spec.
Dažreiz mēs ne atbrīvot pārbaudes.
Piemēram, detektīvromāns, viens no 4 PSET aspektiem,
ir sava veida žēl, ja mēs jums
atbilde par to, kas tas ir, un tur ir vairāki veidi, kā atklāt numurs
, kas personai ir šajā sarkanā troksni.
Spec vienmēr jānorāda nākotnē uz 5 PSET vēlāk
ko pārbauda pastāv jums.
Jūs pamanīsiet, ka tas ir balts URL apakšā.
Tagad, tas ir tikai diagnostikas izeja.
Ja jūs apmeklēt šo URL, jūs saņemsiet visu ķekars traks, mistisks ziņojumus
ka jūs esat laipni aicināti apskatīt, bet tas ir galvenokārt par darbiniekiem
lai mēs varētu diagnosticēt un atkļūdot bugs check50 pati.
>> Bez ADO, pieņemsim pāriet uz kur mēs left off.
CS50 bibliotēka mēs ņēmām par pašsaprotamu dažām nedēļām,
bet tad pagājušajā nedēļā, mēs sākām atplēšot vienu no tā slāņiem.
Mēs sākām liekot malā virkni labu ko vietā?
[Studenti] Char.
Char *, kas ir char * visu šo laiku,
bet tagad mums nav izlikties, ka tā ir faktiskais datu tips virkne.
Drīzāk, tas ir bijis sinonīms veidu par char *,
un virkne ir rakstzīmju secība,
tad kāpēc tas ir jēga, lai pārstāvētu stīgas kā char * s?
Kāda char * pārstāvēt kontekstā šī jēdziena virknes?
Yeah >> [Studentu]. Pirmā zīme.
Labi, pirmais raksturs, bet ne gluži pirmā zīme.
Tas ir-[Studentiem] Adrese.
Labi, adrese pirmās rakstzīmes.
Viss, kas ir nepieciešams, lai pārstāvētu virknes datora atmiņā
ir tikai unikāla adrese jau pirmajā baitā.
Jums pat nav jāzina, cik ilgi tas ir
jo kā jūs varat izdomāt dinamiski?
[Studentu] rindas garums.
Jūs varat zvanīt rindas garums, lieliska, bet kā virknes garums darbu?
Ko tas dod? Yeah.
[Studentu] Turpini, līdz jūs saņemsiet null raksturs.
Jā, tieši tā, tas tikai vairākkārt uzsvērts ar par cilpu, kamēr cilpa,
neatkarīgi no * līdz beigām, un beigas ir pārstāvēta
ar 0 \, tā saukto Nul raksturs, Nul,
nedrīkst jaukt ar null, kas ir rādītājs,
kas nāks klajā sarunā šodien atkal.
>> Mēs nomizoti atpakaļ slāni GetInt, un tad mēs ņēmām apskatīt GetString,
un atcerēties, ka abas šīs funkcijas, vai tiešām,
GetString, bija izmantojot noteiktu funkciju
faktiski parsēt, kas ir, lasīt un analizēt, lietotāja ievadi.
Un kāda bija, ka jaunā funkcija?
Scanf vai sscanf. Tas tiešām nāk daži dažādas garšas.
Ir scanf, tur sscanf, tur fscanf.
Tagad, lai gan, pieņemsim koncentrēties uz viens visvairāk viegli ilustrētas,
un ļaujiet man iet uz priekšu un atvērt arī ierīcē
failu, piemēram, tas, scanf1.c.
Tas ir super vienkārša programma,
bet tas, ko mēs nekad darīts
bez palīdzības no CS50 bibliotēkas.
Tas izpaužas int no lietotāja. Kā tas strādā?
Nu, saskaņā 16 tur,
pamanīt, ka mēs atzīt int sauc x, un šajā brīdī stāsts,
kāda ir vērtība x?
[Dzirdams studentu reaģēšanas]
[Deivids M.] Tiesības, kas zina, kādu atkritumu vērtība potenciāli, tāpēc 17, mēs vienkārši pateikt lietotājam
man numuru, lūdzu, un soli 18 ir, ja tā kļūst interesanti.
Scanf šķiet aizņemties ideju no printf jo tas izmanto šos formāta kodus pēdiņās.
% D protams decimāls skaitlis.
Bet kāpēc man iet uz & X nevis tikai X?
Bijusī ir pareizs. Yeah.
[Dzirdams studentu reaģēšanas]
Tieši tā, ja mērķis šīs programmas, piemēram, funkciju GetInt pati,
ir iegūt int no lietotāja es varētu iet funkcijas
visi mainīgie es gribu, bet, ja man nav nodot tos ar atsauci
vai adreses, vai pēc rādītājs, visi sinonīms šodienas vajadzībām,
tad šī funkcija nav iespējas mainīt saturu šo mainīgo.
Tas iet uz kopiju tāpat kā buggy versija mijmaiņas
ka mēs esam runājuši par pāris reizes tagad.
>> Bet tā vietā, darot & x, es esmu burtiski iet, ko?
[Studentu] adresi. >> Adresi x.
Tas ir tāpat kā zīmēšanas karti par funkciju sauc scanf un šeit saka,
šie ir virzienos uz rieciens atmiņas ar datoru
ka jūs varat iet uzglabāt dažas skaitlim collas
Lai sscanf šim darīt
ko uzņēmējs, kas gabals sintakse tas notiek, lai būtu izmantot
lai gan mēs nevaram redzēt, jo kāds cits rakstīja šo funkciju?
Citiem vārdiem sakot - kas tas ir?
[Studentu] X lasīt.
Tur būs daži lasījumā, bet tikai attiecībā uz x šeit.
Ja scanf tiek nodots adresi x,
sintaktiski, ko operators ir pienākums pastāv kaut kur
iekšpusē scanf īstenošanas lai scanf
faktiski var uzrakstīt numurs 2 uz šo adresi?
Jā, tā *.
Atgādināt, ka * ir mūsu dereference operators, kas būtībā nozīmē iet tur.
>> Kad esat nodota adresi, kā tas ir šajā gadījumā,
scanf ir iespējams, ja mēs tiešām izskatījās apmēram tā pirmkodu-
dara * X vai ekvivalents tiešām iet uz šo adresi un nodot dažas vērtības tur.
Tagad, kā par to, kā scanf izpaužas ievadi no tastatūras,
mēs vicināt savas rokas, kas uz šodienu.
Tikai pieņemt, ka operētājsistēma ļauj sscanf runāt
lietotāja tastatūra, bet šajā brīdī tagad 19 līnija,
kad mēs vienkārši izdrukāt X, tas, šķiet, ir gadījums
ka scanf ir likts int jo x.
Tas ir tieši tā, kā scanf darbojas, un atcerēties pagājušajā nedēļā
tas ir tieši tā, kā GetString un GetInt un citi tās ģimenes funkcijas
visbeidzot strādā, lai gan ar nelielu dispersijas piemēram sscanf,
kas nozīmē skenēt virkni nevis tastatūru.
Bet pieņemsim to apskatīt nelielu dispersijas šo.
Jo scanf2, es tiešām ieskrūvē augšu.
Kas ir nepareizi un es ņemšu paslēpt komentāru, kas izskaidro tik daudz-
Kas ir nepareizi ar šo programmu, 2 versiju?
Esi kā tehniskās iespējas šajā laikā.
Tas izskatās diezgan labi.
Tas ir labi izrobota, bet-
labi, kā par pieņemsim plūmju to uz leju, lai īsāku jautājumiem?
Līnija 16. Kas līnija 16 darām precīzi, bet tehniskā angļu valodā?
Getting mazliet neveikli. Jā, Maikls.
[Studentu] Tas norāda uz pirmo burtu virknes.
>> Labi, tuvu. Ļaujiet man iekniebt, ka mazliet.
Norādot uz pirmo burtu virknes, jūs deklarējat mainīga sauc buferis
kas norāda uz pirmo adresi virknes,
vai drīzāk, kas norādīs tieši uz char.
Pamanāt tas nav reāli norādot visur, jo tur nav piešķires operators.
Nav vienādības zīmi, lai visi mēs darām, ir sadalīt mainīgo saukto bufera.
Tas notiek, ir 32 biti, jo tas ir rādītājs,
un saturu bufera domājams beidzot
ietvers adresi palija, bet tagad, ko tas buferis ir?
Tikai daži viltus, kas zina, kādu atkritumu vērtība,
jo mēs esam nav skaidri inicializēts, tāpēc mums nevajadzētu uzņemties neko.
Labi, tāpēc tagad līnija 17-Kāda Line 17 darīt?
Varbūt, ka būs silts šo augšu.
Tas drukā virkni, labi?
Tas drukā String lūdzu.
>> Līnija 18 ir sava veida pazīstami tagad, ka mēs tikko redzējām nesakritību šis
bet ar citu formātu kodu, tāpēc 18 līnija,
mēs esam spēcīgi scanf šeit ir adrese rieciens atmiņas.
Es gribu, lai jūs gredzens virkni, kas nozīmēja% s,
bet problēma ir tā, ka mēs neesam darījuši pāris lietas šeit.
Kas ir viena no problēmām?
[Studentu] Tas mēģina dereference ar null rādītāju.
Labi, Null vai vienkārši citādi zināma norādes.
Tu esi nododot scanf adresi, bet jūs vienkārši teica pirms brīža
ka adrese ir daži atkritumu vērtība, jo mums nav reāli piešķirtu to neko,
un lai jūs esat stāsta scanf faktiski iet nodot virkni šeit,
bet mēs nezinām, kur šeit vēl ir,
tāpēc mēs esam faktiski nav piešķirti atmiņas buferī.
Turklāt, ko jūs arī nav pat stāstīt scanf?
Pieņemu, ka tas bija rieciens atmiņas, un tas bija nevis atkritumu vērtību,
bet jūs joprojām nav stāsta scanf kaut ko svarīgu.
[Studentu] Ja tas tiešām ir, zīme &.
Zīme &, tāpēc šajā gadījumā, tas ir labi.
Jo buferis jau deklarēta kā rādītājs
ar * gabals sintaksi, mums nav nepieciešams izmantot aizvieto & zīmes
jo tas jau adresi, bet es domāju, ka es dzirdēju to šeit.
[Studentu] Cik liela tā ir?
Labi, mēs esam ne stāsta scanf cik liels tas buferis ir,
kas nozīmē, ka pat tad, ja buferis ir rādītājs,
mēs esam sakot scanf, nodot virkni šeit,
bet šeit varētu būt 2 baiti, tas varētu būt 10 baiti, tas varētu būt megabaitu.
Scanf nav ne jausmas, un tāpēc tas ir rieciens atmiņas
iespējams, tas nav virkne vēl.
Tas ir tikai virkne, kad jūs uzrakstīt rakstzīmes un \ 0 uz šo gabalu no atmiņas.
Tagad tas ir tikai daži rieciens atmiņas.
Scanf nevar zināt, kad apstāties rakstot uz šo adresi.
>> Ja jūs atceraties dažus piemērus pagātnē, kad es nejauši drukāti uz klaviatūras
mēģinot pārplūdes bufera, un mēs runājām piektdien par tieši to.
Ja pretinieks kaut injects savā programmā daudz lielāka vārdu
vai teikumu vai frāzi, tad jums bija gaidījis jūs varat pārsniegts
rieciens atmiņas, kas var būt negatīvas sekas,
piemēram, ņemot visā pati programma.
Mums ir nepieciešams noteikt šo kaut kā.
Ļaujiet man attālināt un iedziļināties šīs programmas 3 versiju.
Tas ir nedaudz labāk.
Šajā versijā, pamanīt atšķirību.
16 līniju, es esmu atkal atzīta par mainīgo sauc buferi,
bet kas tas ir tagad?
Tas masīvs 16 simboli.
Tas ir labi, jo tas nozīmē, ka es tagad var pateikt scanf
šeit ir faktiskais rieciens atmiņas.
Jūs varat gandrīz iedomāties masīvu kā norādes tagad,
pat ja viņi nav faktiski līdzvērtīgs.
Tie būs uzvesties atšķirīgi dažādos kontekstos.
Bet tas noteikti lieta, ka buferis ir atsauces
16 blakusesošiem chars jo tas ko masīvs
un ir bijis dažas nedēļas tagad.
>> Lūk, es saku scanf šeit rieciens atmiņas.
Šoreiz tas ir faktiski rieciens atmiņas,
bet kāpēc šī programma joprojām ir apgūstams?
Kas ir nepareizi vēl?
Man teica man 16 baiti, bet-
[Studentu] Ko darīt, ja tās ierakstīt vairāk kā 16?
Tieši tā, kas notiks, ja lietotājs veidiem 17 rakstzīmēm vai 1700 rakstzīmēm?
Faktiski, pieņemsim redzēt, ja mēs nevaram ceļojums pa šo kļūdu tagad.
Tas ir labāk, bet ne perfekta.
Ļaujiet man iet uz priekšu un palaist padarīt scanf3 apkopot šo programmu.
Ļaujiet man palaist scanf3, Stīgu lūdzu: sveiki, un mēs, šķiet, ir labi.
Ļaujiet man mēģināt nedaudz garāks, sveiki tur.
Labi, pieņemsim do Sveiki Kā jums šodien, Enter.
Getting veida laimīgs šeit, teiksim Sveiki Kā jums.
Damn it.
Labi, tāpēc mēs saņēmām laimīgs. Redzēsim, vai mēs nevaram noteikt šo.
Nē, tas nav gatavojas let me kopēt.
Mēģināsim to atkal.
Visas tiesības, stāvēt.
Redzēsim, cik ilgi es varētu izlikties, lai koncentrētos, kamēr vēl to izdarīt.
Damn it. Tas ir diezgan piemērots, faktiski.
Tur mums iet.
Punkts veikts.
>> Tas, neērts gan tā arī ir, tas ir arī viens no lielu neskaidrību avotu
Rakstot programmas, kas ir bugs, jo tie izpaužas
tikai vienu reizi, bet dažreiz.
Realitāte ir tāda, ka pat tad, ja jūsu kods ir pilnībā bojāta,
tas var būt tikai pilnīgi sadalīti reizi brītiņa
jo dažreiz, būtībā kas notiek ir operētājsistēma ir piešķirti
nedaudz vairāk atmiņas, nekā jums tiešām ir nepieciešams, lai kāda iemesla dēļ,
un tāpēc neviens cits izmanto atmiņu uzreiz pēc Jūsu rieciens 16 zīmēm,
Tātad, ja jūs iet uz 17, 18, 19, neatkarīgi, tas nav tik liels darījumu.
Tagad, dators, pat ja tas nav crash šajā brīdī,
varētu beidzot izmantot baitu numurs 17 vai 18 vai 19 kaut kas cits,
kurā brīdī savus datus, ka jūs likts tur, lai gan pārmērīgi garš,
gatavojas saņemt pārrakstīti potenciāli ar kādu citu funkciju.
Tas nav obligāti gatavojas paliek neskartas,
bet tas ne vienmēr izraisa seg vaina.
Bet šajā gadījumā, es beidzot sniedz pietiekami rakstzīmes
ka es būtībā pārsniedza manu segments atmiņu, un BAM,
operētājsistēma teica: "Atvainojiet, tas nav labi, segmentācija vaina."
>> Un redzēsim tagad, ja kāds paliek šeit manā direktorijā-
pamanīt, ka man ir šī failu šeit, kodols.
Ievērojiet, ka šī ir atkal sauc kodols dump.
Tas ir būtībā fails, kas satur saturu jūsu programmas atmiņā
tajā vietā, kurā tas avarēja,
un tikai mēģināt nedaudz piemēru šeit ļaujiet man iet šeit
un palaist gdb uz scanf3 un tad norādiet trešo argumentu sauc kodols,
un pamanīt šeit, ka ja es sarakstu kodu,
mēs varēsim kā parasti ar gdb sākt staigāt pa šo programmu,
un es varētu palaist to un, tiklīdz es hit-kā ar soli komandu gdb-
tiklīdz es hit potenciāli buggy līniju pēc rakstīt milzīgs virknē,
Es varētu faktiski noteikt to šeit.
Vairāk par šo, lai gan, sadaļā ziņā galveno izgāztuves
un patīk, lai jūs faktiski var pabāzt ap iekšpusē no galvenajiem izgāztuves
un redzēt uz ko līnija programmai neizdevās tevi.
Visus jautājumus, tad par norādes un adreses?
Jo šodien mēs esam gatavojas sākt veikt par pašsaprotamu, ka šīs lietas pastāv
un mēs zinām, tieši to, ko viņi ir.
Jā.
>> [Studentu] kā ir jums nav, lai darītu aizvieto & zīmes blakus daļēji
Labs jautājums.
Kā tas nākas, man nebija likt aizvieto & zīmes blakus uz rakstzīmju masīva kā es darīju agrāk
lielākā daļa no mūsu piemēriem?
Īsā atbilde ir masīvi ir mazliet īpašs.
Jūs varat gandrīz domāt bufera kā faktiski to adresi,
un tas tikai tā notiek, ir gadījums, ka kvadrātiekava notācija
ir ērtība, lai mēs varētu iet uz 0 grupā, kronšteinu 1,
kronšteins 2, bez izmantot * notācija.
Tas ir mazliet no balta meliem, jo ​​masīvi un norādes
ir, faktiski, nedaudz atšķiras, bet tās bieži vien var, bet ne vienmēr var izmantot pārmaiņus.
Īsāk sakot, kad funkcija gaida rādītāju uz rieciens atmiņas,
Jūs varat vai nu nodot to adresi, kas tika atgriezto malloc,
un mēs redzēsim malloc atkal pirms ilgi, vai arī jūs varat nodot to nosaukumu masīva.
Jums nav jādara aizvieto & zīmes ar masīviem, jo ​​tie jau ir
būtībā patīk adreses.
Tas ir viens izņēmums.
Kvadrātiekavās padara to īpašu.
>> Vai jūs varēsiet ievietot aizvieto & zīmes blakus uz bufera?
Ne šajā gadījumā.
Tas nav darbs, jo, atkal, šī stūra lietas
kur masīvi nav gluži reāli adreses.
Bet mēs varbūt nāk atpakaļ, ka pēc neilga laika ar citiem piemēriem.
Mēģināsim atrisināt problēmu šeit.
Mums ir datu struktūra, kas mēs esam, izmantojot kādu laiku sauc par masīvu.
Sakāms, ka tas, ko mēs tikko bija.
Bet masīvi ir daži upsides un downsides.
Masīvi ir jauki, kāpēc?
Kas ir viena lieta, kas jums patīk, cik jums patīk masīvi-par masīvu?
Kas ir ērts par viņiem? Kas pārliecinoši?
Kāpēc mēs ieviest tos pirmajā vietā?
Yeah.
[Studentu] Tās var uzglabāt daudz datu, un jums nav, lai izmantotu visu lieta.
Jūs varat izmantot sadaļu.
Labi, ar masīvu jūs varat uzglabāt daudz datu,
un jums nav obligāti izmantot visu tā, lai jūs varētu overallocate,
kas varētu būt izdevīgi, ja jums nav iepriekš zināt, cik daudz par kaut ko gaidīt.
>> GetString ir perfekts piemērs.
GetString, raksta mums, nav ne jausmas, cik daudz simb gaidīt,
tāpēc, ka mēs varam sadalīt gabalos pieguļošajā atmiņas ir laba.
Masīvi arī atrisināt problēmu mēs redzējām pāris nedēļas atpakaļ tagad
ja jūsu kods sāk pāriet uz kaut ko ļoti slikti izstrādāts.
Atgādināt, ka es izveidojis students struktūru sauc Dāvids,
un tad tas bija patiesībā alternatīva, lai gan,
, kam mainīga sauc vārdu un citu mainīgo sauc, es domāju, māja,
un citu mainīgo sauc ID jo šajā stāstā es gribēja ieviest kaut ko citu
patīk Rob programmā, tā tad es nolēmu gaidīt minūti,
Man vajag, lai pārdēvētu šīs mainīgos.
Sauksim raktuves NAME1, ID1, house1.
Sauksim Rob s name2, house2, ID2.
Bet tad pagaidiet minūti, ko par Tommy?
Tad mums bija vēl trīs mainīgos.
Mēs iepazīstināja kāds cits, četras reizes pa mainīgajiem.
Pasaule sāka iegūt netīrs ļoti ātri,
tāpēc mēs ieviesām structs, un kas ir pārliecinoši par struct?
Kāda C struct jums darīt?
Tas ir patiešām neērti šodien.
Kas >> [dzirdams studentu reaģēšanas]?
Jā, īpaši, typedef ļauj izveidot jaunu datu tipu,
un struktūrai, struktūrai atslēgvārds, ļauj rezumēju
konceptuāli saistītos tiesību datu kopā
un pēc tam viņiem piezvanīt kaut kā students.
>> Tas bija labi, jo tagad mēs varam modelēt
daudz veida konceptuāli atbilstīgs jēdziens skolēns ir mainīgs
nevis patvaļīgi kam viens virknes, viens ID, un tā tālāk.
Masīvi ir jauki, jo tie ļauj mums sākt sakopšanu mūsu kodu.
Bet kāda ir negatīvie tagad no masīva?
Ko jūs varat to darīt? Yeah.
[Studentu] Jums ir jāzina, cik liela tā ir.
Jums ir jāzina, cik liela tā ir, tāpēc tas ir sava veida sāpes.
Tiem no jums ar iepriekšēju programmēšanas pieredzes zinu, ka ir daudz valodu,
piemēram, Java, jūs varat lūgt rieciens atmiņas, kas īpaši masīvs,
cik liels ir jums, ar garumu, īpašuma, tā sakot, un tas ir tiešām ērti.
C, jūs nevarat pat zvanīt strlen par vispārēju masīvs
jo strlen, jo vārds nozīmē, ir tikai stīgas,
un jūs varat izrēķināt garumu virknes, jo par šo cilvēku konvencijas
Kam \ 0, bet masīvs, vairāk vispārīgi, ir tikai rieciens atmiņas.
Ja tas ir masīvs Ints, tur nav būs kādu īpašo raksturu
gada beigās tevi gaida.
Jums ir jāatceras garumu masīva.
Vēl no masīva negatīvie audzēti tās galvu GetString sevi.
Kas vēl no masīva negatīvie?
Sir, tikai tu un es šodien.
[Dzirdams studentu reaģēšanas] >> Tas, ko?
Tas ir atzīts par kaudze.
Labi, paziņoja uz skursteņa. Kāpēc ne jums patīk, ka?
[Studentu], jo tā izpaužas atkārtoti.
Tas izpaužas atkārtoti.
Labi, ja jums izmantot masīvu piešķirt atmiņu,
Jūs nevarat, piemēram, atgriezties, jo tas ir uz skursteņa.
Labi, ka ir trūkums.
Un kā par vienu citu ar masīvu?
Kad jūs piešķirt to, jūs esat veida ieskrūvē, ja jums nepieciešams vairāk vietas
nekā masīvs ir.
>> Tad mēs ieviesām, atceros, malloc, kas deva mums iespēju dinamiski piešķirt atmiņu.
Bet ja mēs centāmies citu pasauli pavisam?
Ko darīt, ja mēs vēlējāmies, lai atrisinātu pāris šīm problēmām
tāpēc mēs tā vietā, mana spalva ir aizmiguši šeit-
Ko darīt, ja mēs tā vietā vēlējāmies būtībā radīt pasauli, kas vairs kā šī?
Tas ir masīvs, un, protams, šāda veida pasliktinās, tiklīdz mēs hit beigām masīva,
un es tagad vairs nav vietas citam skaitlim vai citu raksturu.
Ko darīt, ja mēs veida preemptively saka labi, kāpēc nav mēs atpūsties
Šī prasība, ka visiem šiem atmiņu gabalos būt saistītai atpakaļ atpakaļ,
un kāpēc ne, ja man vajag int vai char,
tikai dod man vietu kādā no tām?
Un, kad man vajag otru, dod man citu vietu,
un, kad man ir nepieciešams cits, dod man citu vietu.
No kura priekšrocība ir tāda, ka, ja kāds cits
ņem atmiņas nekā šeit, nav liels darījumu.
Es ņemšu šo papildu rieciens atmiņas šeit un tad tas viens.
>> Tagad, vienīgais loma šeit ir tas, ka šis gandrīz jūtas kā man ir
viss ķekars dažādiem mainīgajiem.
Tas jūtas kā piecu dažādu mainīgajiem potenciāli.
Bet ja mēs nozagt ideju no stīgām
kad mēs kaut kā sasaistīt šīs lietas kopā konceptuāli, un kas notiks, ja es to izdarīja?
Tas ir mans ļoti slikti sagatavots bulta.
Bet pieņemsim, ka katrs no šiem atmiņas gabalos
norādīja uz otru, un tas puisis, kurš nav brālis viņa tiesības,
nav šādu bultiņas.
Tas ir fakts, ko sauc saistīts saraksts.
Tas ir jauns datu struktūra, kas ļauj mums piešķirt rieciens atmiņas,
tad otru, tad otru, tad vēl, jebkurā laikā mēs vēlamies
programmas laikā, un mēs atceramies, ka viņi visi kaut kā saistīta
ko burtiski Virknējuma tos kopā, un mēs to izdarījām, piktogrammām šeit ar bultiņu.
Bet kods, kāda būtu mehānisms, caur kuru jūs varētu kaut savienot,
gandrīz kā Scratch, viens gabals uz citu gabalu?
Mēs varētu izmantot rādītāju, labi?
Jo tiešām bulta, kas notiek no kreisās augšējās laukumā,
tas puisis šeit uz šo vienu, varētu būt iekšā šajā laukumā
ne tikai daži Ints, ne tikai daži palija, bet ko tad, ja es tiešām piešķirti
nedaudz papildu vietu tā, ka tagad,
katru manu gabalu no atmiņas, lai gan tas maksās mani,
Tagad izskatās nedaudz vairāk taisnstūra kur viens no atmiņas gabalos
tiek izmantots vairākos, tāpat skaita 1,
un tad, ja tas puisis saglabā numuru 2,
šo citu rieciens atmiņas tiek izmantots bulta,
vai vairāk konkrētāk, rādītājs.
Un pieņemsim, ka es glabāt numuru 3 vairāk nekā šeit, bet es izmantoju šo norādīt uz šo puisis,
un tagad tas puisis, pieņemsim es tikai gribu trīs šādas gabalos atmiņas.
Es izdarīt līnija caur ka, norādot null.
Nav papildu raksturs.
>> Patiešām, tas ir, kā mēs varam iet par īstenojot
kaut kas sauc saistīts saraksts.
Saistīts saraksts ir jauna datu struktūra, un tā ir pakāpiens uz
daudz mīļotājs datu struktūras, kas sāk risināt problēmas
gar Facebook-veida problēmas līnijas un Google tipa problēmas
kur jums ir milzīgs datu kopas, un tas vairs griež to
uzglabāt visu contiguously un izmantot kaut ko līdzīgu lineāru meklēšanā
vai pat kaut kā bināro meklēšanu.
Jūs vēlaties vēl labāk darbotos reizes.
Patiesībā, viens no Svētā Grails mēs runājam par vēlāk šajā nedēļā vai nākamās
ir algoritms, kura darbības laiks ir nemainīgs.
Citiem vārdiem sakot, tas vienmēr ir tāds pats laiku neatkarīgi
cik liels ieguldījums ir, un tas tiešām būtu pārliecinoši,
pat vairāk nekā kaut logaritmiskā.
Kas tas ir uz ekrāna šeit?
Katrs no taisnstūru ir tieši tas, ko es tikko vērsa ar rokām.
Bet lieta visu ceļu pa kreisi ir īpašs mainīgs.
Tas būs viens rādītājs, jo viens gotcha
ar saistītu sarakstu, jo šīs lietas sauc,
ir tas, ka jums ir pakārt uz vienu galu saistīts saraksts.
>> Tāpat kā ar auklu, jums ir jāzina adresi pirmā char.
Pats darījums saistītajiem sarakstiem.
Jums ir jāzina adresi pirmo rieciens atmiņas
jo no turienes, jūs varat sasniegt jebkuru citu.
Negatīvie.
Kādu cenu mēs maksāt par šo daudzpusību, kam dinamiski
prāvs datu struktūra, kas, ja mēs kādreiz vajag vairāk atmiņas, labi,
vienkārši piešķirt vēl vienu gabalu un izdarīt rādītāju no
vecās uz jauno asti saraksta?
Yeah.
[Studentu] Tas aizņem apmēram divreiz tik daudz vietas.
Tas aizņem divreiz vairāk vietas, tā ka noteikti negatīvie, un mēs esam redzējuši šo
tradeoff pirms starp laiku un telpu un elastību
kur līdz šim, mums nav 32 bitu par katru no šiem skaitļiem.
Mums tiešām ir nepieciešams 64, 32, skaitu un 32 rādītāja.
Bet hey, man ir 2 gigabaiti RAM.
Pievienojot vēl 32 bitus šeit un šeit nevar teikt, ka liels ir galā.
Bet lielu datu kopu, tas noteikti piebilst, līdz burtiski divreiz tik daudz.
Kas cits negatīvie tagad, vai ko pilnmetrāžas mēs padoties,
ja mēs pārstāvam sarakstus lietas ar saistītajā sarakstā, nevis masīvs?
[Studentu] Jūs nevarat traversa to atpakaļ.
Jūs nevarat traversa to atpakaļ, lai jūs esat veida ieskrūvē ja jūs ejot
no kreisās uz labo, izmantojot par cilpu vai kamēr cilpa
un tad tu saproti, "Ak, es gribu iet atpakaļ uz saraksta sākumā."
Jūs nevarat, jo šīs norādes tikai aiziet no kreisās uz labo pusi, kā bultas norāda.
>> Tagad jūs varētu atcerēties sākumu sarakstā ar citu mainīgo,
bet tas sarežģītības paturēt prātā.
Masīvs, cik tālu jūs dotos, jūs vienmēr varat darīt mīnus, mīnus, mīnus mīnus
un doties atpakaļ, no kurienes jums nāca.
Kas cits negatīvie šeit? Yeah.
[Dzirdams students jautājums]
Jūs varētu, lai jūs esat tiešām tikko piedāvāja datu struktūru sauc divkārt saistīts saraksts,
un, protams, jūs varētu pievienot citu rādītāju uz katru no šiem taisnstūriem
kas iet pretējā virzienā, otrādi no kuriem
Tagad jūs varat traversa un atpakaļ,
kas negatīvie tagad jūs izmantojat trīs reizes tik daudz atmiņas, kā mēs izmantot, lai
un arī pievienojot sarežģītību ziņā kodu jums ir rakstīt, lai saņemtu to labi.
Bet tie visi ir varbūt ļoti saprātīgas kompromisi, ja maiņa ir svarīgāka.
Yeah.
[Studentu] Jūs arī nevar būt 2D saistīts saraksts.
Labi, jūs nevarat patiešām ir 2D saistīts saraksts.
Jūs varētu. Tas ne tuvu nav tik viegli, kā masīvs.
Piemēram masīvu, jūs atklātu kronšteinu, slēgta Bracket, atklātu Bracket, slēgta bracket,
un jūs saņemsiet dažas 2-dimensiju struktūru.
Jūs varētu īstenot 2-dimensiju saistīts saraksts
ja jūs add-kā jūs ierosināts-1/3 rādītāju uz katru no šīm lietām,
un, ja jūs domājat par citu sarakstu nāk pie jums 3D stils
no ekrāna uz mums visiem, kas ir tikai vēl viens ķēdes kaut kāda.
Mēs varētu darīt, bet tas nav tik vienkārši, kā rakstīt atklātu kronšteinu, kvadrātiekavas. Yeah.
[Dzirdams students jautājums]
Labi, tāpēc tas ir reāls futbolists.
>> Šie algoritmi, ka mēs esam pined nekā, piemēram, ak, bināro meklēšanu,
Jūs varat meklēt masīvs numurus uz kuģa
vai telefona grāmatu tik daudz ātrāk, ja jūs izmantojat skaldi un valdi
un bināro meklēšanas algoritmu, bet binārā meklēšana nepieciešami divi pieņēmumi.
Viens, ka dati tika sakārtoti.
Tagad mēs varam iespējams saglabāt šo sakārtoti,
tāpēc varbūt tas nav bažas, bet binārā meklēt arī pieņemts
ka jums bija brīva piekļuve numuru sarakstā,
un masīvs ļauj jums ir brīva piekļuve, un pēc izlases piekļuvi,
Es domāju, ja jūs esat dota masīvs, cik daudz laika tas tevi
nokļūt līdz 0 kronšteinu?
Viena operācija, jūs vienkārši izmantot [0] un tu esi tieši tur.
Cik soļus tas veic, lai iegūtu 10 vietu?
Viens solis, jūs vienkārši doties uz [10], un tu esi tur.
Turpretī, kā Jūs saņemsiet uz 10 skaitlim, kas saistītā sarakstā?
Jums ir jāsāk sākumā, jo jūs esat tikai atcerēties
par saistītu saraksta sākums, tāpat kā virknē tiek atceras
ar adresi savu pirmo char, un atrast, ka 10. int
vai 10. raksturs virknē, jums ir meklēt visu nopelt lieta.
>> Atgādināsim, ka mēs esam ne atrisināt visas mūsu problēmas.
Mēs ieviest jaunas, bet tas tiešām atkarīgs no tā, ko jūs mēģināt, lai dizains.
Runājot par īstenošanas, mēs varam aizņemties ideju no šī studentu struktūras.
Sintakse ir ļoti līdzīga, izņemot tagad, ideja ir mazliet vairāk abstrakts
kā māja un nosaukums un ID.
Bet es ierosinu, ka mēs varētu būt datu struktūra C
ka sauc mezglā, jo pēdējais vārds slaidā liecina,
iekšpusē mezglā, un mezgls ir tikai vispārējs konteiners datorzinātnēs.
Tas parasti sagatavots kā aplis vai kvadrātveida vai taisnstūra kā mēs esam darījuši.
Un šajā datu struktūru, mums ir int, N,
tā ka skaitlis es gribu saglabāt.
Bet kas tas ir otrā rinda, struct mezglā * nākamais?
Kāpēc tas ir pareizi, vai kāda loma šī lieta spēlē,
pat ja tas ir mazliet mistisks pēc pirmā acu uzmetiena?
Yeah.
[Dzirdams studentu reaģēšanas]
Tieši tā, tāpēc * veida laupījuma, ka tas ir rādītājs kaut kāda.
Šīs rādītāja nosaukums ir patvaļīgi nākamais,
bet mēs varētu būt sauc tā neko mēs vēlamies, bet ko šis rādītājs norāda uz?
[Studentu] Vēl mezglā >> Tieši tā,. Tas norāda uz citu šādu mezglu.
>> Tagad tas ir sava veida zinātkāri no C
Atgādināt, ka C ir nolasīt ar kompilatoru augšas uz leju, no kreisās uz labo,
kas nozīmē, ja-tas ir nedaudz atšķiras no tā, ko mēs darījām ar studentu.
Kad mēs noteikti students, mēs faktiski nav laidis vārdu tur.
Tas vienkārši teica typedef.
Tad mums bija int id, String nosaukums, stīgu māja,
un tad studente apakšā struct.
Šī deklarācija ir nedaudz atšķirīgs, jo,
atkal, C kompilators ir mazliet muļķīgi.
Tas ir tikai gatavojas lasīt augšas uz apakšu,
tādēļ, ja tas sasniedz 2 līnija šeit
kur blakus ir deklarēta un tā redz, ak, šeit mainīgo sauc nākamo.
Tas ir rādītājs, lai struct mezglā.
Kompilators gatavojas saprast, kas ir struct mezglā?
Es nekad neesmu dzirdējis par šo lietu pirms,
jo vārds mezglu citādi nevarētu parādīties
līdz apakšā, tāpēc tas ir atlaišana.
Jums ir ko teikt struct mezglā šeit, kuru pēc tam var saīsināt vēlāk
pateicoties typedef noteikti šeit, bet tas ir tāpēc,
mēs atsaucoties struktūru pati iekšpusē struktūru.
Tas ir viens gotcha tur.
>> Dažas interesantas problēmas gatavojas rasties.
Mēs esam ieguvuši sarakstu numurus. Kā mēs ievietot to?
Kā mēs meklēt to? Kā mēs izdzēst no tā?
Sevišķi tagad, ka mums ir pārvaldīt visus šos norādes.
Tu doma norādes bija sava veida prāta saliekuma
kad jums bija viens no tiem vienkārši mēģina lasīt int uz to.
Tagad mums ir manipulēt visu sarakstu vērts.
Kāpēc ne mēs mūsu 5 minūšu pārtraukumu šeit, un tad mēs panāktu
daži pat uz skatuves ļaudīm darīt tieši to.
>> C ir daudz jautrības, kad tas ir rīkojusies out.
Kas būtu burtiski gribētu būt pirmais?
Labi, nāk uz augšu. Tu esi pirmais.
Kurš gribētu būt 9? Labi, 9.
Kā par 9? 17?
Maz kliķe šeit. 22 un 26 Šajā priekšējā rindā.
Un tad kā par kādu tur tiek atgādināts.
Jums ir 34. Labi, 34, nākt uz augšu.
Pirmais ir tur. Labi, visi četri no jums, puiši.
Un kurš gan mēs teikt par 9?
Kurš ir mūsu 9?
Kurš patiešām grib būt 9? Labi, nāc, būs 9.
Šeit mēs iet.
34, mēs sasniegtu jums tur.
Pirmā daļa ir padarīt sevi izskatās, ka.
26, 22, 17, labi.
Ja jūs varat stāvēt off uz pusi, jo mēs ejam uz malloc jums brīdi.
>> Labi, labi.
Labi, teicami, tāpēc pieņemsim uzdot pāris jautājumus šeit.
Un tiešām, kāda ir jūsu vārds? >> Anita.
Anita, labi, nāk vairāk nekā šeit.
Anita gatavojas palīdzēt mums veida atrisināt vienu diezgan vienkāršu jautājumu, pirmkārt,
kas ir, kā jūs atrast, vai vērtība ir sarakstā?
Tagad, ievērosiet, ka, pirmkārt, šeit pārstāv Lucas,
ir nedaudz atšķirīgs, un tāpēc viņa papīra gabals ir apzināti sāniem
jo tas nav gluži tik garš, un nav aizņem tik daudz biti,
pat ja tehniski viņš ir tāds pats papīra izmēru tikai pagriezt.
Bet viņš ir mazliet atšķirīgs, jo viņš ir tikai 32 biti rādītājs,
un visi šie puiši ir 64 biti, no kuriem puse ir skaits, no kuriem puse ir rādītājs.
Bet rādītājs nav attēlots, tādēļ, ja jūs puiši varētu nedaudz neveikli
izmantot savu kreiso roku norādīt uz personu, blakus jums.
Un tu esi skaits 34. Kāds ir Jūsu vārds?
Ari.
Ari, tāpēc patiesībā, tur papīru labajā rokā, un kreisās rokas iet taisni uz leju.
Jūs pārstāvat null pa kreisi.
>> Tagad mūsu cilvēku aina ir ļoti konsekventa.
Tas ir tiešām kā norādes strādā.
Un, ja jūs varat scrunch mazliet šo ceļu, lai es neesmu jūsu veidā.
Anita šeit, atrast man numuru 22,
bet uzņemties ierobežojumu ne cilvēki, turot papīra gabaliem,
bet tas ir saraksts, un jums ir tikai Lucas sākt ar
jo viņš ir burtiski pirmais rādītājs.
Pieņemsim, ka jūs pats esat rādītājs, un tāpēc jums arī ir iespēja norādīt uz kaut ko.
Kāpēc nav sākat norādot tieši to Lucas ir pavērsts?
Labi, un ļaujiet man ieviest šo out nekā šeit.
Tikai dēļ diskusiju, ļaujiet man uzvilkt tukšu lapu šeit.
Kā jūs izskaidrot savu vārdu? >> Anita.
Labi, Anita.
Teiksim mezglā * Anita = Lucas.
Nu, mums nevajadzētu zvanīt jums Lucas. Mums vajadzētu zvanīt vispirms.
Kāpēc tas ir faktiski atbilst realitātei šeit?
Viens, vispirms jau eksistē.
Pirmais ir piešķirti domājams kaut kur šeit.
Mezglā * pirmkārt, un tas ir bijis piešķirts sarakstu kaut.
Es nezinu, kā tas notika. Tas notika pirms klases sākās.
Šis saistīts saraksts cilvēkam ir izveidota.
Un tagad šajā brīdī stāsts-tas viss notiek Facebook acīmredzot vēlāk-
šajā brīdī stāsts, Anita ir inicializēts ir vienāda ar pirmo,
kas nenozīmē, ka Anita norāda uz Lucas.
Drīzāk, viņa norāda uz to, ko viņš norāda uz
jo pati adrese, kas ir iekšā, Lucas ir 32 bitu - 1, 2, 3 -
Tagad arī iekšpusē Anita 32 bitiem - 1, 2, 3.
>> Tagad atrast 22. Kā jūs iet par to izdarīt?
Ko tas nozīmē? >> Point whatever.
Norādīt uz whatever, tā iet uz priekšu un rīkoties to, kā vislabāk iespējams šeit.
Labi, labi, un tagad jūs norādot uz-kāda ir jūsu vārds ar 22?
Ramons. >> Ramons, tāpēc Ramons ir saimniecības up 22.
Tagad esat veikuši pārbaudi.
Vai Ramon == 22, un, ja tā, piemēram, mēs varam atgriezties taisnība.
Ļaujiet man-kamēr šie puiši stāvēt šeit nedaudz neveikli-
ļaujiet man kaut ko darīt ātri kā bool atrast.
Es iešu uz priekšu un teikt (mezglā * saraksta, int n).
Es būšu labi atpakaļ ar jums, puiši. Man vienkārši ir uzrakstīt kādu kodu.
Un tagad es esmu gatavojas iet uz priekšu un darīt šo, mezglā * Anita = sarakstu.
Un es esmu gatavojas iet uz priekšu un saka, kamēr (Anita! = NULL).
>> Metafora šeit kļūst mazliet izstiepts, bet, kamēr (Anita! = NULL), ko es vēlos darīt?
Man vajag kaut kādā veidā salīdzināt
skaitlis, kas Anita tiek pavērsts.
Agrāk, kad mums bija būvēm, kas mezglu,
mēs izmantojām dot apzīmējumu, un mēs teiktu kaut ko līdzīgu
anita.n, bet problēma ir tā, ka Anita nav struktūrai par sevi.
Kas viņa ir?
Viņa rādītājs, tik tiešām, ja mēs vēlamies izmantot šo dot apzīmējumu-
un tas ir gatavojas meklēt apzināti mazliet mistisks-
mums ir jādara kaut kas līdzīgs doties uz kāda Anita kreiso roku tiek pavērsts
un pēc tam iegūt lauku sauc n.
Anita ir rādītājs, bet to, kas ir * Anita?
Ko jūs atradīsiet, kad jūs iet uz to, Anita ir pavērsts?
Struktūrai, mezglu, un mezglu, atsaukšana, ir lauku sauc n
jo tā ir, atceros, šie 2 lauki, blakus un n,
ka mēs redzējām pirms brīža tieši šeit.
>> Lai tiešām atdarināt šo kodu,
mēs varētu darīt un teikt, ja ((* Anita). n == n), n ka es esmu meklē.
Ievērojiet, ka funkcija tika nodota skaita man rūp.
Tad es varētu iet uz priekšu un darīt kaut ko līdzīgu pretī patiesu.
Cits, ja tas nav gadījums, ko es vēlos darīt?
Kā es varu tulkot ar kodu, ko Anita darīja intuitīvi ejot pa sarakstu?
Ko man darīt šeit, lai modelētu Anita veikt minēto pasākumu pa kreisi, šo soli pa kreisi?
[Dzirdams studentu reaģēšanas] >> Kas tas ir?
[Dzirdams studentu reaģēšanas]
Labi, nav slikta ideja, bet agrāk, kad mēs esam izdarījuši, mēs esam darījuši Anita + +
jo tas pievieno numuru 1 līdz Anita,
kas parasti norāda uz nākamo personu, piemēram, Ramon,
vai personai blakus viņam, vai viņam blakus cilvēks uz leju līniju.
Bet tas nav gluži labi, šeit, jo to, ko dara šī lieta izskatās atmiņā?
Nav tas. Mums ir atslēgt to.
Tas izskatās šādi atmiņā, un, lai gan es esmu sastādīts 1 un 2 un 3 tuvu viena otrai,
ja mēs patiešām modelētu šo-Vai jūs guys, bet vēl norādot uz tiem pašiem cilvēkiem,
var kādu no jums veikt izlases soli atpakaļ, daži no jums nejauši solis uz priekšu?
>> Tas haoss joprojām saistīts saraksts,
bet šie puiši varētu būt jebkur atmiņā,
tāpēc Anita + + nav dodas uz darbu, kāpēc?
Kas ir pie vietas Anita + +?
Kas zina.
Tas ir dažas citas vērtības, kas tikai tā notiek, ir izvirzīti
Starp visiem šiem nejaušības mezgliem, jo ​​mēs esam ne izmantojot masīvu.
Mēs, kas katru no šiem mezgliem individuāli.
Labi, ja jūs guys var tīrīt sevi atpakaļ uz augšu.
Ļaujiet man ieteikt, ka nevis anita + +, tā vietā mēs darām Anita izpaužas-
labi, kāpēc nav mēs ejam, lai neatkarīgi Anita tiek pavērsts un pēc tam darīt. tālāk?
Citiem vārdiem sakot, mēs ejam uz Ramon, kurš saimniecībā to 22,
un tad nākamais ir. it kā Anita būtu kopējot savu kreiso roku rādītāju.
Bet viņa negāja tālāk nekā Ramon jo mēs atradām 22.
Bet tas būtu ideja. Tagad tas ir dievs-šausmīgs haoss.
Godīgi, neviens nekad atcerēties šo sintaksi, un tā par laimi,
tas tiešām maz apzinātas-ak, tu faktiski nav redzēt to, ko es uzrakstīju.
Tas būtu vairāk pārliecinoša, ja jūs varētu. Voila!
>> Aiz ainas, man bija problēmas risināšanu šo ceļu.
Anita, spert šo soli pa kreisi,
pirmkārt, mēs iet uz adresi, Anita ir pavērsts
un kur viņa atradīs ne tikai N, ko mēs tikko pārbaudīta tikai salīdzināšanas,
bet jūs atradīsiet arī nākamais - šajā gadījumā,
Ramón kreisā roka norādot uz nākamo mezglu sarakstā.
Bet tas ir dievs-šausmīgs haoss, uz kuru es atsaucos iepriekš,
bet izrādās C ļauj mums vienkāršot šo.
Nevis rakstiski (* Anita), mēs varam vietā vienkārši uzrakstīt Anita-> N,
un tas ir tieši tas pats funkcionāli, bet tas ir daudz vairāk intuitīvi,
un tas ir daudz vairāk saskan ar attēlu, ka mēs esam bijuši zīmēšanas
visu šo laiku, izmantojot bultiņām.
>> Visbeidzot, ko mums vajag darīt beigās šo programmu?
Ir viens līnija kodu atlikuši.
Atgriešanās ko?
Nepatiesi, jo, ja mēs ar visu kamēr cilpa
un Anita ir, faktiski, nulle, tas nozīmē, ka viņa gāja visu ceļu līdz beigām saraksta
kur viņa bija pavērsts-Kāds ir Jūsu vārds atkal?
ARI. >> Ari kreisā roka, kas ir nulle.
Anita tagad nulle, un es saprotu, tu esi vienkārši stāv šeit neveikli aizmirstība
jo es esmu off uz monologs šeit,
bet mēs iesaistīt jūs atkal tikai brīdi.
Anita ir spēkā tajā brīdī stāsts, tāpēc kamēr cilpa izbeidz,
un mums ir jāatgriežas nepatiess, jo, ja viņa ieguva visu ceļu uz Ari s null pointers
tad tur bija neviens numurs, ka viņa meklēja sarakstā.
Mēs varam iztīrīt šo pārāk, bet tas ir diezgan laba īstenošana tad
par šķērsošana funkciju, atrast funkciju saistītajā sarakstā.
Tas joprojām lineāra meklēšanu, bet tas nav tik vienkārši, kā + + rādītājs
vai + + es mainīga, jo tagad mēs nevaram uzminēt
kur katrs no šiem mezgliem ir atmiņā.
Mums ir burtiski sekot taka rīvmaizes vai, precīzāk,
norādes, lai nokļūtu no viena mezgla uz otru.
>> Tagad pamēģināsim kādu citu. Anita, jūs vēlaties atgriezties šeit?
Kāpēc ne mēs ejam uz priekšu un piešķir vienu citu personu no auditorijas?
Malloc-kāda ir jūsu vārds? >> Rebecca.
Rebecca. Rebeka ir malloced no auditorijas,
un viņa tagad ir uzglabātu numuru 55.
Un pie rokas mērķis tagad ir Anita ievietot
Rebecca uz saistīts saraksts šeit tās atbilstošā vietā.
Nāc uz vairāk nekā šeit uz brīdi.
Man ir jādara kaut kas līdzīgs šim.
Man ir darīts mezglā *. Un kāda ir jūsu vārds atkal?
Rebecca. >> Rebeka, labi.
Rebecca izpaužas malloc (sizeof (mezgls)).
Tāpat kā mums ir piešķirti lietas, piemēram, studentiem un plauktiņš pagātnē,
mums ir nepieciešams lielumu mezglā, tāpēc tagad Rebecca
ir vērsta uz to, ko?
Rebeka ir divi lauki iekšpusē viņas, no kuriem viens ir 55.
Darīsim ko, Rebecca-> = 55.
Bet tad Rebecca-> nākamā būtu līdzīgu tiesības tagad, viņas roka ir sava veida, kas zina?
Tas norādot uz kādu atkritumu vērtībā, tad kāpēc ne labs pasākums
mēs vismaz izdarīt tā, ka kreisā roka ir tagad pie viņas sāniem.
Tagad Anita, ņemt to no šeit.
Jums ir Rebeka, kuriem ir piešķirtas.
Iet uz priekšu un atrast, kur mums vajadzētu likt Rebecca.
Labi, ļoti labi.
Labi, labi, un tagad mums nepieciešams, lai jūs sniegtu mazliet virzienā,
lai jūs esat sasniedzis Ari.
Viņa kreisā roka ir nulle, bet Rebeka nepārprotami pieder labi,
tā kā mēs ir mainīt šo saistīts saraksts
Lai ievietotu Rebecca atbilstošajā vietā?
Ja jūs varētu burtiski pārvietot cilvēku kreisās rokas ap kā nepieciešams,
mēs noteikt problēmu, ka veidā.
Labi, labi, un tikmēr, Rebecca kreisā roka ir tagad viņai blakus.
>> Tas bija pārāk viegli.
Pamēģināsim sadalot-we're gandrīz izdarīts, 20.
Labi, nāk uz augšu.
20 ir piešķirts, tāpēc ļaujiet man iet uz priekšu un saka atkal šeit
mēs esam tikai izdarīt mezglā * Saad.
Mums ir malloc (sizeof (mezgls)).
Mēs pēc tam darīt to pašu precīzu sintaksi, kā mēs darījām iepriekš par 20,
un es darīšu nākamo = null, un tagad tas ir līdz Anita
ievietot jūs vērā saistītā sarakstā, ja jūs varētu spēlēt ka tieši tādu pašu lomu.
Izpildīt.
Labi, labi.
Tagad domāju, ka uzmanīgi, pirms sākat pārvietojas kreisās rokas apkārt.
Jūs līdz šim ieguvuši visvairāk neērts loma šodien.
Kura rokas jāpārvieto vispirms?
Labi, pagaidiet, es esmu dzirdes daži nē s.
Ja daži ļaudīm būtu pieklājīgi gribētu, lai palīdzētu risināt ar neērtu situāciju šeit.
Kuras kreisā roka būtu jāatjaunina 1. varbūt? Yeah.
[Studentu] Saad s.
Labi, Saad s, kāpēc, lai gan?
[Dzirdams studentu reaģēšanas]
Labi, jo, ja mēs virzāmies-Kāds ir Jūsu vārds? >> Māršala.
Marshall, ja mēs pārvietot savu roku pirmajā leju uz null,
Tagad mēs esam burtiski bāreņiem četri cilvēki šajā sarakstā
jo viņš bija vienīgais, norādot uz Ramon un visiem pa kreisi,
tāpēc atjauninot šo rādītāju pirmais bija slikti.
Pieņemsim atsaukt to.
Labi, un tagad iet uz priekšu un pārvietot atbilstošu kreiso roku norādot uz Ramon.
Tas jūtas mazliet lieks.
Tagad tur ir divi cilvēki, kas norāda uz Ramon, bet tas ir jauki
jo tagad kā vēl mēs atjaunināt sarakstu?
Kāds cits puses ir, lai pārvietotos?
Teicami, tagad mēs esam zaudējuši jebkādu atmiņu?
Nē, tik labi, pieņemsim redzēt, ja mēs nevaram lauzt to vēl vienu reizi.
>> Mallocing pēdējo reizi, skaits 5.
Viss, kas muguras veidā, nāk uz leju.
Tas ir ļoti aizraujoši.
[Aplausi]
Kāds ir Jūsu vārds? >> Rons.
Ron, labi, jūs malloced kā 5 numuru.
Mēs esam tikko izpildīts kods, kas ir gandrīz identisks šos
tikai ar citu nosaukumu.
Teicami.
Tagad, Anita, veiksmi ievietojot skaits 5 uz sarakstu tagad.
Labi, un?
Teicami, tāpēc tas ir patiešām trešais no trim kopējām lietām.
Mums vispirms bija kāds beigās, Rebecca.
Tad mums bija kāds vidū.
Tagad mums ir kāds sākumā, un šajā piemērā,
Mums tagad bija aktualizēt Lucas pirmo reizi
jo pirmais elements sarakstā šobrīd ir norādīt uz jaunu mezglu,
kas, savukārt, ir vērsta uz mezglu skaits 9.
>> Tas bija ļoti neveikli demonstrācija, es esmu pārliecināts,
tāpēc liela kārtu aplausi šie puiši, ja jūs varētu.
Labi darīts.
Tas arī viss. Jūs varat saglabāt savu gabalu no papīra, kā maz atmiņas.
Izrādās, ka to izdarīt kodu
nav gluži tik vienkārši, kā tikai pārvietojas rokas ap
un norādot norādes pie dažādām lietām.
Bet saprast, ka tad, kad runa ir laiks, lai īstenotu kaut ko līdzīgu
saistīts saraksts vai tā variants, ja jums koncentrēties uz patiešām
šīs pamata pamati, uz kumosa lieluma problēmas, man ir izdomāt,
tas ir tas roku vai šo roku, saprotam, ka to, kas ir citādi diezgan sarežģīta programma
var, faktiski, ir jāsamazina līdz vienkāršiem celtniecības bloki, kā šis.
>> Paņemsim lietas sarežģītākas virzienā joprojām.
Mums tagad ir jēdziens par saistīts sarakstu.
Mums ir arī-pateicoties ierosinājumam muguras tur-divkārt saistīts saraksts,
kas izskatās gandrīz tāds pats, bet tagad mums ir divas norādes iekšpusē struct
nevis viens, un mēs varētu droši saucam šos norādes iepriekšējo un nākamo
vai pa kreisi vai pa labi, bet mēs, patiesībā, vajag divus no tiem.
Kods būtu nedaudz vairāk jāiesaistās.
Anita būtu jādara vairāk, šeit uz skatuves.
Bet mēs, protams, var īstenot šāda veida struktūru.
Runājot par darba laiku, lai gan, kāda būtu darbības laiks
Anita atrodot skaits n ir saistīts saraksts tagad?
Joprojām liela O no n, tāpēc nav labāks par lineāro meklēšanu.
Mēs nevaram darīt bināro meklēšanu, lai gan, atkal.
Kāpēc bija gadījums? Jūs nevarat lēkt apkārt.
Pat ja mēs acīmredzot redzēt visus cilvēkus uz skatuves,
un Anita varēja eyeballed to un sacīja: "Te ir saraksta vidū,"
viņa nezināja, ka viņa būtu datorprogramma
jo vienīgais, ko viņa bija slēdzeni uz sākumā scenārija
bija Lucas, kurš bija pirmais rādītājs.
Viņa būtu obligāti jāievēro šīs saites,
skaitot savu ceļu līdz viņa atrada aptuveni vidū,
un pat tad, viņa nav gatavojas zināt, kad viņa sasniedza vidū
ja vien viņa iet visu ceļu līdz beigām, lai noskaidrotu, cik daudz tur ir,
tad Backtracks, un tas arī būtu grūti, ja vien jums bija
divkārt saistīts saraksts kaut kāda.
>> Risināšanā dažas problēmas šodien, bet ieviešot citus.
Kas par citu datu struktūra pavisam?
Tas ir fotogrāfija no šajā Mather House paplātes,
un šajā gadījumā mums ir datu struktūra, mēs esam arī sava veida jau runā.
Mēs runājām par kaudze kontekstā atmiņu,
un tas ir sava veida apzināti nosaukta tāpēc kaudzīte atmiņas nosacījumiem
ir faktiski datu struktūra, kas ir vairāk un vairāk sīkumi kārtojumu uz augšu no tā.
Bet interesanta lieta par steku, kā tas ir patiesībā,
ir, ka tas ir īpašs datu struktūras.
Tas ir datu struktūra, kurā pirmais elements
ir pēdējais elements out.
Ja jums ir pirmās paplāte tiks likts uz steku,
Jūs esat būs diemžēl pēdējo paplāte jāizņem kaudze,
un tas nav vienmēr ir laba lieta.
Un otrādi, jūs varat domāt par to otrādi,
pēdējais, kas ir pirmā no.
>> Tagad, vai kāds scenāriji nāk prātā kur ar steku
datu struktūra, kurā jums ir, ka īpašums
no pēdējā, pirmais ārā, ir faktiski pārliecinoši?
Ir tas, ka laba lieta? Ir tā, ka slikti?
Tas noteikti slikti, ja paplātes nav visi vienādi
un viņi visi bija īpašas dažādas krāsas vai plauktiņš,
un krāsu vēlaties ir visu ceļu apakšā.
Protams, jūs nevarat saņemt, ka bez lielas piepūles.
Jums ir jāsāk no augšas un darbu savu ceļu uz leju.
Tāpat, ja jūs būtu viens no šiem fanu zēni
kurš gaida visu nakti mēģina iegūt iPhone un līniju līdz
vietā kā šī?
Vai tas nebūtu jauki, ja Apple veikalu
bija kaudze datu struktūra?
Yay? Nē?
Tas ir tikai labi cilvēki, kas parādās pēdējā iespējamā brīdī
un pēc tam saņemt noplūktas off rindā.
Un patiesībā, tas, ka man bija tik vēlme teikt rindā
ir faktiski saskan ar to, ko mēs varētu nosaukt šo veida datu struktūru,
viens patiesībā kur lai tas jautājums,
un jūs vēlaties viens no pirmajiem būt pirmais ārā
ja vien tādēļ, lai cilvēka godīgumu.
Mēs parasti saucam ka rinda datu struktūra.
>> Izrādās ne tikai saistībā sarakstos, mēs varam sākt izmantot šīs pašas idejas
un sākt jaunu un atšķirīgu veidu problēmu risinājumus.
Piemēram, gadījumā, skursteņus, mēs varētu pārstāvēt kaudze
izmantojot datu struktūru, piemēram, tas, es ierosinu.
Šajā gadījumā, es esmu paziņoja struct, un es esmu teica iekšā par šo struktūru
ir skaitļu masīvs, un tad mainīgo sauc lielumu,
un es esmu dodas uz zvanu šī lieta kaudze.
Tagad, kāpēc tas faktiski strādā?
Attiecībā uz skursteņus, es varētu izdarīt to efektīvi uz ekrāna kā masīva.
Te ir mana kaudze. Tie ir mani numuri.
Un mēs izdarīt tos kā šis, tas, tas, tas, tas.
Un tad man ir daži citi dati locekli šeit,
ko sauc izmēra, tāpēc tas ir izmērs, un tas ir skaitļi,
un kolektīvi, viss iPad šeit pārstāv vienu steka struktūru.
Tagad, pēc noklusējuma, izmērs ir iespējams got būt inicializēts līdz 0,
un kas ir iekšā no masīva skaitļu sākotnēji
kad es pirmo reizi piešķir masīvs?
Atkritumu. Kas to lai zina? Un tas nav tiešām jautājums.
Tas nav svarīgi, ja tas ir 1, 2, 3, 4, 5, pilnīgi nejauši
pēc neveiksmes glabājas manā struktūrā, jo tik ilgi, kamēr es zinu, ka no lieluma kaudze
ir 0, tad es zinu programmatiski, nav apskatīt kādu no masīva elementiem.
Tas nav svarīgi, kas ir tur.
Vai nav skatīties uz tiem, kā tas būtu saistība ar izmēru no 0.
>> Bet pieņemsim, ka tagad es iet uz priekšu un ievietot kaut uz skursteņa.
Es gribu ievietot numuru 5, tāpēc man skaits 5 šeit,
un tad ko es varu nolikt šeit?
Tagad es tiešām likts uz leju 1 uz izmēru,
un tagad kaudze ir 1 izmēru.
Ko darīt, ja es iet uz priekšu un ievietojiet numuru, teiksim, 7 nākamais?
Šis tad izpaužas atjaunošana līdz 2, un tad mēs darīsim 9,
un tad tas izpaužas atjaunošana līdz 3.
Bet interesanta iezīme tagad šī kaudze ir, ka
Es esmu vajadzēja noņemt kurš no šiem elementiem, ja es gribu, lai pop
kaut nost no skursteņa, tā teikt?
9 būs pirmā lieta iet.
Kā būtu aina mainīties, ja es gribu, lai pop elementu pie skursteņa,
Daudz kā paplāti Mather?
Yeah >> [Studentu] Iestatīt izmēru līdz 2..
Tieši tā, visi man ir iestatīts izmēru uz 2, un ko man darīt ar masīva?
Man nav darīt jebko.
Es varētu, tikai lai anālais, ielieciet 0 tur vai -1 vai kaut ko, lai apzīmētu
ka tas nav legit vērtība, bet tas nav svarīgi, jo
Es varu ierakstīt ārpus masīva pati cik ilgi tas ir
tāpēc, ka es zinu tikai apskatīt pirmo divu elementu šajā masīvā.
Tagad, ja es eju un pievieno numuru 8, lai šī masīva, kā tas attēls mainās nākamo?
Tas kļūst 8, un tas kļūst 3.
Es esmu griešana dažas stūriem šeit.
Tagad mums ir 5, 7, 8, un mēs esam atpakaļ uz izmēru gada 3.
Tas ir diezgan vienkārši īstenot,
bet, kad mēs gatavojamies nožēlojam šo dizaina lēmumu?
Kad, lietas sāk iet ļoti, ļoti nepareizi? Yeah.
[Dzirdams studentu reaģēšanas]
Ja jūs vēlaties doties atpakaļ un iegūt pirmo elementu jūs likts collas
>> Izrādās šeit pat kaudze ir masīvs zem motora pārsega,
šie datu struktūras mēs esam sākuši runāt par ir arī parasti sauc par
abstraktas datu struktūras, kurā kā viņi īsteno
ir pilnīgi papildus punktu.
Datu struktūra, piemēram, kaudze ir paredzēts pievienot atbalstu
darbības, piemēram, push, kas nospiež ar paplāti uz steku,
un pop, kas noņem elements no skursteņiem, un tas arī viss.
Ja tu būtu, lai lejupielādētu kāds cits kods, kas jau īstenoti
Šī lieta, ko sauc kaudze, kas personai būtu rakstīts
tikai divas funkcijas, lai jūs, push un pop, kuru vienīgais mērķis dzīvē
būtu darīt tieši to.
Jūs vai viņam vai viņai kas īsteno šo programmu
būtu bijis pilnīgi viens, lai izlemtu, kā īstenot
semantiku stumšana un popping zem pārsega
vai funkcionalitāti stumšanas un popping.
Un man ir devuši nedaudz tuvredzīgs lēmums šeit
īstenojot savu kaudze ar šo vienkāršo datu struktūru kāpēc?
Kad šo datu struktūru pārtraukums?
Kurā brīdī man atgriezties kļūda, kad lietotājs pieprasa push, piemēram?
[Studentu] Ja tur nav vairāk vietas.
Tieši tā, ja tur nav vairāk vietas, ja es esmu pārsniedzis jaudu,
kas ir visi vāciņi, jo tas liecina, ka tas ir sava veida pasaules nemainīgs.
Nu, tad es esmu tikai gatavojas teikt, "Atvainojiet, es nevaru push citu vērtību
uz skursteņa, "līdzīgi kā Mather.
>> Kādā brīdī, viņi gatavojas hit top daļu no šī mazā kabinetā.
Tur nav vairāk vietas vai jaudas kaudze, kurā brīdī tur ir dažas kļūdas veida.
Viņiem ir likts elementu kaut kur citur, paplātes kaut kur citur,
vai nekur vispār.
Tagad, ar rindā, mēs varētu īstenot to nedaudz savādāk.
Rinda ir nedaudz atšķirīga, ka zem motora pārsega, to var īstenot
kā masīvu, bet kāpēc, šajā gadījumā, es esmu ierosinot
lai arī ir galvas elements, kas veido galvu no saraksta,
priekšējā saraksta, pirmais cilvēks rindā pie Apple veikala, papildus izmēru?
Kāpēc man ir nepieciešams papildu gabals datu šeit?
Domāju, ka atpakaļ uz kādi skaitļi ir
ja es esmu sagatavots to šādi.
Pieņemu, ka tas ir tagad rinda nevis kaudze,
ir-tāpat kā Apple veikals-rindā atšķirība ir taisnīga.
Pirmais cilvēks rindā sākumā saraksta, šajā gadījumā 5 numurs,
viņš vai viņa būs let uz veikalu vispirms.
Darīsim to.
Pieņemsim, ka tas ir valsts mana rindā šajā brīdī, un tagad Apple veikalu
atver un pirmais cilvēks, skaits 5, vada iekšā veikalā.
Kā mainīt priekšstatu, ka šobrīd man ir de-rindā pirmā persona
priekšā līnijas?
Kas ir, ka >> [Studentu]? Maiņa rindā.
Mainīt galvu, tāpēc 5 pazūd.
Patiesībā, tas ir, it kā-kā vislabāk to darīt?
Patiesībā, tas ir, it kā tas puisis pazūd.
Kas būtu skaits 7 darīt faktisko veikalā?
Viņi veikt lielu soli uz priekšu.
>> Bet tas, ko mēs esam ieradušies novērtēt, kad runa ir masīvi
un pārvietojas lietas apkārt?
Tas ir sava veida atkritumu savu laiku, vai ne?
Kāpēc jums ir jābūt tik anālais, lai būtu pirmā persona
sākumā līnijas pie fiziski sākuma rieciens atmiņas?
Tas ir pilnīgi nevajadzīga. Kāpēc?
Kas varētu Es tikai atceros, nevis >> [dzirdams studentu reaģēšanas]?
Tieši tā, es varētu tikai atcerēties šo papildu datu loceklis galvu
ka tagad saraksta galva vairs 0, kas tas bija pirms brīža.
Tagad tas patiesībā numurs 1. Tādā veidā, man nedaudz optimizāciju.
Tikai tāpēc, ka es esmu de-rindā kāds no rindā sākumā līnijas pie Apple veikala
nenozīmē ikvienam ir novirzīt, kas atsaukšana ir lineāra operācija.
Es varu vietā pavadīt pastāvīgu laiku tikai
un sasniegt tad daudz ātrāku reakciju.
Bet cenu es esmu maksājot ir ko iegūtu, ka papildu sniegumu
un kam nav novirzīt visiem?
Yeah >> [dzirdams studentu reaģēšanas].
Var pievienot vairāk cilvēku, labi, ka problēma ir perpendikulāras
ar to, ka mēs esam ne novirzot cilvēku apkārt.
Tas joprojām masīvs, tāpēc, vai mēs novirzīt ikvienam, vai ne-
Ak, es saprotu, ko tu domā, labi.
Patiesībā, es piekrītu, ko jūs sakāt, ka tas ir gandrīz, it kā
mēs tagad nekad gatavojas izmantot uzsākšanu šī masīva vairs
jo, ja es noņemt 5, tad es noņemt 7.
Bet es tikai nodot cilvēkus uz labo pusi.
>> Tā uzskata, piemēram, es esmu izšķērdēt telpu, un beidzot mana rinda sadalās neko,
lai mēs varētu vienkārši ir cilvēki wraparound,
un mēs varētu domāt par šo masīva tiešām kā sava veida apļveida struktūru,
bet mēs izmantojam kāda operatoru C darīt, ka veida wraparound?
[Dzirdams studentu reaģēšanas] >> modulo operators.
Tas būtu mazliet kaitinošas ir domāt jūs darīt wraparound,
bet mēs varētu darīt to, un mēs varētu sākt liekot cilvēkus, ko izmanto, lai būtu priekšā no līnijas,
bet mēs tikai atcerieties šo galvu mainīgo kurš faktiskā vadītāja līnijas patiesībā ir.
Ko darīt, ja tā vietā, mūsu mērķis visbeidzot, lai gan,
bija meklēt numurus, kā mēs to darījām šeit uz skatuves ar Anita,
bet mēs patiešām vēlamies labāko no visām šīm pasaulēm?
Mēs vēlamies izsmalcinātāka nekā masīvs ļauj
jo mēs vēlamies spēja dinamiski augt datu struktūru.
Bet mēs negribam, lai būtu spiesta kaut kas mums norādīja
Pirmajā lekcijā nebija optimāls algoritms,
ka lineārās meklēšanu.
Izrādās, ka jūs varat, faktiski, panāktu
vai vismaz tuvu pastāvīgu laiku, kad kāds, piemēram, Anita,
ja viņa konfigurē savu datu struktūru nevar būt saistīts saraksts,
nebūt kaudze, nevis būt rinda, varētu, faktiski,
nākt klajā ar datu struktūru, kas ļauj viņai meklēt lietas,
pat vārdiem, ne tikai cipari, ko mēs sauksim pastāvīgu laiku.
>> Un patiesībā, raugoties nākotnē, viens no šīs klases psets gandrīz vienmēr
ieviešana Pareizrakstība, kuru
mēs jums atkal dažas 150,000 angļu vārdiem un mērķis ir
slodze tiem atmiņā un ātri jāspēj atbildēt uz jautājumiem par formu
ir šis vārds uzrakstīts pareizi?
Un tas tiešām sūkāt ja Jums bija atkārtot, izmantojot visus 150,000 vārdiem atbildēt, ka.
Bet, patiesībā, mēs redzam, ka mēs varam darīt to ļoti, ļoti ātri laikā.
Un tas notiek, lai iesaistītu īstenošanas kaut ko sauc hash tabulu,
un pat ja pirmajā mirklī šo lietu sauc hash tabulu gatavojas
ļaujiet mums sasniegt šos super ātrās reaģēšanas laiks,
izrādās, ka tur ir patiesībā problēma.
Kad runa ir laiks, lai īstenotu šo lietu sauc, atkal, es esmu darot to vēlreiz.
Es esmu tikai viens šeit.
Kad runa ir laiks, lai īstenotu šo lietu sauc hash tabulu,
mēs esam nāksies pieņemt lēmumu.
Cik liels tas lieta tiešām ir?
Un, kad mēs sākam ievietojot skaitļus šajā hash tabulā,
Kā mēs glabāt tos tādā veidā
ka mēs varam saņemt tos atpakaļ, kā ātri, kā mēs saņēmām tos?
Bet mēs redzēsim pirms ilgi, ka šis jautājums
Kad visi dzimšanas diena ir savā klasē būs diezgan piederīgs.
Izrādās, ka šajā telpā, mēs esam ieguvuši dažus simtus cilvēku,
tāpēc izredzes, ka divi no mums ir pati dzimšanas diena ir iespējams, ir diezgan augsts.
Ko darīt, ja tur bija tikai 40 no mums šajā telpā?
Kādas ir par diviem cilvēkiem, kuriem ir vienāds dzimšanas izredzes?
[Studenti] Vairāk nekā 50%.
Jā, vairāk nekā 50%. Patiesībā, es pat cēla diagrammu.
Izrādās-un tas ir tiešām tikai ložņāt preview
ja tur ir tikai 58 no mums šajā telpā, varbūtība gada 2 no mums
ar tādu pašu dzimšanas diena ir ļoti augsts, gandrīz 100%,
un kas notiek, lai radītu veselu ķekars sāp par mums trešdien.
>> Ar to teica, pieņemsim atliek šeit. Mēs redzēt jūs trešdien.
[Aplausi]
[CS50.TV]