[Powered by Google Translate] [Nedēļa 6, Turpinājums]
[David J. Malan] [Hārvarda]
[Tas ir CS50.] [CS50.TV]
Tas ir CS50 un tas ir beigu 6 nedēļas.
Tātad CS50x, viens no Hārvardas pirmajiem kursiem, kas iesaistītas EDX iniciatīvā
tiešām debitēja pagājušajā pirmdienā.
Ja jūs vēlētos, lai iegūtu ieskatu par to, ko citiem internetā
tagad pēc kopā ar, jūs varat doties uz x.cs50.net.
Kas būs novirzīt jūs uz attiecīgā vietā edx.org,
kas bija, kad šo un citiem kursiem no MIT un Berklijā tagad dzīvot.
Jums ir pierakstīties uz kontu, jūs atradīsiet, ka materiāls ir lielā mērā tas pats
kā jūs esat bijusi šī semestrī, gan dažas kavējas nedēļu, kā mēs viss gatavs.
Bet ko studenti CS50x tagad redzēt ir saskarne gluži kā šis.
Tas, piemēram, ir Zamyla vadot walkthrough par problēmu kopumu 0.
Pēc piesakoties uz edx.org, CS50x students redz lietas veidu
jūs varētu sagaidīt, lai redzētu kursos: lekciju par pirmdienā,
lekcija trešdien, dažādi šorti, problēma komplekti, walkthroughs, PDF.
Turklāt, kā jūs redzēt šeit, mašīntulkojumi
no angļu stenogrammas uz ķīniešu, japāņu, spāņu, itāļu,
un viss ķekars citu valodu, kas noteikti būs nepilnīga
kā mēs roll tos programmatiski, izmantojot kaut ko sauc API,
vai lietojumprogrammu saskarne, no Google
kas ļauj mums, lai pārvērstu angļu šīm citām valodām.
Bet, pateicoties brīnišķīgo garu dažiem simtiem plus brīvprātīgajiem,
izlases cilvēki internetā, kuri ir laipni piedāvāja iesaistīties
šajā projektā, mēs pakāpeniski uzlabojot šo tulkojumu
, ņemot cilvēki labotu kļūdas, ka mūsu datori ir izgatavoti.
>> Tātad izrādās, mums bija vēl dažas studentu parādās pirmdien, nekā mēs sākotnēji gaidīts.
Patiesībā, tagad CS50x ir 100,000 cilvēki pēc kopā mājās.
Tātad saproti, jūs esat daļa no šī inaugurācijas klase padarot šo kursu datorzinātnēs
izglītību kopumā, plašāk, pieejamāku.
Un realitāte ir tagad, ar dažiem no šiem masveida tiešsaistes kursu,
viņi visi sāk ar šo ļoti liela skaita, kā mēs, šķiet, ir darīts šeit.
Bet mērķis, galu galā, lai CS50x ir patiešām iegūt tik daudz cilvēku uz finiša līniju, kā iespējams.
Pēc konstrukcijas, CS50x gatavojas piedāvāt no šīs pagātnes pirmdiena
visu ceļu cauri 15 aprīlis 2013, lai ļaudīm, kas ir skolas saistības citur,
darbs, ģimene, citi konflikti un tamlīdzīgi, ir nedaudz lielāka elastība
ar kuru nodoties šo kursu, kas, pietiek pateikt,
ir diezgan ambiciozi darīts, ja vien gaitā tikai trīs mēnešus parastā semestrī.
Bet šie skolēni būs novērst to pašu problēmu kopas, skatot pašu saturu,
kam ir piekļuve tām pašām šorti un tamlīdzīgi.
Lai saprastu, ka mēs visi esam patiesi šajā kopā.
Un viens no gala mērķiem CS50x ir ne tikai, lai saņemtu tik daudz ļaudīm
uz finiša līnijas un dot viņiem šo jauniegūto izpratni par datorzinātnes
un programmēšanas bet arī tos ir šo kopīgo pieredzi.
Viens no noteicošajām iezīmēm no 50 uz pilsētiņu, mēs ceram,
ir bijusi šāda veida komunālo pieredzi, lai labāk vai sliktāk, dažkārt
bet kam šie cilvēki vērsties pa kreisi un pa labi,
un biroja stundas un hackathon un taisnīga.
Tas nedaudz grūtāk darīt, ka cilvēks ar ļaudīm tiešsaistē,
bet CS50x noslēgsies aprīlī ar pirmo kādreiz CS50 Expo,
kas būs tiešsaistes pielāgošanu mūsu ideju par patiesā
ja šie studenti tūkstošiem visi tiks aicināti iesniegt 1 - līdz 2 minūšu video,
nu to galīgās projekta vai video no tiem screencast vicinot sveiki
un runā par savu projektu un demoing to,
līdzīgi saviem priekšgājējiem ir darīts šeit Campus gadatirgū,
lai līdz semestra beigām, cerība ir, lai būtu pasaules izstādi
no CS50x studentu gala projektiem, līdzīgi tas, kas jūs sagaida šā gada decembrī šeit par Campus.
Tā vairāk par to nākamajos mēnešos.
>> Ar 100,000 studentu, lai gan, nāk par nepieciešamību vēl dažus SI.
Ņemot vērā, ka jūs guys ir degošs taka šeit un ņemot CS50
vairākas nedēļas pirms materiāla izmantošanas atklājama par EDX ļaudīm,
saproti, mēs labprāt vēlētos, lai iesaistītu jo daudzi no mūsu pašu studentu iespējas šajā iniciatīvā,
gan semestra laikā, kā arī šajā ziemā, un tas nāk pavasarī.
Tātad, ja jūs vēlaties iesaistīties CS50x,
īpaši pievienojās uz CS50x diskutēt, EDX versija CS50 diskutēt,
kuru daudzi no jums ir bijis, izmantojot uz Campus, tiešsaistes dēļa,
lūdzu galvu uz šo URL, dodiet mums zināt, kas jūs esat,
jo mēs labprāt veidot studentu un mācībspēku komanda un fakultātē gan
par Campus kuri vienkārši spēlē kopā un palīdzot.
Un kad viņi redz jautājumu, kas ir pazīstami ar tiem,
Jūs dzirdat students ziņošanas dažas bug kaut kas tur kādu valsti internetā,
un ka gredzeni bell, jo jums arī bija, ka pašu jautājumu
Jūsu d-zālē, kādu laiku atpakaļ, cerams tad jūs varat piebalsot un dalīties ar savu pieredzi.
Tāpēc, lūdzu, piedalīties, ja jūs vēlētos.
>> Datorzinību kursi Hārvardas ir mazliet tradīcijas,
CS50 starp tiem, par kuru daži apģērbu, dažas drēbes, ka jūs varat valkāt ar lepnumu
pēc semestra beigās, sakot diezgan lepni, ka esat pabeidzis CS50
un ņēma CS50 un tamlīdzīgi, un mēs vienmēr cenšamies iesaistīt studentus
Šajā procesā pēc iespējas vairāk, kad mēs aicinām,
ap šo laiku semestra studenti iesniegt projektus
izmantojot Photoshop, vai kāds instrumentu izvēle vēlaties izmantot
ja tu esi dizainers, iesniegt dizainu T-krekli un sporta krekli
un lietussargi un maz bandanas suņiem mums tagad ir un tamlīdzīgi.
Un viss ir, tad - uzvarētāji katru gadu tam tiek izstādīti
par kursu mājas lapā store.cs50.net.
Viss ir pārdots izmaksās tur, bet mājas lapā tikai iet sevi
un ļauj cilvēkiem izvēlēties krāsas un dizainu, kas viņiem patīk.
Tāpēc es domāju, ka mēs gribētu tikai dalīties dažas no pagājušā gada dizainu
kas bija mājas lapā turklāt šo vienu šeit, kas ir ikgadēja tradīcija.
"Katru dienu es esmu SEG Faultn" bija viens no apsvērumiem pagājušajā gadā,
kas joprojām ir pieejams tur absolventiem.
Mums bija šo vienu, "CS50, reģistrēts 1989."
Viens no mūsu Bowdens, Robs, bija ļoti populāra pagājušā gadā.
"Komandas Bowden" piedzima, šis dizains tika iesniegts, starp top pārdevējiem.
Kā tas bija šo vienu šeit. Daudzi cilvēki bija "Bowden Fever" saskaņā ar pārdošanas baļķiem.
Saprast, ka tagad varētu būt jūsu dizaina tur, līdzi internetā.
Sīkāka informācija par šo in nākamo problēmu kopas nākt.
>> Vēl viens instruments: jūs esat bijusi zināma ekspozīciju un cerams tagad
kādu praktisku pieredzi ar gdb,
kas ir, protams, atkļūdotājs un ļauj manipulēt
Jūsu programma pie diezgan zemā līmenī, darot to, ko veida lietas?
Kāda Gdb jums darīt?
Yeah? Dodiet man kaut ko. [Studentu atbilde, nesaprotami]
Good. Solis funkcija, tāpēc jums nav vienkārši ir veids palaistu
un ir programma izpūš kopumā, izdrukāt lietas standarta produkciju.
Drīzāk, jūs varat soli caur to pozīcijai, nu rakstīt nākamo
lai iet pozīcijai pa līniju vai līmenī, kā nodoties funkciju, parasti viens, ka jūs wrote.
Ko vēl Gdb jums darīt? Yeah? [Studentu atbilde, nesaprotami]
Drukāt mainīgos. Tātad, ja jūs vēlaties darīt nedaudz pašanalīze iekšpusē jūsu programmā
bez ķerties pie rakstīšanas printf paziņojumus visas vietas,
Jūs varat vienkārši izdrukāt mainīgo vai parādīt mainīgo.
Ko vēl jūs varat darīt ar atkļūdotājs kā gdb?
[Studentu atbilde, nesaprotami]
Tieši tā. Jūs varat iestatīt pārtraukumpunktus, jūs varat teikt break izpildi
pie galvenās funkcijas vai foo funkciju.
Jūs varat teikt, break izpildi pie 123 līnijas.
Un kontrolpunkti ir ļoti jaudīga tehnika
jo, ja jums ir vispārēju sajūtu kur jūsu problēma
iespējams, ir, jums nav jātērē laiks pastiprināšanu, izmantojot programmas kopumā.
Jūs varat būtiski lēkt tieši tur un tad sāciet rakstīt -
pastiprināšanu caur to ar soli vai nākamo vai līdzīgi.
Bet ar kaut ko līdzīgu gdb nozveju, ka tas palīdz jums, cilvēku,
atrast savas problēmas un atrast savu bugs.
Tas ne vienmēr atrast viņiem tik daudz par jums.
>> Tāpēc mēs iepazīstināja citu dienu style50, kas ir īss komandrindas rīks
kas mēģina Stylize savu kodu nedaudz vairāk tīri nekā jums, cilvēku, varētu būt izdarīts.
Bet tas arī ir patiešām vienkārši estētisku lieta.
Bet izrādās, tur ir šis cits rīks sauc Valgrind kas ir nedaudz vairāk arcane izmantot.
Tās produkcija ir atrociously mistisks pirmā acu uzmetiena.
Bet tas ir lieliski noderīgi, jo īpaši tagad, ka mēs esam pie daļu no termiņa
kur jūs sāk izmantot malloc un dinamisko atmiņas sadalījumu.
Lietas var iet tiešām, tiešām nepareizi ātri.
Jo, ja esat aizmirsis, lai atbrīvotu savu atmiņu, vai jūs dereference kādu NULL rādītājs,
vai jūs dereference kādu atkritumu rādītāju, kas ir parasti simptoms, kas izraisa?
SEG vaina. Un jūs saņemsiet šo fundamentālo failu kādu skaita kilobaiti vai megabaitiem
kas pārstāv valsti no jūsu programmas atmiņā, kad tas avarēja,
bet jūsu programma galu galā SEG kļūdas, segmentēšanas vaina,
kas nozīmē, kaut kas slikts noticis gandrīz vienmēr ir saistīta
uz atmiņas saistītas kļūda, ka jūs veicāt kaut kur.
Tātad Valgrind palīdz atrast lietas, kā šis.
Tas ir instruments, kas jūs izmantojat, piemēram gdb, kad esat apkopojusi savu programmu,
bet nevis palaist savu programmu tieši, palaižot Valgrind
un jums iet uz to savu programmu, tāpat kā jūs darīt ar gdb.
Tagad, izmantošana, lai iegūtu labāko veida produkciju,
ir diezgan garš, tāpēc tieši tur novietotas uz ekrāna jūs redzēsiet Valgrind-V.
"-V" gandrīz visur nozīmē runīgs, ja jūs izmantojat programmas uz Linux datorā.
Tātad tas nozīmē, izspļaut vairāk datu nekā jūs varētu pēc noklusējuma.
"- Noplūde pārbaudīt = pilns." Tas ir vienkārši sakot čeku par visiem iespējamiem atmiņas noplūdes,
kļūdas, kas man varētu būt veikti. Arī tas ir kopīgs paradigma ar Linux programmām.
Parasti, ja jums ir komandrindas argumentu, ka tas "slēdzis",
kas ir paredzēts, lai mainītu programmas uzvedību, un tas ir viens burts,
tas ir-pret, bet, ja tas ir ieslēgts, tikai ar dizainu programmētājs,
ir pilna vārdu vai vārdu sērija, komandrindas arguments sākas ar -.
Šie ir tikai cilvēka konvencijas, bet jūs redzēsiet tos aizvien.
Un tad, beidzot, "a.out" ir patvaļīgs nosaukums programmas šajā piemērā.
Un šeit ir daži pārstāvis produkciju.
>> Pirms mēs apskatīt to, kas varētu nozīmēt, ļaujiet man iet vairāk nekā uz nelielā koda nekā šeit.
Un ļaujiet man pāriet šis no tā, Drīzumā,
un pieņemsim to apskatīt memory.c, kas šajā īsajā piemērs šeit.
Tāpēc šajā programmā, ļaujiet man tuvinātu funkcijām un jautājumiem.
Mums ir funkcija galvenais, kas prasa funkciju, F,
un tad ko tas f turpināt darīt, jo nedaudz tehniskajā angļu valodā?
Kāda f turpināt darīt?
Kā par Es sāktu ar 20 līniju, un zvaigzne atrašanās nav svarīgi,
bet es ņemšu tikai jāsaskan šeit ar pēdējo lekciju.
Kas līnija 20 darīt mums? Kreisajā pusē. Mēs sadalīt tālāk.
Int * x: ko tas dara?
Labi. Tas atzīst rādītāju, un tagad būsim vēl vairāk tehniska.
Ko tas nozīmē, ļoti konkrēti, atzīt rādītāju? Kāds cits?
Yeah? [Studentu atbilde, nesaprotami] Pārāk tālu.
Tātad jūs lasāt uz labajā pusē vienādības zīmi.
Pieņemsim koncentrēties tikai uz kreisi, tikai uz int * x.
Tas "deklarēt" rādītāju, bet tagad pieņemsim ienirt dziļāk šai definīcijai.
Ko tas konkrēti, tehniski nozīmē? Yeah?
[Studentu atbilde, nesaprotami]
Labi. Tas ir gatavojas saglabāt adresi atmiņā.
Good. Un pieņemsim šo vienu soli tālāk, tas ir atzīta par mainīgo x, kas ir 32 biti.
Un es zinu, tas ir 32 biti, jo -?
Tas nav tāpēc, ka tas ir int, jo tas ir rādītājs šajā gadījumā.
Sakritība, ka tas ir viens un tas pats ar int,
bet fakts, ka tur ir zvaigzne tur nozīmē tas ir rādītājs
un iekārtas, kā ar daudziem datoriem, bet ne visi, norādes ir 32 biti.
Uz vairāk mūsdienu aparatūru, tāpat vēlāk Mac, jaunākās datoriem, jums varētu būt 64-bit norādes,
bet ierīci, šīs lietas ir 32 biti.
Tāpēc mēs standartizēt to. Konkrētāk, stāsts iet šādi:
Mēs "deklarēt" rādītāju, ko tas nozīmē?
Mēs sagatavojam uzglabāt atmiņas adresi.
Ko tas nozīmē?
Mēs izveidot mainīgo sauc x, kas aizņem 32 bitus
ka drīz uzglabāt adresi veselam skaitlim.
Un tas ir iespējams, apmēram tikpat precīzi kā mēs varam iegūt.
Tas ir jauki virzās uz priekšu, lai vienkāršotu pasauli un tikai teikt atzīt rādītāju sauc x.
Atzīt rādītāju, bet saprast un saprast, kas patiesībā notiek
pat tikai tajās nedaudzajās rakstzīmes.
>> Tagad, šis viens ir gandrīz mazliet vieglāk, pat ja tas ir ilgāks izpausme.
Kas tad ir šī dara, ka ir iezīmēts tagad: "malloc (10 * sizeof (int));" Jā?
[Studentu atbilde, nesaprotami]
Good. Un es ņemšu to tur. Tas piešķirot rieciens atmiņas desmit integers.
Un tagad pieņemsim pikējošais nedaudz dziļāk, tas ir piešķirot rieciens atmiņas desmit integers.
Kas ir malloc tam atgriežas?
Adrese ka rieciens, vai, konkrētāk, adrese pirmās baits šī rieciens.
Kā tad es esmu, programmētājs, kas zina, kur tas rieciens atmiņas galiem?
Es zinu, ka tas ir blakus. Malloc, pēc definīcijas, sniegs jums blakusesošo rieciens atmiņas.
Nav spraugu tajā. Jums ir pieeja katru baitu šajā rieciens,
atpakaļ atpakaļ uz muguras, bet kā es varu zināt, kur šī rieciens atmiņas gals ir?
Kad jūs izmantot malloc? [Studentu atbilde, nesaprotami] Laba.
Jums nav. Jums ir jāatceras.
Man ir jāatceras, ka es izmantoti vērtību 10, un man nav pat šķiet, ir izdarīts, ka šeit.
Bet pienākums ir pilnīgi par mani. Strlen, ko mēs esam kļuvuši nedaudz atkarīga virknes,
strādā tikai tāpēc, ka šīs konvencijas, kam \ 0
vai šis īpašais Nul raksturs, NUL, beigās virknes.
Tas nenozīmē, ka tur, lai tikai patvaļīgi gabalos atmiņas.
Tas ir atkarīgs no jums. Tātad 20 līnijas, tad, piešķir rieciens atmiņas
kas var uzglabāt 10 naturālus skaitļus, un tas saglabā adresi pirmo baitu
Šī rieciens atmiņas mainīgo sauc x.
ERGO, kas ir rādītājs. Tātad 21 līnija, diemžēl, bija kļūda.
Bet vispirms, kas ir tā dara? Tā saka veikalu pie 10 vietā, indeksē 0,
no atmiņas rieciens sauc x vērtība 0.
>> Tāpēc pamanīt pāris lietas notiek.
Pat ja x ir rādītājs, atceros no pāris nedēļas atpakaļ
ka jūs joprojām varat izmantot masīvu stila kvadrātiekava notācija.
Jo tas tiešām īstermiņa roku nošu par daudz noslēpumains izskata šautriņu aritmētika.
kur mēs varētu darīt kaut kas līdzīgs šim: Veikt adrese X, pārvietot 10 plankumi pāri,
tad iet tur, lai kāds adrese ir saglabāta šajā vietā.
Bet godīgi sakot, tas ir tikai šausmīgs lasīt un iegūt apmierināti ar.
Tātad pasaule parasti izmanto kvadrātiekavas tikai tāpēc, ka tas ir tik daudz cilvēku draudzīgu lasīt.
Bet tas, ko īsti notiek zem pārsega;
x ir adrese, nevis masīvs, per se.
Tātad šis ir uzglabātu 0 pie in x 10 vietā.
Kāpēc tas ir slikti? Yeah?
[Studentu atbilde, nesaprotami] Tieši tā.
Mēs tikai piešķirti 10 Ints, bet mēs paļaujamies no 0 plānojot C,
tāpēc jums ir piekļuve 0 1 2 3 4 5 6 7 8 9, bet ne 10.
Tātad vai nu programma ir gatavojas SEG vaina vai tā nav.
Bet mēs īsti nezinām, tas ir sava veida nondeterministic uzvedību.
Tas patiešām ir atkarīgs no tā, vai mēs laimīgs.
Ja izrādās, ka operētājsistēma nav prātā, ja es izmantot šo papildu baitu,
pat ja tā nav devusi to uz mani, mana programma varētu crash.
Tas ir neapstrādātas, tas ir bagijs, bet jūs nevarēsiet redzēt, ka simptoms,
vai jūs varētu redzēt to tikai reizi brītiņa.
Bet realitāte ir tāda, ka kļūda ir, faktiski, tur.
Un tas ir patiešām sarežģīti, ja jūs esat uzrakstījis programmu, kas jūs vēlaties būt pareizs,
ka esat pārdevis, ka cilvēki izmanto, ka katru reizi brītiņa avārijās programmu
jo, protams, tas nav labi. Patiesībā, ja jums ir Android tālruni vai iPhone
un jums lejupielādēt progr šajās dienās, ja jūs esat kādreiz bija app vienkārši atmest,
visi pēkšņi tā pazūd, tas gandrīz vienmēr rezultāts kaut atmiņas saistītu jautājumu,
kuru programmētājs ieskrūvē augšu un dereferenced rādītāju
ka viņš vai viņa nedrīkst būt, un par iOS vai Android rezultāts ir tikai nogalināt programmu vispār
nevis riska nenoteiktu uzvedību vai kādu drošības kompromisu veida.
>> Ir viena cita kļūda šajā programmā turklāt šo vienu.
Kas vēl man ieskrūvē šajā programmā?
Man nav praktizēta, ko es esmu sludināja. Yeah?
[Studentu atbilde, nesaprotami] Laba.
Man nav atbrīvojušies atmiņu. Tāpēc īkšķis tagad
ir jābūt jebkurā laikā jūs aicinu malloc, jums ir zvanīt bez kad tas ir paveikts, izmantojot šo atmiņu.
Tagad, kad es gribu, lai atbrīvotu šo atmiņu?
Droši vien, pieņemot, ka tas pirmajā rindā bija pareizs, es gribētu to darīt šeit.
Tā kā es nevarēju, piemēram, darīt to šeit. Kāpēc?
Tikai no jomas. Tātad, pat ja mēs runājam par norādes,
tas ir nedēļa 2 vai 3 jautājums, kur x ir tikai joma iekšpusē cirtaini bikšturi, kur tas tika pasludināts.
Tātad, jūs noteikti nevar atbrīvot to tur. Mana vienīgā iespēja, lai atbrīvotu to ir aptuveni pēc 21 līniju.
Tas ir diezgan vienkārša programma, tas bija diezgan viegli, kad jūs veida ietin savu prātu
ap ko programma dara, kur kļūdas bija.
Un pat ja jūs neredzat to sākumā, cerams tas maz skaidrs tagad
ka šīs kļūdas ir diezgan viegli atrisināt, un viegli veikt.
Bet, kad programma ir vairāk nekā 12 līnijas ilgi, tas ir 50 pozīcijas garš, 100 līnijas ilgi,
ejot caur savu kodu pozīcijai, domājot ar to loģiski,
ir iespējams, bet nav īpaši jautri darīt, pastāvīgi meklē bugs,
un tas ir arī grūti izdarīt, un tāpēc līdzīgi Valgrind līdzeklis pastāv.
Ļaujiet man iet uz priekšu un darīt: ļaujiet man atvērt manu termināļa logu,
un ļaujiet man ne tikai palaist atmiņu, jo atmiņas, šķiet, ir labi.
Es saņemu laimīgs. Dodas uz šo papildu baitu beigās masīva
nešķiet pārāk problemātiska.
Bet ļaujiet man, tomēr, do veselība pārbaudītu, kas nozīmē tikai pārbaudīt
vai tas ir faktiski pareiza.
>> Tātad, pieņemsim do Valgrind-V - noplūdes pārbaudīt = pilns,
un tad programmas šajā gadījumā vārds ir atmiņa, nevis a.out.
Tāpēc ļaujiet man iet uz priekšu un darīt to. Hit Enter.
Dārgais Dievs. Tas ir tā produkcija, un tas ir tas, ko es pieminēja agrāk.
Bet, ja jūs uzzinātu izlasīt visu muļķības šeit,
lielākā daļa no tā ir tikai diagnostikas izeja tas nav tik interesanti.
Kāds jūsu acu īsti grib, lai meklē, ir ne vārda par kļūdu vai nederīgu.
Vārdi, kas liecina problēmas.
Un tiešām, pieņemsim redzēt, kas notiek nepareizi leju šeit.
Man ir kopsavilkums par sava veida, "lietojamo izeju:. 40 baiti 1 blokos"
Es neesmu īsti pārliecināts, ko bloks ir vēl, bet 40 baiti
patiesībā jūtas kā es varētu izdomāt, kur tas nāk no.
40 baiti. Kāpēc ir 40 baiti lietošanai izejas?
Un jo īpaši, ja mēs ritiniet uz leju šeit,
kāpēc es noteikti zaudējuši 40 baiti? Yeah?
[Studentu atbilde, nesaprotami] Perfect. Jā, tieši tā.
Tur bija desmit veseli skaitļi, un katrs no tiem ir izmērs 4, 32 vai bitiem,
tāpēc es esmu zaudējis precīzi 40 baiti, jo, kā jūs ierosināts, man nav sauc par bezmaksas.
Tas ir viens bug, un tagad pieņemsim skatīties uz leju nedaudz tālāk un redzēt blakus tam,
"Nederīgs rakstīt 4 lielumu." Tagad to, kas ir šis?
Šī adrese ir izteikta kāda bāze notāciju, acīmredzot?
Tas ir heksadecimālajā un jebkurā laikā jūs redzēsiet vairākas sākot ar 0x,
tas nozīmē heksadecimālajā ko mēs darījām ceļu atpakaļ, es domāju, PSET 0 s sadaļā jautājumiem,
kas bija tikai darīt warmup izmantot, pārvēršot decimal, lai Hex uz bināro un tā tālāk.
Heksadecimālajā tikai ar cilvēka konvencija, parasti izmanto, lai pārstāvētu norādes
vai, plašākā nozīmē, adreses. Tas ir tikai konvencija,
jo tas ir mazliet vieglāk lasīt, tas ir nedaudz kompaktāka nekā kaut ko līdzīgu decimālzīmei,
un bināro ir bezjēdzīgi lielākā daļa cilvēku izmantot.
Tātad tagad, ko tas nozīmē? Nu, izskatās, ka tur ir nederīgs rakstīt
punktā par gada memory.c 21 līnijas 4 izmērs.
Tāpēc iesim atpakaļ uz 21 līnijas, un, protams, šeit ir tas, ka nederīgs rakstīt.
Tāpēc Valgrind nav gatavojas pilnībā turēt manu roku un man noteikt ir,
bet tas ir atklāt, ka es esmu dara nederīgu rakstīt.
Es esmu aizkustinošs 4 baitus, ka man vajadzētu būt, un acīmredzot tas ir tāpēc,
kā jūs norādīja, es esmu dara [10], nevis [9] maksimāli
vai [0] vai starp kaut ko.
Ar Valgrind, realizēt jebkurā laikā jūs tagad rakstot programmu
kas izmanto norādes un izmanto atmiņu, un malloc konkrētāk,
noteikti nokļūt ieradumos darbojas šī ilgi
bet ļoti viegli nokopēt un ielīmēt komandu Valgrind
lai redzētu, vai tur ir dažas tur kļūdas.
Un tas būs milzīgs katru reizi, kad jūs redzēt rezultātu,
bet tikai izanalizēt caur vizuāli visa saražotā produkcija un redzēt, ja jūs redzat piemin kļūdas
vai brīdinājumi vai nederīgs vai pazaudēti.
Jebkurš vārds, kas skaņu kā jūs ieskrūvē up kaut kur.
Lai saprastu, ka tas jaunais rīks jūsu rīkkopa.
>> Tagad pirmdien, mums bija viss ķekars ļaudīm nākt klajā šeit
un pārstāvēt jēdzienu saistītu sarakstu.
Un mēs ieviesa saistīts saraksts kā risinājumu kāda problēma?
Yeah? [Studentu atbilde, nesaprotami] Laba.
Masīvi nevar būt atmiņas pievienots tiem.
Ja jūs piešķirt masīvs 10 izmēra, kas ir viss jums.
Jūs varat zvanīt funkcija ir līdzīga realloc ja sākotnēji sauc malloc,
un kas var mēģināt augt masīvs, ja ir telpa uz beigām tā
ka neviens cits izmanto, un, ja tur nav, tas būs vienkārši atrast jums lielāku gabalu kaut kur citur.
Bet tad tas būs kopija visu šo baitu jaunajā masīvā.
Tas izklausās ļoti pareizs risinājums.
Kāpēc tas ir nepievilcīga?
Es domāju tas darbojas, cilvēki ir atrisināt šo problēmu.
Kāpēc mums ir nepieciešams, lai atrisinātu to pirmdien ar saistītas sarakstiem? Yeah?
[Studentu atbilde, nesaprotami] Tas varētu aizņemt ilgu laiku.
Patiesībā, jebkurā laikā jūs zvanāt malloc vai realloc vai calloc, kas ir vēl otrs,
jebkurā laikā jūs, programmas, runā ar operētājsistēmu,
Jums ir tendence palēnināt programmas leju.
Un, ja jūs darāt šāda veida lietām cilpas, jūs tiešām kavē lietas leju.
Jūs neesat gatavojas nepamanīt par vienkāršāko "Hello World" tipa programmām,
bet daudz lielākām programmām, lūdzot operētājsistēmu atkal un atkal atmiņas
vai sniedzot to atkal un atkal mēdz nebūt laba lieta.
Plus, tas ir tikai sava veida intelektuāli - tas ir pilnīga laika izšķiešana.
Kāpēc piešķirt vairāk un vairāk atmiņas, riska kopēšana viss uz jauno bloku,
ja jums ir alternatīva, kas ļauj piešķirt tikai tik daudz atmiņu, kā jums tiešām ir nepieciešams?
Tātad tur ir plusi un mīnusi, kas šeit.
Viens no plusiem ir tāda, ka mums ir dinamismu.
Nav svarīgi, kur atmiņas gabalos ir, ka ir bezmaksas,
Es varu tikai veida radītu šīs maizes drupatas pa šautru
lai piesietu visa mana saistīts saraksts kopā.
Bet man ir jāmaksā vismaz vienu cenu.
>> Kas man ir jāatsakās gūstot saistītas sarakstus?
Yeah? [Studentu atbilde, nesaprotami] Laba.
Jums ir nepieciešams vairāk atmiņas. Tagad man vajag telpa šiem šautru,
un attiecībā uz šo super vienkāršu saistīts saraksts
kas ir tikai cenšas saglabāt veselus skaitļus, kas ir 4 baiti, mēs turpinām sakot
labi, rādītājs ir 4 baiti, tāpēc tagad es esmu burtiski dubultojies
atmiņas daudzums man vajag tikai, lai saglabātu šo sarakstu.
Bet atkal, tas ir nemainīgs tradeoff datorzinātnēs
starp laiku un telpu un attīstības, pūļu un citu resursu.
Kas cits, izmantojot saistītu sarakstu negatīvie? Yeah?
[Studentu atbilde, nesaprotami]
Good. Nav tik viegli piekļūt. Mēs vairs nevar sviras
nedēļā 0 principus, piemēram, skaldi un valdi.
Un konkrētāk, binārā meklēšana. Jo, pat ja mēs cilvēkiem
var redzēt aptuveni kur šā saraksta vidu ir,
dators tikai zina, ka tas saistīts saraksts sākas pēc adreses sauc pirmās.
Un tas ir 0x123 vai kaut kas tamlīdzīgs.
Un vienīgais veids, kā programma var atrast vidusceļu elements
ir faktiski meklēt visu sarakstu.
Un pat tad, tas burtiski ir meklēt visu sarakstu, jo
pat tad, kad jūs sasniegsiet vidējo elementu, izpildot norādes,
Jūs, programma, nav ne jausmas, cik ilgi šis saraksts ir, iespējams,
līdz sasniegsiet beigām par to, un kā jūs zināt programmiski
ka tu esi beigās saistītajā sarakstā?
Tur īpašs NULL rādītājs, lai atkal, konvencija.
Nevis izmantot šo rādītāju, mēs noteikti negribam, lai to dažas atkritumu vērtība
norādot off stadijā kaut, mēs gribam, lai būtu roku uz leju, null,
tāpēc, ka mums ir šis Terminus šajā datu struktūru, lai mēs zinām, kur tas beidzas.
>> Ko darīt, ja mēs vēlamies, lai manipulēt šo?
Mēs to darījām lielākā daļa šo vizuāli, un ar cilvēkiem,
bet ko tad, ja mēs vēlamies darīt ievietošanu?
Tātad sākotnējā sarakstā bija 9, 17, 20, 22, 29, 34.
Ko darīt, ja mēs pēc tam vēlējāmies malloc vietu skaita 55 mezglu par to,
un tad mēs vēlamies ievietot 55 uz sarakstu tāpat kā mēs to darījām pirmdien?
Kā mēs to darām? Nu, Anita nāca klajā un viņa būtībā gāja sarakstu.
Viņa sāka pie pirmā elementa, tad nākamo, nākamais, nākamais, nākamais, nākamais.
Beidzot hit kreiso galam
un sapratu, ak, tas ir NULL. Tātad, ko rādītājs manipulācijas vajadzēja darīt?
Persona, kas bija uz beigām, numurs 34, nepieciešama viņa kreiso roku izvirzīts
līdz punktam 55, 55 bija nepieciešams viņu kreiso roku uz leju, lai jaunais NULL Terminator. Darīts.
Diezgan viegli ievietot 55 par šķiroto sarakstā.
Un kā tas varētu izskatīties?
>> Ļaujiet man iet uz priekšu un atvērt dažas koda piemērs šeit.
Es atvērt gedit, un ļaujiet man atvērt divus failus pirmās.
Viens no tiem ir list1.h, un ļaujiet man tikai atgādināt, ka tas bija rieciens kodu
ka mēs izmantot, lai pārstāvētu mezglu.
Mezgls ir gan int sauc n un rādītāju sauc blakus kas tikai norāda uz nākamo lieta sarakstā.
Tas tagad ir. H failu. Kāpēc?
Tur šī konvencija, un mēs neesam izmantojuši šo milzīgu paši,
bet persona, kas rakstīja printf un citas funkcijas
deva kā dāvanu pasaulei visus šīm funkcijām, rakstot failu sauc stdio.h.
Un tad tur ir string.h, un tad tur map.h, un tur ir visi šie h faili
ka Jums varētu būt redzējis vai izmanto termiņa laikā raksta citiem cilvēkiem.
Parasti tie h faili ir. Tikai lietas, piemēram typedefs
vai deklarācijas par pasūtījuma veidiem vai deklarācijās konstantes.
Jums nav likts funkcijas "implementācijas header failus.
Jūs likts vietā, tikai savu prototipu.
Jūs nodot lietas, ko vēlaties dalīties ar pasauli, kas tiem nepieciešams
lai apkopotu savu kodu. Tik vienkārši, lai iegūtu šajā ieradums,
mēs nolēmām darīt to pašu. Tur nav daudz list1.h,
bet mēs esam likts kaut kas varētu būt interesanta cilvēkiem pasaulē
kas vēlas izmantot mūsu saistīts saraksts īstenošanu.
Tagad, list1.c, es neiešu cauri visu šo lietu
jo tas ir nedaudz par garu, šī programma, bet pieņemsim palaist to reālā ātri uzvednē.
Ļaujiet man apkopot List1, ļaujiet man tad palaist List1, un ko jūs redzēsiet, ir
Mēs esam modelētiem vienkāršu maz programmu šeit
kas notiek, lai ļauj man pievienot un noņemt numurus sarakstā.
Tāpēc ļaujiet man iet uz priekšu un rakstīt par izvēlnes iespējas 3 3.
Es gribu ievietot numuru - pieņemsim do pirmais numurs, kas bija 9,
un tagad es esmu teicis saraksts ir tagad 9.
Ļaujiet man iet uz priekšu un darīt citas ievietošanu, tāpēc es hit izvēlnes iespēju 3.
Ko skaits vēlos ievietot? 17.
Enter. Un es darīšu tikai viens.
Ļaujiet man ievietot numuru 22.
Tāpēc mums ir aizsākumu saistītajā sarakstā, kas mums bija slaida kā pirms brīža.
Kā tas ievietošanas patiesībā notiek?
Patiešām, 22 ir tagad pie saraksta beigās.
Tātad stāsts mēs teicis uz skatuves pirmdien un recapped tikai tagad
patiešām tiek notiek kodu.
Pieņemsim to apskatīt. Ļaujiet man ritiniet uz leju šajā failā.
Mēs spīdums pār kādu no funkcijām,
bet mēs iesim uz leju, lai, teiksim, ievietot funkciju.
>> Let 's redzēt, kā mēs iet par ievietojot jaunu mezglu saistībā ar šo saistīts saraksts.
Kur ir saraksts deklarēta? Nu, pieņemsim ritiniet visu ceļu augšā,
un ievēroju, ka mana saistīts saraksts būtībā deklarēta kā viens rādītājs, kas ir sākotnēji NULL.
Tāpēc es esmu, izmantojot globālo mainīgo šeit, kas kopumā mēs esam sludināja pret
jo tas padara jūsu kods nedaudz netīrs, lai saglabātu,
tas ir sava veida slinks, parasti, bet tas nav slinks un tas nav nepareizi, un tas nav slikti
Ja programma ir vienīgais mērķis dzīvē ir simulēt viens saistīts sarakstu.
Kas ir tieši tas, ko mēs darām.
Tātad, nevis pasludināt to galvenais un tad ir nodot to uz katru funkciju
mēs esam rakstīts šajā programmā, mēs tā vietā saprotam ak, pieņemsim tikai padara to globālo
jo viss, lai šīs programmas mērķis ir demonstrēt tikai viena vienīga saistīts saraksts.
Tāpēc, ka jūtas labi. Te ir manas prototipi, un mēs ne iet cauri visiem šiem,
bet es uzrakstīju dzēst funkciju, atrast funkciju, baseins ievietot funkcija, un traversa funkciju.
Bet pieņemsim tagad iet atpakaļ uz leju, lai ievietošanas funkciju
un redzēt, kā tas viens strādā šeit.
Ieliktnis ir uz līnijas - šeit mēs iet.
Ievietot. Tāpēc tas neveic nekādus argumentus, jo mēs ejam lūgt
lietotājs iekšpuses šo funkciju skaitu viņi vēlas ievietot.
Bet vispirms mēs sagatavot dot viņiem dažas vietas.
Tas ir sava veida kopēt un ielīmēt no citām piemērs.
Šajā gadījumā mēs piešķirot int, šoreiz mēs piešķirot mezglu.
Man nav īsti atcerēties, cik baiti mezgls ir, bet tas ir jauki.
Sizeof var izdomāt par mani.
Un kāpēc es esmu pārbaudot NULL ar 120 līniju?
Kas varētu iet greizi 119 rindā? Yeah?
[Studentu atbilde, nesaprotami]
Good. Vienkārši varētu būt gadījums, ka es esmu lūdza pārāk daudz atmiņu
vai kaut kas ir nepareizi, un operētājsistēma nav pietiekami daudz baitus, lai dotu man,
tāpēc tas signalizē par daudz, atgriežoties null, un, ja man nav pārbaudīt, ka
un es tikai akli turpināt izmantot adresi atgriezās, tas varētu būt nulle.
Tas varētu būt daži nezināms vērtība, nav laba lieta, ja es -
faktiski nebūs zināms vērtību. Tas varētu būt nulle, tāpēc es nevēlos
ļaunprātīgi to un riskēt dereferencing to.
Ja tas notiks, es tikai atgriezties un mēs izlikties, piemēram, es nedabūju atpakaļ jebkuru atmiņu vispār.
>> Citādi, es pateikt lietotājam dod man numuru, lai ievietotu, es aicinu mūsu vecais draugs GetInt,
un tad tas bija jaunā sintakse mēs iepazīstināja pirmdien.
"Newptr-> n 'nozīmē veikt adresi, kas jums tika dota ar malloc
kas ir pirmais baits jaunu mezglu objektu,
un tad doties uz lauka sauc n.
Mazliet nieki jautājums: Tas ir līdzvērtīgi tam, ko vairāk mistisks līniju kodu?
Kā vēl es varētu būt rakstīts šo? Vēlaties veikt stab?
[Studentu atbilde, nesaprotami]
Good. Izmantojot. N, bet tas nav gluži tik vienkārši, kā šis.
Kas man vispirms ir nepieciešams darīt? [Studentu atbilde, nesaprotami]
Good. Man vajag darīt * newptr.n.
Tātad tas ir saprotams jaunais rādītājs acīmredzot adresi. Kāpēc?
Jo tas bija atpakaļ ar malloc. Iesaistoties * newptr sakot "iet tur,"
un tad, kad tu esi tur, tad jūs varat izmantot vairāk pazīstams. N,
bet tas tikai izskatās mazliet neglīts, jo īpaši, ja mēs cilvēki ir gatavojas
sagatavo norādes ar bultiņām visu laiku, pasaule ir standartizēts uz šo arrow apzīmējums,
kas dara tieši to pašu.
Tātad jums tikai izmantot -> notation kad pa kreisi lieta ir rādītājs.
Pretējā gadījumā, ja tas ir faktiskā struktūrai, izmantojiet. N.
Un tad šis: Kāpēc es sāktu newptr-> blakus uz NULL?
Mēs nevēlamies dangling kreiso roku nost no beigām skatuves.
Mēs vēlamies, norādot taisni uz leju, kas nozīmē beigas šā saraksta
iespējams, varētu būt šo mezglu, lai mēs labāk pārliecinieties, ka tā ir NULL.
Un, vispār, inicializēšana jūsu mainīgos vai jūsu datu locekļiem un structs
lai kaut kas ir vienkārši laba prakse.
Vienkārši ļaujot atkritumu pastāv un turpina pastāvēt parasti izpaužas jums nepatikšanas
ja esat aizmirsis kaut ko darīt vēlāk.
>> Lūk dažas lietas. Tas atkal ir ievietot funkcija,
un pirmā lieta, ko es pārbaudītu, ir, ja mainīgais sauc par pirmo,
ka globālā mainīgais ir NULL, tas nozīmē, ka nav saistīts saraksts.
Mums nav ievietota nekādus skaitļus, tāpēc tas ir niecīgs, lai ievietotu šo pašreizējo skaitu
šajā sarakstā, jo tas vienkārši pieder sākumā sarakstā.
Tātad tas bija, kad Anita bija tikai stāvus šeit vien, izliekoties
neviens cits bija šeit uz skatuves, kamēr mēs piešķirts mezglā,
tad viņa varēja paaugstināt savu roku pirmo reizi,
ja ikviens cits bija atbraukusi līdzi skatuves viņai pakaļ pirmdien.
Tagad šeit, tas ir maz pārbaude, kur man ir ko teikt, ja jaunā mezgla vērtība n
ir <par n vērtību līdzšinējā pirmā mezglā,
tas nozīmē, ka ir saistīts saraksts, kas ir sācies.
Tur ir vismaz viens mezgls sarakstā, taču šī jaunā puisis
pieder pirms tā, tāpēc mums ir nepieciešams, lai pārvietotu lietas apkārt.
Citiem vārdiem sakot, ja sarakstā ir sākusies tikai ar, teiksim,
tikai skaitlis 17, tas ir - patiesībā, mēs varam izdarīt daudz skaidrāk.
Ja mēs sāktu mūsu stāsts ar rādītāju šeit sauc par pirmo,
un sākotnēji tas ir NULL, un mēs ievietojiet numuru 9,
numuru 9, noteikti pieder sākumā sarakstā.
Tāpēc pieņemsim izlikties mēs vienkārši malloced adresi vai numuru 9 un nodot to šeit.
Ja pirmās ir 9 pēc noklusējuma, Pirmais scenārijs mēs apspriedām tikai nozīmē pieņemsim punkts šis puisis šeit,
atstāt šo kā NULL, tagad mums ir skaitli 9.
Nākamais numurs mēs vēlamies ievietot ir 17.
17 pieder vairāk nekā šeit, tāpēc mēs esam gatavojas darīt kādu loģisku pastiprināšanu caur šo.
Tāpēc pieņemsim vietā, pirms mēs to darām, pieņemsim izlikties, ka mēs vēlējāmies ievietot numuru 8.
>> Tik vienkārši ērtības labad labad, es esmu gatavojas izdarīt šeit.
Bet atceries, malloc var nodot to visvairāk jebkur.
Bet Zīmēšanas labad, es nolikšu to šeit.
Tāpēc izlikties es esmu tikko piešķirta mezglu skaita 8; tas ir NULL pēc noklusējuma.
Kas tagad ir noticis? Pāris lietas.
Mēs veicām šo kļūdu uz skatuves pirmdien kur mēs atjaunināt rādītāju kā šis,
tad to izdarīja, un tad mēs apgalvoja - mēs bāreņi visi pārējie uz skatuves.
Jo jūs cant - darbību šeit kārtība ir svarīga,
jo tagad mēs esam zaudējuši šo mezglu 9, ka ir tikai sava veida peldošs kosmosā.
Tātad tas nebija pareizā pieeja pirmdien.
Mums vispirms ir jādara kaut kas cits.
No pasaules valsts izskatās šādi. Sākumā, 8 ir piešķirti.
Kas būtu labāks veids, ievietojot 8?
Tā vietā, lai atjauninātu šo rādītāju, pirmkārt, vienkārši atjaunināt šo vienu šeit vietā.
Tāpēc mums līnijas kodu, kas notiek, lai ieslēgtu šo NULL raksturs
uz faktisko rādītāju, kas ir vērsts uz 9 mezglā,
un tad mēs varam droši jāmaina vispirms norādīt uz šo puisis šeit.
Tagad mums ir saraksts, saistīts saraksts, no diviem elementiem.
Un ko tas patiesībā izskatās šeit?
Ja mēs apskatīt kodu, ievēroju, ka es esmu darījusi tieši tā.
Man teica newptr, un šajā stāstā, newptr tika norādot uz šo puisi.
>> Tāpēc ļaujiet man pievērst vēl viena lieta, un es būtu atstājis nedaudz vairāk vietas par šo.
Lai piedod tiny maz zīmējumu.
Šis puisis sauc newptr.
Tas ir mainīgs mēs paziņoja dažas rindiņas agrāk, jo rindā - nedaudz virs 25.
Un tas norāda uz 8. Tātad, kad es saku newptr-> blakus, tas nozīmē, ka iet uz struct
kas ir tiek norādīja ko newptr, tāpēc šeit mēs esam, iet tur.
Tad bultiņa saka saņemtu nākamo lauku, un tad = saka likts kāda vērtība tur?
Vērtība, kas bija pirmais; kāda vērtība bija pirmais?
Pirmais bija norādot šajā mezglā, lai tas nozīmē, tas tagad norāda šajā mezglā.
Citiem vārdiem sakot, kāda izskatās kaut smieklīgs haoss ar manu rokrakstu,
kāda ir vienkārša ideja vienkārši pārvietojas šīs bultiņas apkārt
pārveido uz kodu ar tikai šo vienu slāni.
Uzglabāt to, kas ir pirmais nākamajā laukā un pēc tam atjaunot to, kas vispirms patiesībā ir.
Iesim uz priekšu un ātri uz priekšu caur kādu no šo,
un apskatīt tikai šajā asti ievietošanas tagad.
Pieņemsim, ka es nokļūt līdz vietai, kur man šķiet, ka nākamais lauks kādu mezglā ir NULL.
Un šajā brīdī stāsts, detalizēti, ka es esmu glossing pār
ir tas, ka es esmu ieviesusi citu rādītāju šeit 142 rindā, priekšgājējs rādītāja.
Būtībā, šajā brīdī stāsts, tiklīdz saraksts kļūst garš,
Es veida nepieciešams staigāt to ar diviem pirkstiem, jo, ja man iet pārāk tālu,
atceros vienas garuma sarakstu, jūs nevarat iet atpakaļ.
Tātad šis predptr ideja ir mana kreisā pirkstu, un newptr - ne newptr.
Vēl rādītājs, kas ir šeit ir mana pirkstu, un es esmu tikai veida pastaigas sarakstu.
Tieši tāpēc, ka pastāv. Bet pieņemsim tikai uzskatīt par vienu no vienkāršāku gadījumu šeit.
Ja šīs rādītāju nākamās lauks ir NULL, kāda ir loģisks netieši?
Ja Jums ir šķērsot šo sarakstu un jūs hit NULL rādītāju?
Tu esi pie saraksta beigās, un tā kods, lai pēc tam pievienot šo vienu papildu elementu
ir sava veida intuitīvs būs veikt šo mezglu, kura nākamais rādītājs ir NULL,
tāpēc tas ir šobrīd NULL, un mainīt to, lai gan, lai būtu adrese jaunu mezglu.
Tāpēc mēs esam tikai zīmējumu kodu bultiņai, ka mēs vērsa uz skatuves, paaugstinot kādu kreiso roku.
>> Un lieta, ka es ņemšu vilnis savu roku pie tagad,
tikai tāpēc, ka es domāju, ka tas ir viegli pazust, kad mēs to varam izdarīt šāda veida vidē,
tiek pārbaudīti ievietošanai uz sarakstu s vidū.
Bet tikai intuitīvi, kas nepieciešams, lai notiktu, ja jūs vēlaties, lai noskaidrotu
kur daži numurs pieder vidū ir jums ir staigāt tā
ar vairāk nekā vienu pirkstu, vairāk nekā viens rādītājs,
izdomāt, kur tā pieder ar pārbaudi ir elements <pašreizējo vienu,
> Pašreizējo, un, kad jūs atradīsiet šo vietu,
tad jums ir jādara šāda veida čaulas spēle, kur jūs pārvietot norādes ap ļoti rūpīgi.
Un ka atbilde, ja jūs vēlaties, lai tādēļ caur šo mājās par savu,
aprobežojas tikai ar šīm divām līnijām kodu, bet kā šo līniju, lai ir super svarīgi.
Jo, ja jūs piliens kādu roku un paaugstināt kāds cits nepareizā secībā,
atkal, jūs varētu nonākt orphaning sarakstu.
Apkopot vairāk konceptuāli, pie astes ievietošana ir samērā vienkārša.
Pie galvas ievietošana ir arī salīdzinoši vienkārši,
bet jums ir nepieciešams atjaunināt par papildus rādītāju šo laiku
izspiest skaits 5 uz sarakstu šeit,
un tad ievietošanas vidū ietver vēl vairāk pūļu,
līdz ļoti uzmanīgi ievietot skaits 20 pareizā vietā,
kas ir starp 17 un 22.
Tātad jums ir nepieciešams kaut ko darīt, piemēram, ir jauna mezgla 20 punktu līdz 22,
un tad, kura mezgla rādītājs ir jāatjaunina pēdējais?
Tas ir 17, lai faktiski ievietotu.
Tātad vēlreiz, es ņemšu atlikt faktisko kodu par konkrēto īstenošanu.
>> No pirmā acu uzmetiena, tas mazliet milzīgs, bet tas patiešām ir tikai bezgalīgs cilpas
kas ir looping, looping, looping, looping, un pārkāpj tiklīdz jūs hit NULL rādītāju,
kurā brīdī jūs varat darīt nepieciešamo ievietošanu.
Tas, tad, tiek uzrādīts saistīts saraksts ievietošanas kodu.
Tas bija sava veida partijas, un tā uzskata, tāpat kā mēs esam atrisināta viena problēma,
bet mēs esam ieviesa pilnīgi citu. Atklāti sakot, mēs esam pavadījuši visu šo laiku
uz lielā O un Ω un darba laika, mēģinot risināt problēmas ātrāk,
un šeit mēs speram lielu soli atpakaļ, tā uzskata.
Un tomēr, ja mērķis ir glabāt datus,
tā uzskata, tāpat kā Svētais Grāls, kā mēs teicām pirmdien, būtu patiešām
uzglabāt lietas uzreiz.
>> Faktiski, pieņemsim, ka mēs malā saistīts saraksts uz brīdi
un mēs tā vietā ieviesa jēdzienu galda.
Un pieņemsim tikai domā par galda uz brīdi kā masīvs.
Šis masīvs un šis gadījums ir apmēram 26 elementi, 0 līdz 25,
un pieņemsim, ka jūs vajag kādu gabalu uzglabāšanu nosaukumiem:
Alise un Bobs un Čārlijs un līdzīgi.
Un jums ir nepieciešams zināms datu struktūru, lai saglabātu šos nosaukumus.
Nu, jūs varētu izmantot kaut kas līdzīgs saistīts saraksts
un jūs varētu staigāt sarakstu ievietojot Alise pirms Bobs un pēc Bob Čārliju un tā tālāk.
Un, patiesībā, ja jūs vēlaties redzēt kodu, piemēram, ka malā,
zinu ka list2.h, mēs tieši tā.
Mēs ne iet caur šo kodu, bet tas ir variants no pirmā piemērs
kas ievieš vienu citu struct mēs esam redzējuši pirms sauktā studentu,
un tad kāda tā faktiski uzglabā saistītajā sarakstā ir rādītājs, lai studentu struktūru
nevis vienkārši nedaudz skaitlim, n.
Tātad saprast, ka kods, tur, kas ietver faktiskos stīgas,
bet, ja pie rokas mērķis tiešām tagad ir risināt efektivitātes problēmas,
tas nebūtu jauki, ja mēs esam dota objektu sauc Alise,
Mēs vēlamies, lai viņas uz pareizā vietā datu struktūru,
tā uzskata, tāpat kā tas lūdzu būt tiešām jauki, tikai likt Alice,
kura vārds sākas ar, pirmajā vietā.
Un Bobs, kura vārds sākas ar B, otrajā vietā.
Ar masīvu, vai sāksim aicinot to tabulu, hash tabulas tajā,
mēs varam darīt tieši to. Ja mums ir dots nosaukums, piemēram, Alice,
piemēram Alise virkne, kur jūs nodot A-L-i-C-e?
Mums vajag hueristic. Mums ir nepieciešams funkciju veikt kādu ieguldījumu, piemēram, Alice
un atgriezties atbildi, "Put Alise šajā vietā."
Un šī funkcija, šī melnā kaste, gatavojas saukt jaucējfunkciju.
>> Jaucējfunkciju ir kaut kas ņem ievade, piemēram, "Alice",
un atgriežas jums parasti, ciparu atrašanās kāda datu struktūra, kurā Alise pieder.
Šajā gadījumā mūsu jaucējfunkciju būtu samērā vienkāršs.
Mūsu jaucējfunkciju būtu teikt, ja Jums ir dota "Alise", kura raksturs man rūp?
Pirmais. Tāpēc es skatos [0], un tad es saku, ja [0] raksturs ir, atgriešanās numuru 0.
Ja tas ir B atgriezties 1. Ja tas ir C, atgriezties 2, un tā tālāk.
Visi 0 indeksu, un kas ļautu man ievietot Alise un tad Bob un tad Čārlijs un tā tālāk
šajā datu struktūra. Bet tur ir problēma.
Ko darīt, ja Anita nāk kopā vēlreiz?
Kur mēs ieliekam Anita? Viņas vārds, arī sākas ar burtu A,
un tā uzskata, tāpat mēs esam padarījuši vēl lielāks haoss šo problēmu.
Mums tagad ir tūlītēja ievietošanu, pastāvīga laika ievietošanas, par datu struktūru
nevis nelabvēlīgākā lineāra,
bet ko mēs varam darīt ar Anita šajā gadījumā?
Kādas ir divas iespējas, tiešām? Yeah?
[Studentu atbilde, nesaprotami] Labi, lai mēs varētu būt vēl viens aspekts.
Tas ir labi. Lai mēs varētu veidot lietas 3D piemēram, mēs runājām par mutiski pirmdien.
Mēs varētu pievienot vēl pieejami šeit, bet pieņemsim, ka nē, es cenšos, lai saglabātu šo vienkāršo.
Visa mērķis šeit ir, lai būtu nekavējoties nemainīga laikā piekļūt,
tā ka ir pievienojot pārāk daudz sarežģītību.
Kādas ir citas iespējas, mēģinot ievietot Anita šajā datu struktūra? Yeah?
[Studentu atbilde, nesaprotami] Laba. Lai mēs varētu virzīties ikvienam citam leju,
piemēram leju Bobs un Alise, Charlie nudges un tad mēs uzdodam Anita kur viņa patiešām vēlas būt.
>> Protams, tagad, tur ir blakusparādība šo.
Šī datu struktūra ir iespējams noderīgs ne tāpēc, ka mēs gribam, lai ievietotu cilvēkus reizi
bet tāpēc, ka mēs gribam, lai pārbaudītu, vai viņi tur vēlāk
ja mēs gribam, lai izdrukātu visus to datu struktūras nosaukumiem.
Mēs ejam, lai kaut ko darīt ar šiem datiem beidzot.
Tāpēc tagad mēs esam veida ieskrūvē vairāk Alice, kas vairs, kur viņa ir vajadzēja būt.
Nedz Bobs, ne Čārlijs.
Tāpēc varbūt tas nav tik laba ideja.
Bet tiešām, tas ir viens variants. Mēs varētu novirzīt ikvienam leju,
vai heck, Anita ieradās vēlu, lai spēli, kāpēc nav mēs tikai izvirzīti Anita
ne šeit, ne šeit, ne šeit, pieņemsim tikai nodot viņas nedaudz zemāks sarakstā.
Bet tad šī problēma sāk pāriet no jauna.
Jums varētu būt iespēja atrast Alise uzreiz, balstoties uz viņas vārda.
Un Bobs uzreiz, un Čārlijs. Bet tad jūs meklēt Anita,
un jūs redzat, hmm, Alise ir ceļā.
Nu, ļaujiet man pārbaudiet zemāk Alice. Bobs ir ne Anita.
Čārlijs nav Anita. Ak, tur ir Anita.
Un, ja jūs turpināt šī vilciena loģikas visu ceļu,
kāda ir vissliktākā lieta darbības laiks atrast vai ievietojot Anita šo jauno datu struktūra?
Tas ir O (n), vai ne?
Jo sliktākajā gadījumā, tur ir Alise, Bobs, Čārlijs. . .
visu ceļu uz leju, lai kāds ar nosaukumu "Y", tāpēc tur ir tikai viena vieta pa kreisi.
Par laimi, mums nav viens sauc par "Z", tāpēc mēs uzdodam pašā apakšā Anita.
>> Mums nav īsti atrisināt šo problēmu.
Tāpēc varbūt mums ir nepieciešams, lai ieviestu šo trešo dimensiju.
Un izrādās, ja mēs ieviestu šo trešo dimensiju,
mēs nevaram izdarīt perfekti, bet Svētais Grāls gatavojas iegūt
pastāvīga laika ievietošanas un dinamisku ievietošanas lai
Mums nav grūti kods masīvs 26 izmēra.
Mēs varam ievietot tik daudz vārdus, kā mēs gribam, bet pieņemsim mūsu 5 minūšu pārtraukumu šeit
un tad darīt pareizi.
Labi. Es noteikti stāstu izveidota diezgan mākslīgi tur
izvēloties Alise un tad Bob un tad Čārlijs un tad Anita,
kura vārds bija acīmredzami gatavojas saduras ar Alice.
Bet jautājums, mēs beidzās pirmdien ar ir, cik ticams ir tas
ka jūs varētu saņemt šāda veida sadursmēs? Citiem vārdiem sakot,
ja mēs sāktu lietot šo tabulāru struktūra, kas ir patiešām vienkārši masīvs,
Šajā gadījumā 26 vietām,
Ko darīt, ja mūsu izejvielas tiek nevis vienmērīgi sadalīti?
Tas nav mākslīgi Alise un Bobs un Čārlijs un Deivids un tā tālāk pēc alfabēta,
tas vienmērīgi sadalīta pa cauri Z.
>> Varbūt mēs vienkārši saņemt laimīgs un mēs nebrauksim ir divas vai divu B darbības
ar ļoti lielu varbūtību, bet kā kāds norādīja,
ja mēs vispārināt šo problēmu, nevis darīt 0-25
bet, teiksim, no 0 līdz 364 vai 65, bieži dienu skaits Parastā gadā
un uzdeva jautājumu: "Kas ir varbūtība, ka divi no mums šajā telpā ir tāds pats dzimšanas diena?"
Citiem vārdiem sakot, kāda ir varbūtība, ka divi no mums ir nosaukums sākas ar?
No jautājuma kārtošanas ir tas pats, bet šī adrese telpa,
šo meklējumu telpa, ir lielāks gadījumā dzimšanas dienas,
jo mums ir tik daudz vairāk dienas gadā nekā burtiem alfabēta.
Kas par sadursmes iespējamība?
Nu, mēs varam domāt par to, ko norādītas math pretējā virzienā.
Kas no ne sadursmes iespējamība?
Nu, šis izteiciens šeit saka, ka to, kas ir varbūtība
ja tur ir tikai viens cilvēks šajā telpā, ka tie ir unikāla dzimšanas dienu?
Tas ir 100%. Jo, ja tur ir tikai viens cilvēks telpā,
viņa vai viņas dzimšanas dienā, var būt jebkurš no 365 dienas no gada.
Tātad 365/365 varianti dod man vērtību 1.
Tātad attiecīgais varbūtība šobrīd ir tikai 1.
Bet, ja tur ir otrā persona telpā,
kāda ir varbūtība, ka to dzimšanas diena ir atšķirīgs?
Ir tikai 364 possible dienas, ignorējot garajos gados,
par savu dzimšanas dienu nav saduras ar citām personām.
Tātad 364/365. Ja trešā persona nāk, tas ir 363/365, un tā tālāk.
Lai mēs saglabātu reizinot kopā šos frakcijas, kas kļūst mazākas un mazākas,
lai saprastu, kas ir varbūtība, ka visi no mums ir unikālas dzimšanas dienas?
Bet tad mēs varam, protams, vienkārši ņem šo atbildi un uzsist tā ap
un darīt 1 mīnus visu, ka izteiksmes mēs beidzot nokļūt
ja jūs atceraties atpakaļ jūsu math grāmatas, tas izskatās mazliet kaut kas līdzīgs šim,
kas ir daudz vieglāk interpretēt grafiski.
Un šī grafiskā šeit ir uz x ass skaits dzimšanas dienas,
vai cilvēku skaits ar dzimšanas dienas, un uz y asi ir varbūtība maču.
Un ko tas saka, ka, ja jums ir, teiksim, pat,
pieņemsim izvēlēties kaut ko līdzīgu 22, 23.
Ja tur ir 22 vai 23 cilvēki telpā,
varbūtība, ka divi no tiem ļoti maz cilvēku gatavojas ir pats jubileju
ir faktiski super augsts, combinatorially.
50% izredzes, ka klasē ir tikai 22 cilvēku, seminārs, praktiski,
2 no tiem cilvēkiem būs tādas pašas dzimšanas dienu.
Jo tur ir tik daudz veidi, kā jūs varat būt pats jubileju.
Vēl sliktāk, ja paskatās labajā pusē diagrammas,
ar laiku jums ir klasi ar 58 skolēniem tajā,
no 2 cilvēkiem, kam ir dzimšanas diena varbūtība ir super, super augsts, gandrīz 100%.
Tagad tas ir sava veida fun faktu par reālo dzīvi.
>> Bet sekas, tagad, datu struktūras un glabāta informācija
nozīmē, ka tikai pieņemot, ka jums ir jauka, tīru, vienotu datu izplatīšanu
un jums ir pietiekami lielas masīvs, lai ietilptu ķekars lietas
nenozīmē, ka jūs gatavojas saņemt cilvēkus unikālu vietās.
Jūs esat nāksies sadursmes. Tātad šis sajaukšanai jēdziens, jo tā sauc,
lietojat ievade, piemēram, "Alise" un masāžas to kaut kādā veidā
un tad saņemt atpakaļ atbildi, piemēram 0 vai 1 vai 2.
Getting atpakaļ kādu izeju no šī funkcija ir plagued ar šo varbūtību sadursmes.
Tātad, kā mēs varam realizēt tās sadursmes?
Nu, par vienu gadījumu, mēs varam pieņemt ideju, kas tika ierosināts.
Mēs varam vienkārši novirzīt ikvienam, vai varbūt, mazliet vienkāršāk,
nevis kustībā ikvienam citam, pieņemsim tikai pāriet Anita uz apakšu no pieejamā vietā.
Tātad, ja Alise ir 0, Bobs ir 1, Čārlija ir 2,
mēs tikai izvirzīti Anita pie 3 vietā.
Un tas ir arī datu struktūras tehniku ​​sauc lineāra zondēšana.
Lineārs jo jūs esat tikai ejot šo līniju, un jūs esat veida zondēšana
pieejamās plankumi datu struktūru.
Protams, tas devolves uz O (n).
Ja datu struktūra ir patiešām pilns, tur ir 25 cilvēki, kas tajā jau ir,
un tad Anita nāk kopā, viņa beidzas līdz plkst kādi būtu vieta Z, un tas ir jauki.
Viņa joprojām der, un mēs varam atrast viņas vēlāk.
>> Bet tas ir pretrunā ar mērķi paātrināt lietas uz augšu.
Tātad, ko tad, ja mēs tā vietā ieviesa šo trešo dimensiju?
Ka šis paņēmiens ir parasti sauc atsevišķi ķēžu rādītāju, vai ar ķēdēm.
Un ko hash tabulu tagad ir, tas tabulveida struktūra,
jūsu galda ir tikai masīvs norādes.
Bet kādi ir šie norādes norādīt, ir minējums, ko?
Saistīts saraksts. Tātad, ko tad mēs labāko no abām šīm pasaulēm?
Mēs izmantojam masīvi uz pirmajiem rādītājiem
uz datu struktūru, lai mēs varētu uzreiz doties uz [0] [1], [30] vai tā tālāk,
bet tā, ka mums ir zināma elastība, un mēs varam fit Anita un Alise un Adam
un jebkuru citu vārdu,
Mēs nevis ļaut citiem ass augt patvaļīgi.
Un mēs beidzot, jo pirmdien, ir, ka ekspresīvā iespējas ar saistītajā sarakstā.
Mēs varam augt datu struktūra patvaļīgi.
Alternatīvi, mēs varētu tikai milzīga 2 dimensiju masīvs,
bet tas būs šausmīgs situācija, ja viens no 2-dimensiju masīvs rindās
nav pietiekami liels, lai nākamo personu, kuras vārds notiek, lai sāktu ar A.
Dievs pasarg mums ir pārdalīt milzīgs 2 dimensiju struktūra
tikai tāpēc, ka ir tik daudz cilvēku nosaukts,
it īpaši, ja tur ir tik maz cilvēku nosaukti Z kaut.
Tas tikai būs ļoti rets datu struktūra.
Tātad, tas nav perfekts ar jebkādiem līdzekļiem, bet tagad mums vismaz ir iespēja
lai uzreiz atrast, kur Alise vai Anita pieder,
vismaz attiecībā uz vertikālo asi,
un tad mums vienkārši ir izlemt, kur likt Anita vai Alise šajā saistīts saraksts.
Ja mums nav jārūpējas par šķirošanas lietām, cik ātri mēs varētu ievietot Alise par struktūru, kā šī?
Tas ir nemainīgs laika. Mēs indekss par [0], un, ja neviens ir tur,
Alise dodas sākumā minētā saistīts saraksts.
Bet tas nav milzīgs galā. Jo, ja Anita tad nāk kopā
daži virkne pasākumu vēlāk, kad tas Anita pieder?
Nu, [0]. OOP. Alise ir jau minētajā saistītas sarakstā.
>> Bet, ja mums nav jārūpējas par šķirošanas šos vārdus,
mēs varam vienkārši pārvietot Alice pāri, ievietot Anita, bet pat tas ir nemainīgs laika.
Pat ja tur ir Alise un Ādams un visi šie pārējie A nosaukumi,
tas nav īsti novirzot tos fiziski. Kāpēc?
Jo mēs tikko bija šeit ar saistīts saraksts, kas zina bija šie mezgli ir vienalga?
Viss, kas Jums jādara, ir pārvietot maizes drupatas.
Pārvietot bultiņas apkārt, jums nav, lai fiziski pārvietot datus apkārt.
Tātad, mēs varam ievietot Anita, šajā gadījumā, uzreiz. Nemainīgs laiks.
Tāpēc mums ir pastāvīga laika lookup un pastāvīga laika ievietošana kāds, piemēram, Anita.
Bet sava veida oversimplifying pasauli.
Ko darīt, ja mēs vēlāk vēlaties atrast Alise?
Cik soļus ir tas, ka gatavojas veikt?
[Studentu atbilde, nesaprotami]
Tieši tā. Cilvēku skaits pirms Alise saistītajā sarakstā.
Tātad, tas nav gluži ideāls, jo mūsu datu struktūra, atkal, ir šī vertikālā pieeja
un tad tas ir šīs saistītos sarakstus nokarājas - patiesībā, nemaz nav izdarīt to masīvu.
Tas ir šie saistītie saraksti karājās pie tā, ka izskatās mazliet kaut kas līdzīgs šim.
Bet problēma ir, ja Alise un Ādams un visi šie pārējie A nosaukumi
galu galā vairāk un vairāk nekā tur,
atrast kādu varētu beigties, ņemot ķekars soļus,
bcause jums ir, lai šķērsotu saistīts saraksts,
kas ir lineāra operācija.
Tik tiešām, tad, ievietošanas laiks beidzot ir O (n), kur n ir elementu skaits sarakstā.
Dala ar pieņemsim patvaļīgi sauc to m, kur m ir vairāki saistīti sarakstos
ka mums ir šīs vertikālās ass.
Citiem vārdiem sakot, ja mēs patiesi pieņemam vienotu sadalījumu nosaukumiem,
pilnīgi nereāli. Tur acīmredzot vairāk dažas vēstules, nekā citi.
>> Bet, ja mēs pieņemam uz brīdi vienota izplatīšanas,
un mēs esam N Kopējais cilvēku, un m Kopējais ķēdes
pieejamas mums, tad ilgums katrā no šīm ķēdēm
diezgan vienkārši būs kopā, n dalīts ar skaitu ķēdēm.
Tātad N / m. Bet šeit, kur mēs varam būt visi matemātiski gudrs.
m ir konstants, jo tur ir noteikts skaits no tiem.
Jūs gatavojas atzīt savu masīvs sākumā,
un mēs esam ne izmēru vertikālo asi. Pēc definīcijas, kas paliek nemainīgi.
Tas ir tikai horizontālā ass, tā sakot, situācija mainās.
Tātad tehniski, tas ir nemainīgs. Tāpēc tagad, ievietošanas laiks
ir diezgan daudz O (N).
Lai nejūtas tik daudz labāk.
Bet kāda ir patiesība šeit? Nu, visu šo laiku, lai nedēļas,
Mēs esam teicis O (n ²). O (N), 2 x n ², - N, dalīts ar 2. . . ech.
Tas ir tikai N ². Bet tagad, šajā daļā semestrī,
mēs varam sākt runāt par reālo pasauli vēlreiz.
Un n / m ir absolūti ātrāk nekā tikai n atsevišķi.
Ja jums ir tūkstoš vārdu, un jūs pauze tās vairākos segmentos
tāpēc, ka jums ir tikai desmit vārdus katru no šīm ķēdēm,
absolūti meklējot desmit lietas būs ātrāk nekā tūkstotis lietas.
Un tā viens no gaidāmo problēmu kopas gatavojas apstrīdēt jums
domāt par to, tieši tas, lai gan, jā,
asimptotiski un matemātiski, tas joprojām ir tikai lineārs,
kas iesūc vispār mēģinot atrast lietas.
Patiesībā, tas būs ātrāk nekā
jo šī dalītājs.
Un tā tur atkal būs šis kompromiss
un šis konflikts starp teoriju un realitāti,
un viens no pogām sāksies pagrieziena šajā punktā semestrī
ir vairāk par realitāti, viens, kā mēs veida sagatavotos semster beigām,
jo mēs ieviest pasaulē web programmēšanas,
ja tiešām, sniegums ir gatavojas rēķināties, jo lietotāji gatavojas
sāk justies un novērtēt slikts dizains lēmumus.
>> Tātad, kā jūs iet par īstenojot saistītas - hash tabulu ar 31 elementiem?
Un iepriekšējais piemērs bija patvaļīgi par dzimšanas dienas.
Ja kādam ir dzimšanas diena 1 janvārī vai februārī 1, mēs viņus šajā spainī.
Ja tas ir gada 2 februāris 2, marts 2 mēs viņus šajā spainī.
Tieši tāpēc tas bija 31. Kā jūs atzīt hash tabulu?
Tas var būt diezgan vienkāršs, mezglu * galds ir mans patvaļīgs vārds par to, [31].
Tas dod man 31 norādes uz mezgliem,
un kas ļauj man ir 31 palīglīdzekļi saistītas sarakstos
pat ja šie ķēdes ir sākotnēji NULL.
Ko es gribu, lai, ja es gribu, lai saglabātu "Alise", "Bobs", "Čārlijs"?
Nu, mums ir nepieciešams, lai aplauzt tās lietas, kas struktūrā
jo mums Alise norādīt uz Bob, norādīt uz Charlie, un tā tālāk.
Mēs nevaram vienkārši ir vārdi vien, lai es varētu izveidot jaunu struktūru sauc mezglā šeit.
>> Kas ir faktiskais mezglu? Kas ir šajā jaunajā saistīts saraksts mezgls?
Pirmā lieta, ko sauc par vārdu, ir personas vārda.
GARUMS, iespējams, attiecas uz maksimālo garumu cilvēka vārdu,
kāds tas ir, 20, 30, 40 rakstzīmes traks stūra gadījumos,
un +1 ir par ko? Tas ir tikai papildu NULL raksturs, \ 0.
Tātad šis mezgls ir ietīšana "kaut kas" iekšā no sevis,
bet tas arī deklarē rādītāju sauc nākamo
lai mēs varētu ķēde Alise Bobam lai Čārlijs un tā tālāk.
Var būt nulle, bet ne obligāti jābūt.
Visus jautājumus par šīm hash tabulu? Yeah?
[Studentu lūdzot jautājumu, nesaprotami] masīvs - labs jautājums.
Kāpēc tas ir char vārds masīvā nevis tikai char *?
Šajā nedaudz patvaļīgi Piemēram, es negribēju būt spiesta
līdz malloc katram no sākotnējiem nosaukumiem.
Es gribēju paziņot maksimālo summu atmiņas par virkni
lai es varētu kopēt uz struktūru Alise \ 0 un nav jātiek galā ar malloc un bezmaksas un līdzīgu.
Bet es varētu darīt, ja es gribēju būt vairāk apzinās kosmosa izmantošanu. Labs jautājums.
Tāpēc pieņemsim mēģināt vispārināt prom no šīs
un koncentrēties uz atlikušo šodienu datu struktūrām kopumā
un citas problēmas, kas mēs varam atrisināt, izmantojot tos pašus pamatus
lai gan datu struktūras pašas var atšķirties to detaļās.
>> Tātad izrādās, datorzinātnēs, koki ir ļoti bieži.
Un jūs varat domāt par koku veida, piemēram, ģimenes koku,
ja tur ir dažas saknes, daži matriarch vai patriarhs
vecmāmiņa vai grandpa vai agrāk muguras,
zem kura ir mamma un tētis vai dažādu vecvecākus vai tamlīdzīgi.
Tātad koka struktūru ir mezglu un tas ir bērni,
parasti 0 vai vairāk bērni uz katru mezglu.
Un daži no žargonu, ka jūs redzēt šajā attēlā šeit
ir kāds no mazajiem bērniem vai grandkids par malām
kam nav bultas, kas izriet no tiem,
tie ir tā saucamie lapas, un no iekšpuses ikviens
ir iekšējais mezgls, jūs varat zvanīt tā neko pa šo līniju.
Bet šī struktūra ir diezgan bieži. Šis viena ir nedaudz patvaļīgs.
Mums ir viens bērns pa kreisi, mums ir trīs bērni par tiesībām,
divi bērni apakšā pa kreisi.
Lai mēs varētu būt dažādi izmēra koki, bet, ja mēs sākam standartizēt lietas,
un jūs varētu atcerēties šo no Patrika video par binārā meklēšanas no iepriekšējā īss
tiešsaistē, binārā meklēšana nav jāīsteno ar masīvu
vai papīra gabalus uz tāfeles.
Pieņemsim, ka jūs vēlētos, lai saglabātu savus numurus, kas ir vairāk sarežģītu datu struktūru.
Jūs varētu izveidot koku, kā šis.
Jums varētu būt mezglu deklarēto C, un tas mezgls var būt vismaz divi elementi iekšpusē no tā.
Viens no tiem ir numurs, kuru vēlaties saglabāt, un otrs ir - labi, mums vajag vēl vienu.
Otrs ir tā bērni.
Tātad, šeit ir vēl viens datu struktūra. Šoreiz, mezglu ir definēts kā uzglabāt vairākus n
un tad divas norādes, kreisajā bērnu un labi bērnam.
Un viņi nav patvaļīgs. Kas ir interesanti par šo koku?
>> Kas, kā mēs esam, kas šo veic vai kā Patriks kas to veic viņa video modelis?
Tas ir sava veida skaidrs, ka tur ir daži šķirošanas notiek šeit,
bet kāda ir vienkāršs noteikums? Yeah?
[Studentu atbilde, nesaprotami]
Perfekta. Ja jūs skatienu, jūs redzēt nelielu skaitu kreisajā pusē,
lielie skaitļi par kreisi, bet tas ir taisnība par katru mezglu.
Par katru mezglu, tās kreisajā bērnam ir mazāk par to un tās tiesības bērns lielāks nekā to.
Ko tas nozīmē, tagad ir, ja es gribu, lai meklētu šo datu struktūru, teiksim, numurs 44,
Man ir jāsāk pie saknes, jo, kā ar visām šīm vairāk sarežģītu datu struktūras tagad,
mums ir tikai rādītāju uz vienu lietu, sākums.
Un šajā gadījumā, sākums ir sakne. Tas nav pa kreisi beigas,
tas saknes par šo struktūru. Tāpēc es redzu šeit ir 55, un es esmu meklē 44.
Kurā virzienā vēlos aiziet?
Nu, es gribu iet pa kreisi, jo acīmredzot, ar tiesībām būs pārāk liels.
Tātad paziņojums šeit, tu esi veida konceptuāli cirst koku uz pusēm
jo jūs nekad iet uz leju, labajā pusē.
Tāpēc tagad es iet no 55 līdz 33. Tas ir pārāk mazs skaitlis.
Es meklēju 44, bet tagad es zinu, ja 44 ir šajā kokā, es varu iet protams uz labo pusi.
Tātad vēlreiz, es esmu atzarošana koku pusi.
Tas ir diezgan daudz identiski konceptuāli uz telefona grāmatu.
Tas ir identisks tam, ko mēs izdarījām ar uz tāfeles dokumentiem,
bet tas ir vēl sarežģītākas struktūra, kas ļauj mums patiesībā darīt
šis skaldi un valdi ar dizainu algoritmu,
un patiesībā, šķērsojot struktūru, kā šis - whoops.
Šķērso struktūru, piemēram, tas, kur tas ir tikai "iet šo ceļu vai iet šo ceļu,"
nozīmē visu šo kodu, ieliektām jūsu prātā pirmais, kad to īsteno sadaļā
vai ejot caur to mājās, lai bināro meklēšanu, izmantojot rekursija vai iterācijas,
tas sāpes kaklā. Atrast vidējo elementu, tad darīt savu noapaļošana uz augšu vai leju.
>> Tur skaistumu, jo mēs tagad var izmantot rekursijas atkal,
bet daudz vairāk tīri. Patiešām, ja jūs esat pie numura 55 un jūs vēlaties, lai atrastu 44,
Jums iet pa kreisi, šajā gadījumā, tad ko jūs darīt? Jūs palaist tieši tādu pašu algoritmu.
Jūs pārbaudītu vērtību mezglā, tad jums iet pa kreisi vai pa labi.
Tad jūs pārbaudītu vērtību mezglā, iet pa kreisi vai pa labi.
Tas ir lieliski piemērots, lai recursion.
Tātad, pat ja agrāk mēs esam darījuši dažas diezgan patvaļīgi piemērus iesaistot rekursija
ka nav nepieciešams būt rekursīvs, ar datu STUCTURES,
īpaši koki, tas ir ideāls pieteikumu par šo ideju par ņemot problēmu,
sarūk, un tad risinot tāda paša veida, taču mazākus programmu.
>> Tātad tur ir cits datu struktūra, kas mēs varam ieviest.
Tas viens ir paredzēts pirmajā brīdī izskatās noslēpumains, bet tas viens ir pārsteidzošs.
Tātad šī ir datu struktūra sauc Trie, Trie, kas ir mantots no vārda iegūšanai,
kas nav izrunāts atkārtoti izmēģināt-val, bet tas, ko pasaule prasa šīs lietas. Mēģina. T-R-i-e.
Tas ir koks struktūru dažu šķirot, bet katra no kādas Trie mezgliem
Šķiet, ko? Un tas ir nedaudz maldinošs, jo tas ir sava veida saīsināts.
Bet izskatās, ka katrs šajā Trie mezgls ir faktiski masīvs.
Un pat ja šīs shēmas autors nav pierādījusi to,
Šajā gadījumā, tas Trie ir datu struktūra, kuras mērķis dzīvē ir uzglabāt vārdus
Like A-L-i-c-e vai B-o-B.
Un kādā veidā šie dati veikali Alise un Bobs un Čārlijs un Anita un tā tālāk
ir tā izmanto masīvu, kurā glabāt Alice in a Trie,
mēs sākam pie saknes mezgla, kas izskatās masīvs,
un tas ir bijis rakstīts saīsināts pierakstā.
Autore izlaist abcdefg jo nav ar, ka nosaukumus.
Viņi tikai parādīja M un P un T, bet šajā gadījumā,
pieņemsim virzīties prom no Alice un Bob un Čārlijs dažiem nosaukumiem, kas šeit.
Maxwell faktiski šajā diagrammā.
Tātad, kā to darīja autors veikalā M--x-W-e-l-l?
Viņš vai viņa sāka pie saknes mezgla, un devās uz [M], lai aptuveni 13 13 atrašanās masīvā.
Tad no turienes, tur rādītājs.
Rādītājs noved pie citu masīvu.
No turienes autors indeksēti vērā, ka masīva atrašanās vietā A, kā attēlots tur augšā pa kreisi,
un tad viņš vai viņa sekoja šim rādītāju uz citu masīvu,
un devās uz Bultiņas atrašanās X.
Tad nākamajā masīva atrašanās W, E, L, L, un tā tālāk,
un visbeidzot, pieņemsim faktiski mēģina ievietot attēlu ar šo.
Ko nozīmē mezglu izskatīsies kodu?
Ir Trie mezgls ietver masīvu norādes uz vairāk punktiem.
Bet tur ir arī tagad ir sava veida Būla vērtība, vismaz šajā īstenošanā.
Es notikt, lai izsauktu to is_word. Kāpēc?
Jo, kad jūs Ievietojot Maxwell, jūs ne ievietojot
kaut šajā datu struktūra.
Jūs neesat rakstiski M. Tu ne rakstiski X.
Visi jūs darāt, ir šādas norādes.
Rādītājs, kas atspoguļo m, tad rādītāju, kas pārstāv,
tad rādītājs, kas pārstāv X, tad W, E, L, L,
bet to, kas jums jādara, beigās ir veida iet, pārbaudiet, es sasnieguši šo vietu.
Tur bija vārds, kas beidzas šeit datu struktūru.
>> Tātad, kādi Trie ir patiešām piepildīta ar un autors izvēlējās pārstāvēt
šie terminuses ar nelielu trīsstūri.
Tas tikai nozīmē, ka tas tas trīsstūris ir šeit, tas Būla vērtība patiess
nozīmē, ja jums iet atpakaļ kokā,
tas nozīmē, ka vārdu nosaukts Maksvels ir šis.
Bet vārds foo, piemēram,
nav koku, jo, ja es sāktu pie saknes mezgla šeit augšā,
Nav f rādītājs, ne o rādītājs, ne o rādītājs. Foo nav vārdu šajā vārdnīcā.
Bet tieši pretēji, Turing, t-U-R-i-n-g. Atkal, man nebija glabāt t vai u vai R vai es vai N vai g.
Bet es tomēr veikalu šajā datu struktūru vērtību patieso ceļu uz leju šeit šajā mezglā - kokā
nosakot šo boolean vērtību is_word taisnība.
Tātad Trie ir veida šo ļoti interesanto meta struktūru,
kur jūs neesat īsti glabāšanai vārdi paši par šāda veida vārdnīcas.
Lai būtu skaidrs, jūs vienkārši uzglabāt jā vai nē, ir vārds, kas beidzas šeit.
>> Tagad to, kas ir saistība?
Ja jums ir 150,000 vārdus vārdnīcā, ka jūs mēģināt saglabāt atmiņā
izmantojot kaut kā saistīts saraksts,
Jums nāksies 150,000 punktiem savā saistīts saraksts.
Un atrast vienu no šiem vārdiem alfabēta varētu veikt O (n) laiks.
Lineārā laika. Bet šajā gadījumā par Trie,
kāda ir darbības laiks atrast vārdu?
Izrādās skaistums ir tas, ka pat tad, ja jums ir 149.999 vārdus jau šajā vārdnīcā,
kas īstenota ar šo datu struktūru,
cik daudz laika tas veic, lai atrastu vai ievietot vēl vienu personu vērā, ka, piemēram, Alice, Alice?
Nu, tas ir tikai 5, varbūt 6 soļi par trailing raksturs.
Sakarā presense ar citiem nosaukumiem struktūrā
nesaņem ceļā ievietojot Alice.
Turklāt, meklējot Alise reiz ir 150,000 vārdus šajā vārdnīcā
nav iegūt savā veidā, lai atrastu Alise vispār,
jo Alise ir. . . . . šeit, jo es atklāju boolean vērtību.
Un, ja nav Būla taisnība, tad Alise nav šajā datu struktūru vārdiem.
Citiem vārdiem sakot, darbības laiks atrast lietas un ievietojot lietas vērā šo jauno
datu struktūra Trie ir O no - tas nav n.
Sakarā 150,000 cilvēku presense nav nekādas ietekmes uz Alise, šķiet.
Tāpēc sauksim to k, kur k ir maksimālais garums vārdu angļu valodā
kas parasti ir ne vairāk kā 20 kaut rakstzīmes.
Tātad k ir nemainīgs. Tātad Svētais Grāls mēs, šķiet, esam atraduši tagad
ir, ka Trie, pastāvīgu laiku iestarpinājumus, lookups, lai svītrojumiem.
Jo vairākas lietas jau struktūrā,
kas nav pat fiziski tur. Atkal, viņi vienkārši veida pārbauda off, jā vai nē,
neietekmē tās turpmāko darba laika.
>> Bet tur ir nokļuvis būt nozvejas, citādi mēs nebūtu veltīgi tik daudz laika
uz visiem šiem citiem datu struktūrās tikai, lai beidzot iegūtu uz slepeno vienu, kas ir pārsteidzošs.
Tātad kādu cenu mēs maksāt, lai sasniegtu šo diženumu šeit? Telpa.
Šī lieta ir milzīgi. Un iemesls tam, ka autors
nesniedza to šeit, ievērosiet, ka visas šīs lietas, kas izskatās masīvi,
viņš nav vērst pārējo koka, pārējā Trie,
tāpēc, ka viņi vienkārši nav saistīti ar stāstu.
Bet visi šie mezgli ir super plašs, un katrs koks mezgls aizņem
26 vai tiešām, varētu būt 27 rakstzīmes, jo šajā gadījumā man bija tostarp kosmosa par apostrofam
lai mēs varētu būt apostrophized vārdus.
Šajā gadījumā tie ir platas masīvi. Tātad, pat ja viņi nav picutured,
Tas aizņem milzīgu summu RAM.
Kas varētu būt labi, especilly mūsdienu aparatūru,
bet tas tradeoff. Mēs saņemt mazāk laika tērējot vairāk vietas.
Tātad, ja ir tas viss notiek?
Nu, pieņemsim do - pieņemsim skatīt šeit.
Darīsim lēkt uz šo puisis šeit.
>> Ticiet vai ne, tik daudz prieka kā C ir kādu laiku tagad,
mēs sasniedzot punktu semestra kur tas ir laiks, lai pārietu uz lietām vairāk mūsdienu.
Lietas, par augstākā līmenī. Un, pat ja par nākamo pāris nedēļu laikā
mēs joprojām turpina iegremdēt sevi pasaulē norādes un atmiņas vadība
lai iegūtu, ka komfortu, ar kuru mēs varam veidot uz,
beigās spēle galu galā ir ieviest, ironiskā kārtā, nevis šī valoda.
Mēs tērēt, piemēram, 10 minūtes runā par HTML.
Viss HTML ir ir iezīmēšanas valoda, un kāda iezīmēšanas valoda ir
ir šie sērijas atvērtām iekavām un slēgtās kronšteini, kas saka "padara šo bold"
"Padarīt šo kursīvā '' padara šo centrēts."
Tas vēl nav viss, kas intelektuāli interesanti, bet tas ir super noderīga.
Un tas noteikti visuresošs šajās dienās.
Bet kas ir spēcīgs par pasaules HTML, un web programmēšana kopumā,
būvē dinamisko lietas; rakstot kodu valodās, piemēram, PHP vai Python vai Ruby vai Java vai C #.
Tiešām, neatkarīgi no jūsu valodu izvēle ir, un radot HTML dinamiski.
Radīt kaut ko sauc CSS dinamiski.
Kaskādes stila lapas, kas arī ir par estētiku.
Un tā pat, šodien, ja es eju uz kādu tīmekļa vietni, piemēram iepazinušies Google.com,
un es iet, lai apskatītu, attīstītājs, apskatīt avota, kas varbūt jūs esat darījuši agrāk,
bet iet apskatīt avotu, šī stuff droši vien izskatās diezgan noslēpumains.
Bet tas ir pamatā kods, kas īsteno Google.com.
Uz priekšējā galā. Un patiesībā tas viss ir pūkains estētika sīkumi.
Tas ir CSS šeit. Ja es glabāt ritinot uz leju mēs iegūt kādu krāsu kodēta sīkumi.
Šis ir HTML. Google koda izskatās haoss, bet, ja es tiešām atvērt citu logu,
mēs varam redzēt dažus struktūru šo.
Ja es atveru šo augšu, pamanīt šeit, tas ir mazliet vieglāk saprotamus.
Mēs ejam, lai redzētu, pirms ilgi šo tagu, [vārds] ir tag,
HTML, galvas, ķermeņa, div, skripts, teksta apgabals, standarta, centrēts, div.
Un tas ir arī sava veida mistisks izskatīgs pēc pirmā acu uzmetiena,
bet visu šo putru šādi noteiktiem modeļiem un atkārtojamiem modeļus,
tāpēc, ka, tiklīdz mēs iegūt pamatus uz leju, jūs varēsiet rakstīt kodu, kā šis
un tad manipulēt kodu, piemēram, tas, izmantojot vēl vienu valodu, ko sauc JavaScript.
Un JavaScript ir valoda, kas darbojas iekšpusē pārlūku
ka šodien mēs izmantot par Hārvardas kursus, par kursu iepirkšanās rīks, ka Google Maps izmanto
lai dotu jums visu ķekars dinamismu, Facebook dod jums, lai parādītu instant statusa atjauninājumus,
Twitter to izmanto, lai parādītu jums tweets uzreiz.
Tas viss mēs sāksim iegremdēt sevi collas
Bet tur nokļūt, mums ir jāsaprot, mazliet kaut ko par internetu.
Šis klips šeit ir tikai minūti gara, un pieņemsim, tagad tas ir, faktiski,
kā internets darbojas kā teaser par to, kas ir apmēram nāk. Es jums "Warriors no tīkla."
>> [♫ Lēna koris mūzika ♫]
[Vīrietis stāstītājs] Viņš atnāca ar ziņu.
Ar protokolu viss viņa paša.
[♫ Ātrāk elektroniskās mūzikas ♫]
Viņš nāca pasaulē atdzist ugunsmūru, uncaring maršrutētājiem,
un briesmas daudz sliktāk nekā nāvi.
Viņš ir ātrs. Viņš ir spēcīgs. Viņš TCP / IP, un viņš ieguva savu adresi.
Karavīri no Net.
[Malan] Nākamnedēļ, tad. Interneta. Web programmēšana. Tas ir CS50.
[CS50.TV]