[Powered by Google Translate] [Review] [Quiz 0] 

[Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University] 

[Þetta er CS50.] [CS50.TV] 

Hey, allir. Velkomin endurskoðun fundur fyrir Quiz 0, sem á sér stað í Miðvikudagur. Það sem við erum að fara að gera í kvöld, ég er með 3 önnur TFS, og saman við erum að fara að fara í gegnum endurskoðun á það sem við höfum gert í námskeiðinu svo langt. Það er ekki að fara að vera 100% tæmandi, en það ætti að gefa þér betri hugmynd af því þú hefur nú þegar niður og hvað þú þarft samt að læra fyrir miðvikudag. Og ekki hika við að hækka hönd þína með spurningum eins og við erum að fara eftir, en hafðu í huga að við munum einnig hafa smá tíma í lok- ef við fáum í gegnum nokkrar mínútur til vara til að gera almennar spurningar, þannig að það í huga, og svo ætlum við að byrja á byrjun með viku 0. 

[Spurningakeppni 0 frétta!] [Part 0] [Lexi Ross] En áður en við gerum sem við skulum tala um flutninga í spurningakeppni. 

[Logistics] [Quiz fer fram á miðvikudaginn 10/10 í stað fyrirlestri] 

[(Sjá http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf fyrir frekari upplýsingar)] Það er á Wednesday, October 10. 

Það er þetta miðvikudagur, og ef þú ferð á þessa slóð hér, sem er einnig aðgengileg frá CS50.net-það er tengill til þess- þú getur séð upplýsingar um hvar á að fara byggja á eftirnafn eða skóla tengsl og það segir um nákvæmlega hvað quiz mun ná og þær tegundir af spurningum sem þú ert að fara að fá. Hafðu í huga að þú munt einnig hafa tækifæri til að rifja upp fyrir prófið í kafla, svo TFS þín ætti að vera að fara yfir nokkrar æfa vandamál, og það er annað gott tækifæri til að sjá hvar þú þarft samt að læra allt fyrir próf. Við skulum byrja á byrjun með Bytes 'N' bits. Mundu a hluti er bara 0 eða 1, og bæti er safn af 8 af þeim bita. Við skulum líta á þetta safn bita hérna. Við ættum að vera fær um að reikna út hversu margir bitar eru. Þar við teljum það er bara 8 af þeim, átta 0 eða 1 einingar. Og þar er 8 bitar, sem er 1 bæti, og við skulum umbreyta það til sextánskur. Sextánskt er stöð 16, og það er frekar auðvelt að breyta fjölda í tvöfaldur, sem er það sem er að tala í sextánskur. Allt sem við gerum er að við horfum á hópa af 4, og við umbreyta þeim á viðeigandi sextánskur stafa. Við byrjum með hægri mestu hópi 4, svo 0011. Það er að fara að vera einn 1 og einn 2, svo saman sem gerir 3. Og þá skulum við líta á aðra blokk 4. 1101. Það er að fara að vera einn 1, einn 4 og ein 8. Saman sem er að fara að vera 13, sem gerir D. Og við munum minnast þess að í sextánskur við ekki bara að fara í 0 til 9. Við förum 0 gegnum F, svo eftir 9, 10 samsvarar, 11 til B, et cetera þar sem f er 15. Hér 13 er D, svo til að umbreyta það til aukastaf allt sem við gerum er að við í raun meðhöndla hverja stöðu sem valdi 2. Það er ein 1, einn 2, núll 4S, núll 8s, einn 16, et cetera, og það er svolítið erfitt að reikna í hausnum, en ef við förum á næstu glæru sjáum við svarið við því. 

Í meginatriðum erum við að fara yfir frá strax aftur til vinstri, og við erum að margfalda hverja stafa af sama krafti 2. Og mundu, að sextánskur við tákna þessar tölur með 0x í upphafi svo við ekki rugla ekki með heiltala. Endurmenntun á, þetta er ASCII Table, og það sem við notum ASCII til að landakort af stöfum í töluleg gildi. Mundu í dulmál pset við gert mikla notkun ASCII töflu í því skyni að nota ýmsar aðferðir við dulkóðun, að Caesar og Vigenère dulmál, að breyta mismunandi bréf í streng samkvæmt takkann gefin af notanda. Við skulum líta á smá ASCII stærðfræði. Þegar litið er á 'P' + 1, í formi karakter sem yrði Q, og muna að "'5 ≠ 5. Og hvernig nákvæmlega við viljum breyta milli þessara 2 formi? Það er í raun ekki of erfitt. Í því skyni að fá 5 við draga '0 ' vegna þess að það eru 5 staðir milli á '0 'og '5.' Til að fara í hina áttina við bætum bara 0, svo það er tegund af eins og venjulegur stærðfræði. Mundu bara að þegar eitthvað er vitna um það að það er eðli og því samsvarar gildi í ASCII töflunni. Flytja inn fleiri almenna tölvunarfræði efni. Við lærðum hvað reiknirit er og hvernig við notum forritun að framkvæma reiknirit. Dæmi um reiknirit er eitthvað mjög einfalt eins og athuga hvort tala sé jafnvel eða stakur. Til að muna við unga fólkið fjölda með 2 og athuga hvort niðurstaðan er 0. Ef svo er, er það jafnvel. Ef ekki, er það skrýtið. Og það er dæmi um raunverulega undirstöðu reiknirit. 

A lítill hluti af a fleiri taka þátt einn er tvöfaldur leit, sem við munum fara yfir síðar í endurskoðun fundur. Og forritun er hugtakið sem við notum til að taka reiknirit og umbreyta það til merkjamál the tölva getur lesið. 2 dæmi um forritun er klóra, sem er það sem við gerðum í viku 0. Jafnvel þótt við gerum ekki raunverulega gerð út kóðann það er leið til að innleiða Þetta reiknirit, sem er prentun tölurnar 1-10, og hér erum við að gera það sama í C forritunarmál. Þetta eru jafngild, bara skrifað á mismunandi tungumálum eða setningafræði. Við lærðum síðan um Boolean tjáningu, og Boole er gildi sem er annaðhvort satt eða ósatt, og hér oftsinnis Boolean tjáning fara inn í aðstæður, þannig að ef (x ≤ 5), Jæja, fórum við þegar x = 5, þannig að skilyrði sé að fara að meta til satt. Og ef það er satt, hvað númerið er undir ástandi er að fara að meta af tölvunni, þannig að band er að fara að prenta við hefðbundna framleiðslu, og hugtakið ástand vísar til hvað sem er inni í sviga í ef yfirlýsingu. Mundu alla rekstraraðila. Mundu && það og | | þegar við erum að reyna að sameina 2 eða fleiri skilyrði, == Ekki = að athuga hvort 2 hlutir eru jafnir. Mundu að = er fyrir verkefni en == er Boole rekstraraðila. ≤, ≥ og svo endanleg 2 eru sjálfstætt skýringar. Almenn endurskoðun á Boolean rökfræði hér. Og Boolean tjáning eru einnig mikilvæg í lykkjum, sem við munum fara yfir núna. Við lærðum um 3 tegundir af lykkjur svo langt í CS50, fyrir, á meðan, og gera á meðan. Og það er mikilvægt að vita að á meðan í flestum tilfellum við getum í raun notað hvaða tegund af lykkju yfirleitt Það eru ákveðnar tegundir af tilgangi eða sameiginleg mynstur í forritun sem sérstaklega kalla fyrir einn þessara lykkjur að gera það sem mest duglegur og glæsilegur að kóða það á þann hátt. Förum yfir hvað hver þessara lykkjur tilhneigingu til að vera nota oftast. 

Í for lykkju við yfirleitt þegar vita hversu oft við viljum iterate. Það er það sem við setjum á ástandi. Því i = 0, i <10, til dæmis. Við vitum nú þegar að við viljum gera eitthvað 10 sinnum. Nú, um while lykkju, almennt við ekki endilega vita hversu oft við viljum að lykkja til að keyra. En við vitum einhverskonar ástandi sem við viljum það til alltaf að vera satt eða alltaf að vera falskur. Til dæmis, er á meðan setja. Við skulum segja að er Boole breytu. Þó það er satt að við viljum að kóða til að meta, svo svolítið meira teygjanlegur, svolítið meira almennt en fyrir lykkju, en allir í lykkju getur einnig verið breytt í while lykkju. Að lokum, gera á meðan lykkjur, sem getur verið erfiðustu til að skilja strax, er oft notuð þegar við viljum meta kóðann fyrst áður en fyrsta skipti sem við athuga ástand. A sameiginlegur nota málið fyrir að gera á meðan lykkja er þegar þú vilt fá notandi inntak, og þú veist að þú vilt spyrja notanda fyrir hjálpina minnsta kosti einu sinni, en ef þeir gefa þér ekki góða inntak strax þú vilt halda að spyrja þá þar til þeir gefa þér góða inntak. Það er algengasta notkun gera á meðan lykkja, og við skulum líta á the raunverulegur skipulag þessara lykkjur. Þeir yfirleitt alltaf hafa tilhneigingu til að fylgja þessum mynstrum. 

Á að lykkja inni þú hefur 3 þætti: frumstilling, oftast eitthvað eins og int i = 0 þar sem ég er gegn, ástand, þar sem við viljum að segja keyra þetta fyrir lykkju svo lengi sem þetta ástand enn heldur, eins og ég <10, og svo að lokum, uppfærslu, sem er hvernig við hækka Teljarinn breyta á hverjum stað í lykkju. A sameiginlegur hlutur til að sjá að það er bara i + +, sem þýðir hækka i um 1 í hvert skipti. Þú getur líka gert eitthvað eins og i + = 2, sem þýðir að bæta 2 við i hvert skipti sem þú ferð í gegnum lykkjuna. Og þá að gera þetta bara átt við kóða sem raunverulega liggur hluti af hliðar. Og um while lykkju, í þetta sinn við höfum í raun frumstilling utan lykkju, svo til dæmis, við skulum segja að við erum að reyna að gera slíkt hið sama tegund af lykkju sem ég lýst bara. Við viljum segja int i = 0 áður en lykkja hefst. Þá gætum við sagt en i <10 gera þetta, þannig að sömu blokk af kóða sem áður, og að þessu sinni að uppfæra hluti af kóða, til dæmis, i + +, reyndar fer inni í lykkju. Og að lokum, fyrir að gera á meðan, það er svipað og while lykkju, en við verðum að muna að kóðinn mun meta þegar áður en ástand er kannað, svo gerir það miklu meira vit ef þú horfir á það í röð toppur til botn. Í gera á meðan lykkja kóðann metur áður en þú horfir jafnvel á meðan ástand, en a while lykkju, tékka það fyrst. Yfirlýsingar og breytum. Þegar við viljum til að búa til nýja breytu sem við viljum fyrst að frumstilla hana. 

Til dæmis, int Bar Frumstillir breytu bar, en það þýðir ekki að gefa það a gildi, svo það er þess virði bar núna? Við vitum það ekki. Það gæti verið einhver sorp gildi sem var áður í minni þar, og við viljum ekki að nota þá breytu þar til við að gefa í raun það gildi, svo við að lýsa því hér. Þá erum við að frumstilla það að vera 42 hér á eftir. Nú, auðvitað vitum við þetta er hægt að gera á einni línu, int Bar = 42. En bara til að hreinsa margar skref sem eru að fara á, yfirlýsing og frumstilling eru að gerast sérstaklega hér. Hún gerist á einu skrefi, og hið næsta, int Baz = Bar + 1, þessa yfirlýsingu hér að neðan, sem hækkar Baz, svo í lok þessa kóða blokk Ef við vorum að prenta verðmæti Baz það væri 44 því við að lýsa og frumstilla það að vera 1> Bar, og þá erum við að hækka það aftur með + +. Við fórum yfir þetta nokkuð stutta stund, en það er gott að hafa almenna skilning á því hvað þræði og viðburðir eru. Við gerðum aðallega þetta í grunni, svo þú getur hugsa um þræði sem mörgum röð af kóða í gangi á sama tíma. Í raun, líklega það er ekki í gangi á sama tíma, en svona abstractly við getum hugsa um það á þann hátt. 

Í grunni, til dæmis, við höfðum marga sprites. Það gæti verið framkvæmd mismunandi kóða á sama tíma. Ein gæti verið að ganga á meðan hinn er að segja eitthvað í öðru hluta skjásins. Viðburðir eru önnur leið til að aðgreina út rökfræði milli mismunandi þátta kóðanum þínum, og á grunni sem við gátum til að líkja atburðum með útvarpi, og það er í raun Þegar ég fæ, ekki þegar ég heyri, en í raun er það leið til að senda upplýsingar frá einum Sprite til annars. Til dæmis, getur þú vilt senda leikinn yfir, og þegar annar Sprite fær leikinn yfir, hún svarar á vissan hátt. Það er mikilvægt líkan til að skilja forritun. Bara til að fara yfir helstu viku 0, það sem við höfum farið yfir hingað til, skulum líta á þessa einföldu C program. Textinn kann að vera svolítið lítið áfram, en ég ætla að fara yfir það mjög fljótt. Við erum meðal 2 haus skrá efst cs50.h og stdio.h. Við erum þá að skilgreina fastann takmörk að vera 100. Við erum þá að innleiða helstu virkni okkar. Þar sem við ekki nota stjórn lína rifrildi hér við þurfum að setja tómið sem rök fyrir helstu. Við sjáum int yfir helstu. Það er aftur gerð, vegna áreturn 0 neðst. Og við erum að nota CS50 bókasafn virka fá int að spyrja notanda um inntak og geymum það í breytu X, svo við að lýsa x yfir, og við frumstilla hana með x = GetInt. 

Við athuga þá hvort notandinn gaf okkur góða inntak. Ef það er ≥ LIMIT við viljum skila villu kóða 1 og prenta villu. Og að lokum, ef notandi hefur gefið okkur gott inntak við erum að fara að veldi fjölda og prenta út þá niðurstöðu. Bara til að vera viss um að þeir allir högg heim þú getur séð merki um mismunandi hluta kóða hér. Ég nefndi stöðug haus skrá. Ó, int x. Gakktu úr skugga um að muna það er staðbundin breytu. Það andstæðum það frá alþjóðlegum breytu, sem við munum tala um svolítið síðar í endurskoðun fundur, og við erum að hringja í bókasafn virka printf, þannig að ef við hefðum ekki ma stdio.h hausaskrár myndum við ekki vera fær um að hringja printf. Og ég tel að örin sem fékk skera burt hér bendir til% d, sem er formatting band í printf. Það segir prenta út þessa breytu sem tala,% d. Og það er það í viku 0. Nú Lucas er að fara að halda áfram. Hey, krakkar. Ég heiti Lucas. Ég er sophomore í besta hús á háskólasvæðinu, Mather, og ég ætla að tala svolítið um viku 1 og 2,1. [Vika 1 og 2,1!] [Lucas Freitas] Eins Lexi var að segja, þegar við byrjuðum að þýða kóðann þinn frá grunni í C eitt af því sem við höfum tekið eftir er að þú getur ekki bara skrifa kóðann og keyra það með græna fána lengur. Raunverulega, þú þarft að nota nokkur skref til að gera C program verða executable skrá. Í grundvallaratriðum er það sem þú gerir þegar þú ert að skrifa forrit sem þú þýða hugmynd inn á tungumáli sem þýðanda skil, þannig að þegar þú ert að skrifa forrit í C hvað þú ert að gera er í raun að skrifa eitthvað sem þýðanda er að fara að skilja, og þá þýðandinn er að fara að þýða að kóða í eitthvað sem tölvan þín skilur. 

Og málið er, að tölvan þín er í raun mjög heimsk. Tölvan getur aðeins skilið 0s og 1s, svo reyndar í fyrstu tölvur fólk forritað venjulega nota 0s og 1s, en ekki lengur, guði sé lof. Við þurfum ekki að leggja á minnið röð fyrir 0s og 1s fyrir for lykkju eða um while lykkju og svo framvegis. Þess vegna höfum við þýðanda. Hvað þýðandinn gerir er að það þýðir í rauninni C kóða, í okkar tilviki, við tungumál sem tölvan mun skilja, sem er að mótmæla kóða og þýðandi sem við erum að nota heitir clang, þannig að þetta er í raun tákn fyrir clang. Þegar þú hefur program, þú þarft að gera 2 hluti. Fyrst þarftu að setja saman program, og þá þú ert að fara að keyra forritið þitt. Til að safna saman forrit sem þú hafa a einhver fjöldi af valkostur til að gera það. Sú fyrsta er að gera clang program.c á hvaða forrit er nafn program. Í þessu tilviki getur þú séð að þeir eru bara að segja "Hey, þýða forritið mitt." Þú ert ekki að segja "Ég vil þetta nafn fyrir áætlun minn" eða eitthvað. 

Seinni valkosturinn er að gefa nafn til program. Þú getur sagt clang-o og svo nafnið sem þú vilt the executable skrá til að vera nefndur sem og þá program.c. Og þú getur líka gera það forrit, og sjá hvernig í fyrstu 2 tilvikum Ég setti. C, og í þriðja sem ég hef bara forrit? Já, í raun að þú ættir ekki að setja. C þegar þú notar gera. Annars þýðandinn er í raun að fara að æpa á þig. Og líka, ég veit ekki hvort þið munið, en a einhver fjöldi af sinnum við einnig notað-lcs50 eða-LM. Það heitir hlekkur. Það segir bara þýðanda sem þú munt nota þau bókasöfn rétt þarna, þannig að ef þú vilt nota cs50.h þú ert í raun að slá clang program.c-lcs50. Ef þú gerir það ekki, að þýðandinn er ekki að fara að vita að þú ert að nota þessar aðgerðir í cs50.h. Og þegar þú vilt keyra forritið sem þú hefur 2 valkosti. Ef þú gerðir clang program.c þú ekki gefa nafn á forritinu. Þú þarft að keyra það með því að nota. / A.out. A.out er staðlað nafn sem clang gefur program ef þú gefur ekki það nafn. Annars þú ert að fara að gera. / Forrit ef þú gafst upp nafnið á forritinu, og líka ef þú did gera program nafn sem áætlunin er að fara að fá er nú þegar að fara að forrita sama nafn og c skrá. Þá erum við að tala um tegundir gagna og gögn. 

Grundvallaratriðum gögn tegundir eru það sama og litlu kassa sem þeir nota að geyma gildi, þannig að gögn tegundir eru í raun bara eins og Pokémons. Þeir koma í öllum stærðum og gerðum. Ég veit ekki hvort að hliðstæðan vit. Gögnin stærð veltur í raun á vél arkitektúr. Öll gögn stærðir sem ég ætla að sýna hér eru í raun fyrir 32-bita vél, sem er um er að ræða tæki okkar, en ef þú ert í raun kóðun Mac eða í Windows einnig sennilega þú ert að fara að hafa 64-bita vél, svo muna að gögn stærðir sem ég ætla að sýna hér er fyrir 32-bita vél. Sú fyrsta sem við sáum var int, sem er frekar einfalt. Þú notar int að geyma heiltölu. Við sáum einnig staf, sem char. Ef þú vilt nota bréf eða lítið tákn sem þú ert líklega að fara að nota bleikju. A bleikju hefur 1 bæti, sem þýðir 8 bitar, eins og Lexi sagði. Í grundvallaratriðum höfum við ASCII töflu sem hefur 256 mögulegar samsetningar 0s og 1s, og svo þegar þú slærð inn bleikju hún er að fara að þýða eðli að inntak þú tala um að þú ert í ASCII töflunni, eins og Lexi sagði. Við höfum einnig fljóta, sem við notum til að geyma aukastafi tölur. Ef þú vilt velja 3,14, til dæmis, þú ert að fara að nota flot eða tvöfalt sem hefur meiri nákvæmni. A fljóta hefur 4 bæti. A tvöfaldur er 8 bæti, þannig eini munurinn er að nákvæmni. Við höfum líka lengi sem er notað fyrir heiltölur og þú getur séð fyrir 32-bita vél int og lengi hefur sömu stærð, þannig að það skiptir í raun ekki skynsamleg að nota fyrir í 32-bita vél. 

En ef þú ert að nota Mac og 64-bita vél, reyndar fyrir löngu hefur stærð 8, svo fer það virkilega á arkitektúr. Fyrir 32-bita vél það ekki gera skilningarvit til að nota fyrir mjög. Og þá lengi lengi, hins vegar, hefur 8 bæti, svo það er mjög gott ef þú vilt hafa lengri heiltölu. Og að lokum, höfum við streng, sem er reyndar a char *, sem er bendi á char. Það er mjög auðvelt að hugsa um að stærð af the band er að fara að vera eins og fjölda stafa sem hægt er að hafa það, en í raun char * sjálft hefur stærð bendill til bleikju, sem er 4 bæti. Stærð á char * er 4 bæti. Það skiptir ekki máli ef þú ert með lítið orð eða bréf eða eitthvað. Það er að fara að vera 4 bæti. Við lærðum líka svolítið um steypu, Svo eins og þú sérð, ef þú ert til dæmis, forrit sem segir int x = 3 og svo printf ("% d", x / 2) gera þú krakkar vita hvað það er að fara að prenta á skjánum? 

Einhver? >> [Nemendur] 2. 1. >> 1, já. Þegar þú gerir 3/2 og það er að fara að fá 1,5, en þar sem við erum með heiltölu og það er að fara að hunsa aukastaf hluta, og þú ert að fara að hafa 1. Ef þú vilt ekki að gerast það sem þú getur gert, til dæmis, er að lýsa yfir fljóta y = x. Þá x sem nota til að vera 3 er nú að fara að vera 3.000 í y. Og þá er hægt að prenta y / 2. Reyndar ætti ég að hafa 2. þarna. Það er að fara að gera 3.00/2.00, og þú ert að fara að fá 1,5. Og við höfum þetta 0,2 f bara að biðja um 2 aukastaf eininga í aukastaf hluta. Ef þú ert með 0,3 f það er að fara að hafa í raun 1.500. Ef það er 2 það er að fara að vera 1,50. Við höfum einnig þetta mál hér. Ef þú fljóta x = 3.14 og þá er printf x þú ert að fara að fá 3.14. Og ef þú gerir x = int af X, sem þýðir skemmtun x og heiltala og þú prentað x nú þú ert að fara að hafa 3,00. Er það skynsamleg? Þar sem þú ert fyrst að meðhöndla X sem heiltölu, þannig að þú ert að hunsa aukastaf hluta, og þá þú ert prentun x. Og að lokum, þú getur líka gert þetta, int x = 65, og þá lýsa bleikju c = x, og svo ef þú prentað C þú ert í raun að fara að fá A, Svo í rauninni hvað þú ert að gera hér er það þýðing á heiltölu í eðli, bara eins og ASCII Table gerir. Við ræddum einnig um rekstraraðila stærðfræði. Flest af þeim eru ansi einfalt, svo +, -, *, /, og einnig við ræddum um unga fólkið, sem er afgangurinn af skiptingu 2 númer. Ef þú hefur 10% 3, til dæmis, það þýðir skipta 10 með 3, og hvað er afgangurinn? Það er að fara að vera 1, þannig að það er í raun mjög gagnlegt fyrir a einhver fjöldi af the programs. Fyrir Vigenère og Caesar Ég er nokkuð viss um að allir sem þú krakkar nota unga fólkið. Um rekstraraðila stærðfræði, að vera mjög varkár þegar sameina * og /. 

Til dæmis, ef þú gerir (3/2) * 2 hvað ertu að fara að fá? [Nemendur] 2. Já, 2, vegna þess að 3/2 er að fara að vera 1,5, en þar sem þú ert að gera starfsemi á milli 2 heiltölur þú ert í raun bara að fara að huga að 1, og svo 1 * 2 er að fara að vera 2, svo vera mjög varkár hvenær aðgerð tölur með heiltölur þar þú gætir fengið að 2 = 3, í því tilviki. Og einnig að vera mjög varkár um forgang. Þú ættir venjulega að nota sviga til að vera viss um að þú vitir hvað þú ert að gera. Nokkrir gagnlegir flýtivísar, auðvitað, er einn i + + eða i + = 1 eða með því að nota + =. Það er það sama og að gera i = i + 1. Þú getur einnig gert i - eða i - = 1, sem er það sama og i = i -1, eitthvað sem þú krakkar nota mikið í fyrir lykkjur, að minnsta kosti. Einnig, til *, ef þú notar * = og ef þú gerir það, til dæmis, i * = 2 er það sama og að segja að ég = i * 2, og það sama um skiptingu. Ef þú gerir i / = 2 það er það sama og i = i / 2. 

Nú um aðgerðir. Þið krakkar læra að aðgerðir eru mjög góð stefna að vista númer meðan þú ert að forrita, svo ef þú vilt að framkvæma sama verkefni í númerið aftur og aftur, sennilega þú vilt nota valkost bara svo að þú þarft ekki að afrita og líma kóðann aftur og aftur. Reyndar, helstu er fall, og þegar ég sýna þér snið aðgerð þú ert að fara að sjá að það er nokkuð augljóst. Við notum einnig aðgerðir frá sumum bókasöfnum, til dæmis, printf, GetIn, sem er frá CS50 bókasafn, og aðrar aðgerðir eins toupper. Allar þessar aðgerðir eru í raun til framkvæmda í öðrum bókasöfnum, og þegar þú setur þær tether skrá í upphafi forritinu þú ert að segja getur þú vinsamlegast gefið mér kóðann fyrir þeim aðgerðum þannig að ég þarf ekki að koma þeim með mér? Og þú getur líka skrifað eigin starfsemi þína, þannig að þegar þú byrjar að forritun þér grein fyrir að bókasöfn ekki allar aðgerðir sem þú þarft. Fyrir síðustu pset, td skrifaði við drögum, Scramble, og útlit, og það er mjög, mjög mikilvægt að vera fær um að skrifa virka vegna þess að þeir eru gagnlegar, og við notum þær allra tíma í forritun, og það sparar mikið af kóða. The snið af aðgerð er þetta. Við höfum aftur gerð í upphafi. Hvað er aftur gerð? Það er bara þegar aðgerð er að fara að koma aftur. Ef þú ert með virka, td þáttatilraun, sem er að fara að reikna út a aðfeldi heiltala, líklega það er að fara að skila heiltölu líka. Þá aftur tegund er að fara að vera int. Printf hefur í raun tegund aftur tóm vegna þess að þú ert ekki aftur neitt. Þú ert bara að prenta það á skjáinn og hætta að virka eftir. Síðan sem þú hefur nafnið á aðgerð sem þú getur valið. Þú ættir að vera svolítið sanngjarn, eins og ekki velja nafn eins og xyz eða eins x2f. Reyndu að gera upp nafn sem er vit í. 

Til dæmis, ef það er þáttatilraun, segja þáttatilraun. Ef það er aðgerð sem er að fara að draga eitthvað, nafn það draga. Og þá höfum við breytur, sem einnig kallast rök, sem eru eins og úrræði sem virka þarf frá kóða til að framkvæma verkefni hennar. Ef þú vilt reikna aðfeldi tölu sennilega þú þarft að hafa númer til að reikna þáttatilraun. Ein rök sem þú ert að fara að hafa er númerið sjálft. Og þá er að fara að gera eitthvað og skila gildi í lok nema það er ógilt virka. Við skulum sjá dæmi. Ef ég vil að skrifa fall sem sums allar tölur í fjölda heiltalna, fyrst af öllu, aftur tegund er að fara að vera int vegna þess að ég er með fjölbreytta heiltölur. Og þá er ég að fara að hafa fallið nafn eins sumArray, og þá er að fara að taka array sig að int nums, og þá lengd fylkisins þannig að ég veit hve mörg númer sem ég þarf að leggja. Og ég þarf að frumstilla breytilega kallast summa, til dæmis til 0, og í hvert skipti sem ég sé stak í fylki sem ég ætti að bæta því við fjárhæð, þannig að ég gerði fyrir lykkju. Rétt eins og Lexi sagði, þú int i = 0, i <lengd og i + +. Og fyrir hvert frumefni í fylki ég gerði summa + = nums [i], og þá er ég aftur summu, svo það er mjög einfalt, og það sparar mikið af kóða Ef þú ert að nota þessa aðgerð a einhver fjöldi af sinnum. Síðan tókum við að líta á aðstæður. Við höfum ef annað, og annað hvort. Við skulum sjá hvað er munurinn á milli þeirra. Taka a líta á þessar 2 númerum. Hver er munurinn á milli þeirra? Sú fyrsta er-grundvallaratriðum númerin vilt þú að segja Ef tala er +, -, eða 0. Sú fyrsta segir ef það er> 0 þá er það jákvætt. Ef það er = að 0 þá er það 0, og ef það er <0 þá er það neikvætt. 

Og hitt er að gera ef annað hvort, annars. Munurinn á milli tveggja er að þessi maður er í raun að fara að athuga hvort> 0, <0 eða = 0 þrisvar sinnum, þannig að ef þú hefur númer 2 td það er að fara að koma hingað og segja if (x> 0), og það er að fara að segja já, svo ég prenta jákvæð. En jafnvel þó að ég veit að það er> 0 og það er ekki að fara að vera 0 eða <0 Ég er samt að fara að gera það 0, það er <0, þannig að ég er í raun að fara innan IFS að ég þyrfti ekki að vegna þess að ég veit nú þegar að það er ekki að fara að uppfylla einhverjar af þessum skilyrðum. Ég get notað ef annað hvort, annars yfirlýsingu. Það segir í rauninni ef x = 0 Ég prenta jákvæð. Ef það er ekki, ég ætla að einnig að prófa þetta. Ef það er 2 ég ætla að gera þetta. Í grundvallaratriðum ef ég hefði x = 2 þú vilt segja if (x> 0), já, svo prenta þetta. Nú þegar ég veit að það er> 0 og að það fullnægi kröfum fyrst ef Ég ætla ekki einu sinni að fara að keyra þennan kóða. Kóðinn keyrir hraðar, reyndar, 3 sinnum hraðar ef þú notar þetta. Við lærðum líka um og og eða. Ég ætla ekki að fara í gegnum þetta vegna þess að Lexi þegar talað um þá. Það er bara && og | | rekstraraðila. 

Það eina sem ég segi er að vera varkár þegar þú ert 3 skilyrði. Nota sviga því það er mjög ruglingslegt þegar þú ert með ástand og annað eða annað. Nota sviga bara til að vera viss um að skilyrði þín skynsamleg vegna þess að í því tilfelli, til dæmis, getur þú ímyndað þér að það gæti verið fyrsta skilyrði og einn eða annan eða hafa 2 skilyrði sameina í og eða þriðji, svo bara að vera varkár. Og að lokum, talaði við um rofa. A rofi er mjög gagnlegt þegar þú ert með breytu. Við skulum segja að þú ert með breytu eins n sem geta verið 0, 1 eða 2, og fyrir hvert af þessum tilfellum þú ert að fara að framkvæma verkefni. Það má segja að kveikja á breytu, og það bendir til þess að gildið er þá eins gildi1 ég ætla að gera þetta, og þá skal ég brjóta, sem þýðir að ég ætla ekki að fara að horfa á eitthvað af öðrum tilvikum vegna þess að við ánægð þegar þessi mál og þá gildi2 og svo framvegis, og ég líka með sjálfgefna rofi. Það þýðir að ef það er ekki uppfylla eitthvað af þeim málum sem ég hafði að ég ætla að gera eitthvað annað, en það er valkvætt. Það er allt fyrir mig. Nú skulum hafa Tommy. Allt í lagi, þetta er að fara að vera Vika 3-ish. Þessir ert sumir af the efni sem við munum vera nær, Crypto, umfang, fylki, et cetera. Just a fljótur orð á dulritunarstjórneiningunni. Við erum ekki að fara að negla þetta heimili. 

Við gerðum þetta í pset 2, en prófið að tryggja að þú veist muninn milli Caesar dulmál og Vigenère dulmáli, hvernig bæði þeim dulmál vinna og hvað það er að dulkóða og hallmæla texta með þessar 2 veikar. Mundu að Caesar dulmál snýst einfaldlega hvern staf með sömu upphæð, að tryggja að þú unga fólkið með fjölda af bréfum í stafrófinu. Og Vigenère dulmál, hins vegar, snýst hvern staf með mismunandi magni, svo frekar en að segja hvert eðli snúið um 3 Vigenère birtir hvern staf með mismunandi upphæð eftir því sumir leitarorð þar sem hver stafur í leitarorð er nokkur mismunandi magn að snúa skýra textann með. Við skulum fyrst tala um mismunandi umfang. Það eru 2 mismunandi gerðir af breytum. Við höfum staðbundnum breytur, og þær eru að fara að vera skilgreind utan helstu eða utan hvaða aðgerð eða blokk, og þeir munu vera aðgengilegar hvar sem er í forritinu. Ef þú ert með virka og sem virka er meðan lykkja stóra Global breyta er aðgengileg alls staðar. A sveitarfélaga breyta, hins vegar, er scoped á stað þar sem það er skilgreint. 

Ef þú ert með virka hér, til dæmis höfum við þetta fall g, og inni g er breytilegt hér kallað y, og það þýðir að þetta er staðbundin breytu. Jafnvel þó að þessi breyta er kallað Y og þessi breyta er kallað Y þessar 2 aðgerðir hef ekki hugmynd um hvað staðbundnar breytur hvers annars eru. Á hinn bóginn, allt hér við segjum int x = 5, og þetta er utan gildissviðs aðgerð. Það er utan við helstu, þannig að þetta er alþjóðlegt breytu. Það þýðir að innan þessar 2 virka þegar ég segi x - eða x + + Ég er að opna sama x þar þessa Y og þessi y eru mismunandi breytur. Það er munurinn á alþjóðlegum breytu og staðbundin breytu. Eins og langt eins og hönnun varðar, stundum er það líklega betri hugmynd að halda breytur sveitarfélaga þegar þú getur hugsanlega þar með fullt af alþjóðlegum breytur er hægt að fá mjög ruglingslegt. Ef þú ert með fullt af störfum allra breyta sama þú gætir gleyma hvað ef þessi aðgerð óvart breytir þetta alheims, og þetta önnur aðgerð veit ekki um það, og það er að fá mjög ruglingslegt eins og þú færð meiri kóða. Gæsla breytur sveitarfélaga þegar þú getur hugsanlega er bara góð hönnun. Fylki, muna, er einfaldlega listi yfir þætti af sömu gerð. Inni í CI geta ekki lista eins og 1, 2,0, halló. Við getum bara ekki gert það. 

Þegar við lýsa fylki í C alla þætti að vera af sömu gerð. Hér ég hef fjölbreytta 3 heiltölur. Hér ég hef lengd fylkisins, en ef ég ætla bara að lýsa henni í setningafræði þar sem ég tilgreina hvaða alla þá þætti er ég ekki tæknilega þörf á þessari 3. The þýðanda er sviði nógur til að reikna út hversu stór fylki ætti að vera. Nú þegar ég þarf að fá eða setja the gildi af fylki þetta er setningafræði til að gera það. Þetta mun í raun breyta seinni þáttur í fylki því, muna, númer byrjar á 0, ekki 1. Ef ég vil lesa þessi gildi sem ég get sagt eitthvað eins og int x = array [1]. Eða ef mig langar til að setja þessi gildi, eins og ég er að gera hér, Ég get sagt array [1] = 4. Þessi tími aðgangur þætti með vísitölu þeirra eða stöðu þeirra eða hvar sem þeir eru í fylki, og að skráning hefst kl 0. Við getum einnig hafa fylki af fylki, og þetta er kallað multi-víddar array. Þegar við höfum multi-víddar array sem þýðir að við getum haft eitthvað eins og raðir og dálka, og þetta er bara ein leið til að visualizing þetta eða hugsa um það. Þegar ég er með multi-víddar array sem þýðir að ég ætla að byrja að þurfa meira en 1 vísitölu vegna þess að ef ég hef rist bara segja hvað röð þú ert í er ekki að gefa okkur tala. Það er í raun bara að fara að gefa okkur lista yfir númer. Við skulum segja að ég hef þetta fylki hérna. Ég fylki heitir rist, og ég er að segja 2 línur það og 3 dálka, og svo er þetta ein leið til að visualizing það. Þegar ég segi að ég vil fá hluti á [1] [2] sem þýðir að vegna þess að þetta eru línur fyrst og síðan dálka Ég ætla að hoppa til róa 1 þar sem ég sagði 1. 

Og ég ætla að koma hérna til dálki 2, og ég ætla að fá gildið 6. Skynsamleg? Multi-víddar fylki, muna, er tæknilega bara fylki af fylki. Við getum haft fylki af fylki af fylki. Við getum haldið áfram, en í raun ein leið til að hugsa um hvernig þetta er sett fram og hvað er að gerast er að sjón það í töflu eins og þessa. Þegar við framhjá fylki til að virka, þá eru þeir að fara að haga sér svolítið öðruvísi en þegar við framhjá reglulega breytum við virka eins standast int eða fljóta. Þegar við framhjá í int eða bleikju eða einhverju af þessum gögnum gerðum fórum bara að líta á hvort aðgerðin breytir gildi þeirrar breytu sem breyting er ekki að fara að breiða upp til að kalla virka. Með fjölda, hins vegar, sem mun gerast. Ef ég fara í fjölda að einhverju virka og að virka breytist sum atriði, þegar ég kem aftur upp í aðgerð sem heitir það array minn er nú að fara að vera öðruvísi, og orðaforða til að fylki er eru liðin með tilvísun, eins og við munum sjá síðar. Þetta tengist því hvernig ábendingum vinnu, þar sem þessi helstu tegundir gagna, á hinn bóginn, eru samþykkt af gildi. 

Við getum hugsað sem svo að gera afrit af einhverju breytu og þá liggur í eintak. Það skiptir ekki máli hvað við gerum við þá breytu. Starf aðgerð mun ekki vera kunnugt um að það var breytt. Fylki er bara svolítið öðruvísi í þeim efnum. Til dæmis, eins og við sáum bara, helstu er einfaldlega fall sem getur tekið í 2 rök. Fyrsta rök að helsta hlutverk er argc, eða fjölda rök, og seinni rök heitir argv, og þeir eru í raun gildi þeirra rök. Við skulum segja að ég er með forrit sem heitir this.c, og ég segi gera þetta, og ég ætla að keyra þetta á skipanalínunni. Nú til að fara í sumum rökum að forrita minn heitir þetta, Ég gæti sagt eitthvað eins og. / Þetta er cs 50. Þetta er það sem við ímyndað Davíð að gera á hverjum degi í flugstöðinni. En nú er helsta hlutverk innan brautarinnar hefur þessi gildi, svo argc 4. Það gæti verið svolítið ruglingslegt því virkilega að við erum aðeins á ferð fyrir er cs 50. Það er einungis 3. En mundu að fyrsta þáttur argv eða fyrsta rifrildi er nafn fallsins sig. Svo þýðir að við höfum 4 hluti hér, og fyrsti þátturinn er að fara að vera. / þetta. Og þetta mun vera fulltrúa sem streng. Þá eftir þættir eru það sem við slegið inn eftir nafni áætlunarinnar. Svo bara sem er til hliðar, eins og við sáum líklega í pset 2, muna að band 50 er ≠ tölunnar 50. Þannig að við getum ekki sagt eitthvað eins og: "int x = argv 3. ' 

Það er bara ekki að fara að gera skilningarvit, því þetta er band, og þetta er heiltala. Svo ef þú vilt að umbreyta á milli 2, mundu, við erum að fara að hafa þetta galdur virka kallast atoi. Sem tekur streng og skilar heiltölu fulltrúa innan strengsins. Svo það er auðvelt mistök að gera á spurningakeppni, bara að hugsa að þetta mun sjálfkrafa rétta tegund. En bara veit að þetta mun alltaf vera strengir jafnvel ef strengurinn inniheldur aðeins heiltölu eða staf eða fljóta. Svo nú skulum við tala um að keyra tíma. Þegar við höfum öll þessi reiknirit sem gera allt þetta brjálaður hluti, það verður mjög gott að spyrja: "Hversu lengi gera þeir taka?" Við fulltrúar að með eitthvað sem kallast asymptotic tákn. Svo þýðir þetta að - ja, við skulum segja að við séum að gefa reiknirit okkar sumir virkilega, virkilega, virkilega stór inntak. Við viljum spyrja: "Hversu lengi er það að fara að taka? Hversu mörg skref tekur það reiknirit okkar til að keyra sem fall af stærð inntak? " Svo er fyrsta leiðin sem við getum lýst hlaupa tíma með stór O. Og þetta er versta hlaupandi tími okkar. Þannig að ef við viljum að raða fylki, og gefum algrím okkar fylki sem er í röð þegar það ætti að vera í röð, sem er að fara að vera versta. Þetta er efri okkar bundið í hámarks tíma algrím okkar mun taka. Á hinn bóginn, þetta Ω er að fara að lýsa best í að keyra tíma. Svo ef við gefa þegar raðað array að flokka reiknirit, hversu lengi mun það taka að flokka það? Og þetta, þá lýsir, minni bundið að keyra tíma. Svo hér eru bara nokkur orð sem lýsa nokkrar algengar gangi sinnum. Þetta eru í hækkandi röð. Hraðasta hlaupandi tíma sem við höfum kallast stöðug. 

Það þýðir sama hversu margir þættir við gefa reiknirit okkar, sama hversu stór array okkar er flokkun það eða gera hvað sem við erum að gera til fylkisins mun alltaf taka sama magn af tíma. Svo við getum táknað að bara með 1, sem er fasti. Við leit einnig á lógaritmískum hlaupa tíma. Svo er eitthvað eins og tvöfaldur leit lógaritmískum, þar sem við skera vandamálið í tvennt í hvert skipti og það fá bara hærri þaðan. Og ef þú ert alltaf að skrifa O hvers þáttarannsókn reiknirit, þú sennilega ætti ekki að íhuga þetta sem daglegu starfi þínu. Þegar við saman í gangi sinnum það er mikilvægt að hafa í huga þetta. Svo ef ég er með reiknirit sem er O (n), og einhver annar hefur reiknirit O (2n) þetta eru í raun aðfellu jafngildir. Svo ef við ímynda n að vera stór tala eins eleventy milljarða: svo þegar við erum að bera saman eleventy milljörðum eitthvað eins eleventy milljarða + 3, skyndilega að +3 er ekki raunverulega gera a stór mismunur lengur. Það er þess vegna sem við erum að fara að byrja að skoða þetta til að vera jafngildar. Svo hluti eins og þessa Fastar hér, það er 2 x þetta eða bæta 3, Þetta eru bara fastar, og þetta er að fara að falla upp. Svo er það hvers vegna allir 3 þessara hlaupa sinnum eru eins og að segja að þeir eru O (n). Á sama hátt, ef við höfum 2 öðrum tímum hlaupa, við skulum segja að O (N ³ + 2n ²), getum við bætt við + N, + 7, og þá höfum við annað hlaupa tíma sem er bara O (N ³). aftur, er þetta það sama því að þetta - þetta eru ekki það sama. Þetta eru sömu hlutina, því miður. Svo þetta er það sama vegna þess að This N ³ er að fara að ráða þessa 2N ². 

Það er ekki það sama er ef við höfum keyrt sinnum eins og O (N ³) og O (n ²) því þetta N ³ er miklu stærri en þetta n ². Svo ef við höfum exponents, skyndilega byrjar þetta að máli, en þegar við erum bara að takast á við þætti eins og við erum hérna, þá er það ekki að fara að máli vegna þess að þeir eru bara að fara að detta út. Við skulum taka a líta á sumir af the reiknirit sem við höfum séð hingað til og tala um tíma hlaupa þeirra. Fyrsta leiðin til að leita að tala í lista, sem við sáum, var línuleg leit. Og framkvæmd línuleg leit er frábær einfalt. Við verðum bara lista, og við erum að fara að horfa á hvert einasta þáttur í lista þar er að finna fjölda sem við erum að leita að. Svo það þýðir að í versta falli, það O (n). Og versta hér gæti verið ef frumefni er síðasta þáttur, þá nota línulega leit við verðum að líta á hvert einasta þáttur þangað til við komum að síðasta til þess að vita að það var reyndar í listanum. Við getum ekki bara gefast upp á miðri leið og segja: "Það er líklega ekki þar." Með línuleg leit við verðum að líta á the heild hlutur. Besta-málið hlaupandi tími, hins vegar, er stöðug því að í besta tilfelli þáttur sem við erum að leita að er bara sá fyrsti á listanum. Svo það er að fara að taka okkur nákvæmlega 1 skref, sama hversu stór listi er ef við erum að leita að fyrsti þáttur í hvert skipti. 

Svo þegar þú leitar, muna, er það ekki þurfa að listi okkar að vera flokkaður. Þar sem við erum bara að fara að horfa yfir hverjum einasta frumefni, og það skiptir ekki máli hvaða röð þessir þættir eru inn A fleiri greindur leita reiknirit er eitthvað eins og tvöfaldur leit. Mundu að framkvæmd leit tvöfaldur er þegar þú ert að fara að halda að leita á miðjum listanum. Og vegna þess að við erum að horfa á miðju, krefjumst við þess að skráin sé raðað eða annað sem við vitum ekki hvar miðjan er, og við verðum að líta á allan listann til að finna það, og þá á þeim tímapunkti sem við erum bara að sóa tíma. Svo ef við höfum raðað lista og við finnum miðju, við erum að fara að bera saman á miðju til frumefni sem við erum að leita að. Ef það er of hátt, þá getum við gleymt rétt helmingur vegna þess að við vitum að ef þátturinn okkar er nú þegar of hátt og allt til hægri þessa frumefnis er enn hærra, þá þurfum við ekki að horfa þar lengur. Hvar á hinn bóginn, ef þátturinn okkar er of lágt, við vitum allt vinstra megin við að frumefni er of lágt, þannig að það skiptir í raun ekki skynsamleg að líta þar, heldur. This vegur, með hvert skref og hvert skipti sem við líta á miðju á listanum, við erum að fara að skera vandamál okkar í tvennt vegna þess að allt í einu við vitum a heild búnt af tölum sem ekki er hægt að sá sem við erum að leita að. 

Í sauðakóðanum þetta myndi líta eitthvað eins og þetta, og vegna þess að við erum að skera listann í hálfa hvert einasta skipti, versta falli hlaupa tíma okkar stökk frá línuleg til lógaritmískum. Svo skyndilega við höfum þig í áföngum í því skyni að finna stak í lista. Besta-málið hlaupandi tíma, þó, er enn stöðug því nú, við skulum bara segja að þátturinn sem við erum að leita að er alltaf nákvæmlega miðja upprunalegu skránni. Þannig að við getum vaxa lista okkar eins og stór eins og við viljum, en ef þátturinn sem við erum að leita að er í miðju, þá er bara að fara að taka okkur 1 skref. Svo er það þess vegna sem við erum O (log n) og Ω (1) eða stöðugur. Við skulum í raun keyra tvöfaldur leita á þessum lista. Svo skulum segja að við erum að leita að frumefni 164. The fyrstur hlutur sem við erum að fara að gera er að finna miðpunkt þessum lista. Það bara gerist svo að miðpunkt er að fara að falla á milli þessara 2 talna, þannig að við skulum bara geðþótta segja, í hvert skipti sem miðpunkt fellur á milli 2 númer, skulum bara umferð upp. Við þurfum bara að tryggja að við að gera þetta í hvert skref á leiðinni. Þannig að við erum að fara að umferð upp, og við erum að fara að segja að 161 sé um miðja lista okkar. Svo 161 <164, og hver þáttur til vinstri 161 er <164, svo að við vitum að það er ekki að fara að hjálpa okkur á öllum að byrja að horfa á hér vegna þess að þátturinn sem við erum að leita að getur ekki verið þar. Svo er það sem við getum gert við getum bara gleyma um það allt vinstri hluta á listanum, og nú bara telja frá hægri á 161 og áfram. 

Svo aftur, þetta er miðpunkt, við skulum bara umferð upp. Nú er 175 of stór. Þannig að við vitum að það er ekki að fara að hjálpa okkur að leita hér eða hér, þannig að við getum bara henda því í burtu, og að lokum munum við högg the 164. Einhverjar spurningar um tvöfaldur leit? Við skulum fara frá að leita í gegnum þegar-raðaða lista í raun og veru að taka lista yfir númer í hvaða röð og að þessi listi í hækkandi röð. Fyrsta reiknirit sem við skoðuðum heitir kúla tegund. Og þetta væri einfaldara af reiknirit sem við sáum. Bubble tegund segir að þegar einhverjar 2 þættir inni í listanum eru af stað, sem þýðir að það er meiri fjöldi til vinstri á lægri tölu, þá erum við að fara að skipta á þeim, því það þýðir að listinn verði "Meira raðað" en það var áður. Og við erum bara að fara að halda áfram þessu ferli aftur og aftur og aftur þar að lokum þætti konar kúla að rétta staðsetningu þeirra og við höfum raðað lista. 

The hlaupa tími er þetta að fara að vera O (n ²). Hvers vegna? Jæja, vegna þess að í versta tilfelli, við erum að fara að taka alla hluti, og við erum að fara að enda bera það hvert annað atriði á listanum. En í besta tilfelli, höfum við nú þegar raðað lista, kúla tegund er bara að fara að fara í gegnum einu sinni, segir "Nei. ég ekki gera neinar skiptasamninga, þannig að ég er búin." Þannig að við höfum best í gangi þegar Ω (n). Við skulum hlaupa kúla raða á lista. Eða fyrst, við skulum bara líta á einhverjum sauðakóðanum mjög fljótt. Við viljum að segja við viljum halda utan um, í hvert endurtekning á lykkju, halda utan um hvort við breytt hvaða atriði. Svo ástæðan fyrir því er, við erum að fara að hætta þegar við höfum ekki skipt hvaða atriði. Svo í byrjun lykkju okkar sem við höfum ekki skipt neitt, þannig að við munum segja að það er rangt. Nú erum við að fara að fara í gegnum listann og bera saman hluti sem ég að þáttur i + 1 og ef það er raunin að það er stærri tala til vinstri færri, þá erum við bara að fara að skipta á þeim. 

Og svo við erum að fara að muna að við skipti stak. Það þýðir að við þurfum að fara í gegnum listann amk 1 sinni enn vegna þess að ástand þar sem við hætt er þegar allur listinn er þegar raðað, sem þýðir að við höfum ekki gert neinar skiptasamninga. Svo er það hvers vegna ástand okkar niður hér "en nokkur atriði hafa verið skipti." Svo nú skulum við bara líta á þetta í gangi á lista. Ég hef lista 5,0,1,6,4. Bubble tegund er að fara að byrja alla leið til vinstri, og það er að fara að bera saman i þætti, svo 0 í i + 1, sem er þáttur 1. Það er að fara að segja, vel 5> 0, en núna 5 er til vinstri, þannig að ég þarf að skipta um 5 og á 0. Þegar ég skipta þá, skyndilega ég fengið þessar mismunandi lista. Nú 5> 1, þannig að við erum að fara að skipta á þeim. 5 er ekki> 6, þannig að við þurfum ekki að gera neitt hér. En 6> 4, þannig að við þurfum að skipta. Aftur þurfum við að keyra í gegnum allan listann til að lokum uppgötva að þetta eru út af röð, við skipta þeim, og á þessum tímapunkti þurfum við að keyra í gegnum lista 1 meiri tíma að ganga úr skugga um að allt er í röð þeirra, og á þessum tímapunkti kúla tagi er lokið. A mismunandi reiknirit til að taka nokkur atriði og flokkun þá er val konar. Hugmyndin á bak við tegund val er að við erum að fara að byggja upp raðað hluta listanum 1 þáttur í einu. 

Og hvernig ætlum við að gera það er með því að byggja upp vinstri hluti af listanum. Og í rauninni, hvert - á hverju skrefi, þá ætlum við að taka minnstu hluti sem við höfum til vinstri sem hefur ekki verið raðað enn, og við erum að fara að færa það inn í þessi raðaða hluta. Það þýðir að við þurfum að stöðugt að finna lágmarks óflokkuðu þáttur og síðan taka að lágmarki þáttur og skipta um það með hvaða vinstri-mest þáttur sem er ekki raðað. Run tími er þetta að fara að vera O (n ²) vegna þess að í versta falli við þurfum að bera hvert einasta þáttur að sérhver önnur frumefni. Þar sem við erum að segja að ef við byrjum á vinstri hluta á listanum, við þurfum að fara í gegnum allt hægri hluti til að finna minnstu frumefni. Og þá aftur, við þurfum að fara yfir alla rétta hluti og að fara yfir það aftur og aftur og aftur. Það er að fara að vera N ². Við erum að fara að þurfa að innan lykkja annars fyrir lykkju sem bendir n ². Í besta falli hugsun, við skulum segja að við séum að gefa það þegar raðað lista; við í raun gera ekki allir betri en n ². Vegna val tegund hefur enga leið að vita það lágmarks þáttur er bara það sem ég gerst að vera að horfa á. Það þarf samt að ganga úr skugga um að þetta er í raun lágmarki. 

Og eina leiðin til að ganga úr skugga um að það er það lágmark, að nota þennan reiknirit, er að horfa á hvert einasta þáttur aftur. Svo í raun, ef þú gefur það - ef þú gefur val raða þegar raðað lista, það er ekki að fara að gera eitthvað betra en að gefa það upp lista sem er ekki raðað enn. Við the vegur, ef það gerist að vera að ræða um að eitthvað sé O (eitthvað) og Omega um eitthvað, getum við bara segja meira succinctly að það er θ um eitthvað. Svo ef þú sérð að koma upp hvar sem er, það er það sem einfaldlega þýðir. 

Ef eitthvað er Þeta á n ², er það bæði stór O (n ²) og Ω (n ²). Svo besta tilfelli og versta tilfelli, er það ekki máli, reiknirit er að fara að gera það sama í hvert skipti. Svo er þetta það sauðakóðanum fyrir tegund val gæti litið út. Við erum í rauninni að fara að segja að ég vil iterate á lista frá vinstri til hægri, og á hverjum endurtekning lykkju, ég er að fara að flytja lágmarks þáttur í þessu raðað hluta á listanum. Og þegar ég flyt eitthvað þarna, ég þarf aldrei að líta á frumefni aftur. Því um leið og ég skipti stak á vinstri hluta á listanum, er það flokkað vegna þess að við erum að gera allt sem í hækkandi röð með lágmarki. Svo við sögðum, allt í lagi, við erum í stöðu i, og við þurfum að líta á alla þá þætti til hægri á ég til að finna amk. Svo þýðir það að við viljum að líta frá i + 1 til loka listanum. Og nú, ef þáttur sem við erum nú að leita að er minna en minnst okkar svo langt, sem mundu, við erum að byrja lágmarks burt að bara vera hvað þátturinn sem við erum nú í, ég geri ráð fyrir að er lágmark. Ef ég finn stak sem er minni en það, þá er ég að fara að segja allt í lagi, Jæja, ég hef fundið nýja lágmarki. Ég ætla að muna þar sem minnst var. 

Svo nú, þegar ég hef farið í gegnum það rétt óflokkuðu hluti, Ég get sagt að ég ætla að skipta um lágmarks þáttur með atriði sem er í stöðu i. Það er að fara að byggja upp listanum mínum, flokkað hlutdeild mín af listanum frá vinstri til hægri, og við gerum ekki alltaf að líta á frumefni aftur þegar það er í þeim hluta. Þegar við höfum skipti það. Svo skulum hlaupa val raða á þennan lista. Bláa þáttur hér er að fara að vera i, og rauði þáttur er að fara að vera að lágmarki þáttur. Svo byrjar ég alla leið til vinstri á listanum, svo í 5. Nú þurfum við að finna lágmarks óflokkuðu frumefni. Þannig að við segjum 0 <5, svo er 0 nýtt lágmark mín. 

En ég get ekki hætt þar, vegna þess að jafnvel þó að við getum viðurkenna að 0 er lítill, við þurfum að hlaupa í gegnum alla aðra þáttur á listanum til að vera viss. Svo 1 er stærri, 6 er stærri, 4 er stærri. Það þýðir að eftir að horfa á alla þessa þætti, ég hef ákveðið 0 er minnsta. Þannig að ég ætla að skipta um 5 og á 0. Þegar ég skipti að ég er að fara að fá nýjan lista, og ég veit að ég hef aldrei þurft að líta á 0 aftur vegna þess að þegar ég hef skipst það, hef ég flokkað það og við erum að gera. Nú það bara gerist svo að blár þáttur er aftur 5, og við þurfum að horfa á 1, 6 og 4 til að ákvarða að 1 er minnsta lágmark þáttur, þannig að við munum skipta um 1 og 5. Aftur þurfum við að líta á - bera 5 til 6 og 4, og við erum að fara að skipta á 4 og 5, og að lokum, bera saman þessir 2 tölur og skipta þeim þar til við fá raðað lista okkar. Einhverjar spurningar um tegund val? Allt í lagi. Við skulum fara í síðasta þráð hér, og það er endurkvæmni. 

Endurkvæmni, muna, þetta er í raun Meta hlutur þar sem virka ítrekað kallar sig. Svo á einhverjum tímapunkti, en fuction okkar er ítrekað að kalla sig, Það þarf að vera einhver benda á þar sem við hætt að kalla okkur. Vegna þess að ef við gerum það ekki, þá erum við bara að fara að halda áfram að gera þetta að eilífu, og áætlun okkar er bara ekki að fara að segja. Við köllum þetta ástand grunn tilfelli. Og stöð málið segir, frekar en að kalla á aðgerð aftur, Ég ætla bara að fara að fara aftur sumir gildi. Svo þegar við höfum skilað gildi, höfum við hætt að kalla okkur, og restin af símtöl sem við höfum gert svo langt getur einnig aftur. Andstæða grunn tilfelli er endurkvæma raunin. Og þetta er þegar við viljum gera annað símtal að virka sem við erum nú inn Og við sennilega, þó ekki alltaf, að nota mismunandi rök. 

Svo ef við höfum virka heitir F og F hringdi taka 1 rök, og við höldum bara að hringja f (1), f (1), f (1), og það bara gerist svo að þau rök 1 fellur í endurkvæma tilfelli erum við samt aldrei að fara að hætta. Jafnvel þótt við höfum grunn tilfelli, þurfum við að tryggja að lokum ætlum við að högg sem byggja mál. Við ekki bara að halda að dvelja í þessu endurkvæma tilfelli. Almennt, þegar við köllum okkur, við erum líklega að fara að hafa mismunandi rök hverju sinni. Hér er mjög einföld endurkvæma virka. Svo mun reikna aðfeldi tölu. Upp Efst hér höfum við stöð okkar tilviki. Í tilviki að n ≤ 1, við erum ekki að fara að hringja þáttatilraun aftur. Við erum að fara að hætta, við erum bara að fara að fara aftur sumir gildi. Ef þetta er ekki satt, þá erum við að fara að lemja endurkvæma okkar tilviki. Tilkynning hér að við erum ekki bara að hringja þáttatilraun (n), vegna þess að það myndi ekki vera mjög hjálpsamur. Við ætlum að hringja aðfeldi eitthvað annað. 

Og svo þú getur séð, að lokum ef við standast þáttatilraun (5) eða eitthvað, við erum að fara að hringja þáttatilraun (4) og svo framvegis, og að lokum ætlum við að ná þessu grunn tilfelli. Svo lítur þetta vel út. Við skulum sjá hvað gerist þegar við hlaupum í raun það. Þetta er á mánudaginn, og við skulum segja að helsta er að fara að kalla þetta aðgerð með rök (4). Svo sér þegar þáttatilraun og = 4, þáttatilraun vilja kalla sig. Nú, allt í einu, höfum við þáttatilraun (3). Svo þessar aðgerðir eru að fara að halda að vaxa þar til að lokum við högg stöð okkar tilviki. Á þessum tímapunkti, skilagildi er aftur (NX skilagildi þetta), skilagildi er NX skilagildi þetta. Að lokum þurfum við að lemja einhvern fjölda. Efst hér, segjum við aftur 1. Það þýðir að þegar við aftur að tala, við getum skjóta það burt stafla. Svo þetta aðfeldi (1) er lokið. Þegar 1 skilar, þetta aðfeldi (1) skilar, það aftur til 1. Skilagildi þessu, muna, var NX skilagildi þetta. Svo allt í einu, þetta strákur veit að ég vil aftur 2. 

Svo man, skila gildi þetta er bara NX skilagildi upp hér. Svo nú getum við sagt 3 x 2 og að lokum, hér getum við sagt þetta er bara að fara að vera 4 x 3 x 2. Og þegar þetta skilar, fáum við niður í eina heiltölu inni helstu. Einhverjar spurningar um endurkvæmni? Allt í lagi. Þannig að það er meiri tími fyrir spurningar í lok, en nú Jósef mun ná eftirstandandi efni. 

[Joseph Ong] Allt í lagi. Svo nú að við höfum talað um recursions, við skulum tala svolítið um hvað Mergesort er. Sameina tegund er í grundvallaratriðum önnur leið flokkun lista af tölum. Og hvernig það virkar, og Mergesort þú ert með lista, og það sem við gerum er að við segjum, við skulum skipta þessu í 2 helminga. Við munum fyrst hlaupa Mergesort aftur á vinstri helming, þá munum við keyra Mergesort á hægri hluta, og það gefur okkur nú 2 helminga sem eru flokkuð, og nú ætlum við að sameina þær helminga saman. Það er dálítið erfitt að sjá án þess að dæmi, þannig að við munum fara í gegnum tillögur og sjá hvað gerist. Svo þú byrjar með þessum lista, við skipt því í 2 helminga. Hlaupum Mergesort á vinstri hluta fyrst. Svo er það vinstri helming, og nú erum við að keyra þá í gegnum þennan lista aftur sem fær staðist í Mergesort, og þá erum við að líta aftur, á vinstri hlið af þessum lista og hlaupum Mergesort á það. Nú fáum við niður á lista yfir 2 númer, og nú er vinstri helmingur einungis 1 þáttur lengi, og við getum ekki skipt lista sem er aðeins 1 þáttur í helming, þannig að við segjum bara, þegar við höfum 50, sem er bara 1 þáttur, það er raðað nú þegar. 

Þegar við erum búin með það, getum við séð að við getum fara til hægri hluta lista, og 3 er einnig raðað, og svo nú að bæði helminga af þessum lista eru flokkuð við getum taka þessar tölur aftur saman. Svo við lítum á 50 og 3, 3 er minni en 50, þannig að það fer í fyrsta og þá kemur 50 tommur Nú, er það gert, við förum aftur upp að þeim lista og raða það er rétt helmingur. 42 er eigin númer það er, þannig að það er nú þegar raðað. Svo nú erum við að bera saman þessar 2 og 3 er minni en 42, svo að fær að setja í fyrsta, nú 42 fær sett í, og 50 verður sett inn Nú, það er raðað, förum alla leið aftur á toppinn, 1337 og 15. Jæja, lítum við nú á vinstri hluta lista, 1337 er af sjálfu sér þannig að það er raðað og sama með 15. Svo nú erum við að sameina þessar 2 tölur til að raða að upprunalega lista, 15 <1337, svo fer það í fyrstu, þá fer 1337 inn Og nú erum við raðað bæði helminga af upprunalegu lista upp topp. Og allt sem við þurfum að gera er að sameina þetta. Við lítum á fyrstu 2 tölur á þessum lista, 3 <15, svo það fer í röðun fylkisins fyrst. 15 <42, svo fer það inn Nú, 42 <1337, sem gengur inn 50 <1337, svo fer það inn og taka eftir því að við tókum bara 2 tölur burt af þessum lista. Þannig að við erum ekki bara að skiptast á milli 2 listum. Við erum bara að horfa á í upphafi, og við erum að taka þáttur það er minni og þá setja það inn í array okkar. Nú höfum við sameinast öll helminga og við erum að gera. 

Einhverjar spurningar um Mergesort? Já? [Nemandi] Ef það er að skiptast í mismunandi hópa, hví ekki að þeir hættu bara það einu sinni og þú hefur 3 og 2 í hóp? [Rest af óskiljanlegur spurningu] Ástæðan - svo er spurningin, hvers vegna getum við ekki sameinast bara þá á þessi fyrstu skref eftir að við höfum þá? Ástæðan að við getum gert þetta, byrja á vinstri flestum þáttum báðum hliðum, og þá taka minni einn og setja það á, er að við vitum að þetta einstakra listar eru í raðað pantanir. Svo ef ég er að leita á vinstri flestum þáttum beggja helminga, Ég veit að þeir eru að fara að vera minnsti þætti þessara lista. Þannig að ég get sett þá í minnstu þáttur blettur þessa stór listi. Á hinn bóginn, ef ég horfi á þá 2 lista í öðru stigi þarna, 50, 3, 42, 1337 og 15, eru þeir ekki raðað. Svo ef ég horfi á 50 og 1337, ég ætla að setja 50 í listanum mínum fyrst. En það er í raun ekki skynsamleg, því 3 er minnsti þátturinn úr öllum þeirra. Svo er eina ástæðan sem við getum gert þetta sameina skref vegna listum okkar eru þegar raðað. Hver er ástæða þess að við þurfum að fá niður alla leið til the botn vegna þess að þegar við höfum bara eitt númer, þú veist að ein tala í sjálfu sér er nú þegar raðað lista. 

Einhverjar spurningar? Nei? Flókið? Jæja, getur þú séð að í hverju skrefi það er endir tölur, og við getum deilt lista í log helmingur n sinnum, sem er þar sem við fáum þessa n x log n flókið. Og þú munt sjá það besta við um Mergesort er n log n, og það bara gerist svo að versta tilfelli, eða Ω þarna, er einnig N log n. Eitthvað til að hafa í huga. Að flytja á, við skulum fara á nokkur frábær undirstöðu skrá I / O. Ef þú lítur á Scramble, youll 'taka eftir við höfðum einhverskonar kerfi þar sem þú getur skrifað á annálinn ef þú lest í gegnum kóðann. Við skulum sjá hvernig þú gætir gert það. Jæja, við höfum fprintf, sem hægt er að hugsa um eins og bara printf, en bara prentun á skrá í staðinn, og þar með f í upphafi. Þessi tegund af kóða upp hér, hvað það gerir er, eins og þú gætir hafa séð í Scramble, það fer í gegnum 2-víddar array prentun út röð fyrir röð hvað tölurnar eru. Í þessu tilfelli, printf prentar út flugstöðinni eða það sem við köllum venjulegt framleiðsla kafla. 

Og nú, í þessu tilfelli, allt sem við þurfum að gera er að skipta printf með fprintf, segja það hvaða skrá þú vilt að prenta, og í þessu tilviki það prentar bara út til að skrá í stað þess að prenta það út til flugstöðinni. Jæja, þá bidur að spurningin: Hvar fáum við þessa tegund af skrá frá, ekki satt? Við fórum að skrá þig inn í þessa fprintf fuction en við höfðum ekki hugmynd um hvar það kom frá. Jæja, snemma í númerið, það sem við höfðum var þessi klumpur af kóða hérna, sem í grundvallaratriðum segir að opna skrá símtöl log.txt. Það sem við gerum eftir það er að við verðum að ganga úr skugga um að skrá er í raun opnað tekist. Þannig að það gæti mistekist mörgum ástæðum, þú þarft ekki nóg pláss á tölvunni þinni, td. Svo er það alltaf mikilvægt áður en þú gerir einhverjar aðgerðir með skrá að við athugum hvort þessi skrá var opnuð tókst. Svo það að, það er rifrildi í fopen vel, getum við opna skrá á marga vegu. Það sem við getum gert er, getum við fara framhjá það W, sem þýðir hunsa skrá ef það hættir nú þegar, Við getum framhjá a, sem þeir bæta við í lok skrá stað vega þyngra það, eða við getum tilgreina r, sem þýðir, við skulum opna skrána sem lesa-eini. Svo ef forritið reynir að gera neinar breytingar á skrá, öskra á þá og ekki láta þá gera það. Að lokum, þegar við erum búin með the skrá, búin að gera aðgerðir á henni, við þurfum að tryggja að við að loka skrá. Og svo í lok program, þú ert að fara að gefa þeim aftur þessi skrá sem þú hefur opnað, og bara loka því. Svo er þetta eitthvað mikilvægt að þú þarft að ganga úr skugga um að þú gerir. Svo muna að þú getur opnað skrá, þá er hægt að skrifa á skrá, gera starfsemi í skrá, en þá þarftu að loka skrá í árslok. 

Einhverjar spurningar um undirstöðu skrá I / O? Já? [Námsmaður spurning, óskiljanlegur] Hérna. Spurningin er, hvar er þetta log.txt skrá birtast? Jæja, ef þú gefur bara það log.txt, skapar það því í sömu möppu og executable. Svo ef Ertu - >> [Student spurning, óskiljanlegur] Já. Í sömu möppu, eða í sömu möppu, eins og þú kallar það. Nú minni, stafla og hrúga. Svo hvernig er minni lagði út í tölvunni? Jæja, getur þú ímyndað þér minni sem tegund þessa blokk hér. Og í minni við höfum það sem kallast hrúga fastur þarna, og stafla sem er þarna niðri. Og hrúga vex niður og stafla vex upp. Svo eins og Tommy nefnd - Jæja, og við höfum þessar aðrar 4 hluti sem ég ætla að fá í annað - Eins og Tommy sagði áðan, þú veist hvernig aðgerðir hans kalla sig og kalla hvert annað? Þeir byggja upp þessa tegund af stakkur ramma. Jæja, ef helstu símtöl Foo, foo fær setja á mánudaginn. Foo kallar Bar, Bar fá er sett á mánudaginn, og það verður sett á mánudaginn eftir. Og eins og þeir koma aftur, hver þeir fá tekið af stafla. Hvað halda öllum þessum stöðum og minni? Jæja, the toppur, sem er texti hluti, inniheldur forritið sjálft. Svo vél númer, það er það, þegar þú saman program. Næst allir frumstilla alþjóðlegum breytur. 

Svo þú ert á heimsvísu breytur í forritinu, og þú segir eins og a = 5, sem fær að setja í þeim flokki, og rétt undir því, þú hefur einhverjar forsniðinn alþjóðlegum gögnum, sem er bara int a, en þú segir ekki það er jafn neitt. Gera sér grein fyrir að þetta eru alþjóðlegt breytur, svo þeir eru utan helstu. Svo þýðir þetta allir alþjóðlegum breytur sem lýst en ekki forsniðin. Svo er það í hrúga? Minni úthlutað með malloc, sem við munum fá í smá. Og að lokum, með stafla þú hefur einhverjar staðbundnar breytur og hvaða aðgerðir sem þú gætir hringt í einhverju breytum þeirra. The síðastur hlutur, þú í raun ekki að vita hvað umhverfið breytur gera, en þegar þú keyrir forritið, það er eitthvað sem tengist, eins og þetta er notandanafn þess sem hljóp forritið. Og það er að fara að vera tegund af neðst. Hvað talna minni, sem eru sextánskur gildi, gildin á efstu byrja á 0, svo að þeir fara alla leið niður á botn. Í þessu tilfelli, ef þú ert á 32-bita kerfi, heimilisfangið neðst er að fara að vera 0x, eftir AF, því það er 32 bita, sem er 8 bytes, og í þessu tilviki 8 bæti jafngildir 8 sextánskur tölustafir. Svo niður þú ert að fara að hafa, eins og, 0xffffff, og allt þar sem þú ert að fara að hafa 0. Svo hvaða ert ábendingum? Sumir af þú mega ekki hafa fjallað þetta í kafla áður. en við fengum að fara yfir það í fyrirlestri, svo bendillinn er bara gögn tegund sem verslanir, í stað einhvers konar gildi eins og 50, hún geymir heimilisfang einhverjum stað í minni. Svona minni [óskiljanlegur]. Svo í þessu tilfelli, það sem við höfum er að, höfum við bendi á heiltölu eða int *, og það inniheldur þessa sextánskur heimilisfang 0xDEADBEEF. 

Svo það sem við höfum er, nú, þetta bendillinn stig á einhverjum stað í minni, og það er bara, gildið 50 er á þessum minni. Á sumum 32-bita kerfi, á öllum 32-bita kerfi, ábendingum taka upp 32 bita eða 4 bæti. En, td á 64-bita kerfi, ábendingum 64 bits. Svo er það eitthvað sem þú þarft að hafa í huga. Svo á endir-bita kerfi, bendillinn er endir bits langur. Ábendingar eru svona erfitt að melta án auka hlutum, þannig að við skulum fara í gegnum dæmi um dynamic minni úthlutun. Hvað dynamic minni úthlutun gerir fyrir þig, eða það sem við köllum malloc, það er hægt að úthluta einhvers konar gögnum utan setja. Svo er þetta gögn svona meira varanleg á meðan the program. Því eins og þú veist, ef þú lýsa x inni í aðgerð og að skilar, þú hefur ekki lengur aðgang að þeim gögnum sem var geymd í x. Hvaða ábendingar skulum gera er að þeir láta okkur geyma minni eða geyma gildi í mismunandi hluti af minni, þ.e. hrúga. Nú þegar við aftur úr virka, svo lengi sem við höfum músina að þeim stað í minni, þá er það sem við getum gert við getum bara líta á gildi þar. Við skulum líta á dæmi: Þetta er minni skipulag okkar aftur. Og við höfum þessa aðgerð, helstu. Hvað það gerir er - allt í lagi, svo einfalt, ekki satt - int x = 5, það er bara mismunandi á stafla í helstu. 

Á hinn bóginn, nú erum við að lýsa yfir músina sem kallar aðgerðina giveMeThreeInts. Og svo nú erum við að fara í þessa aðgerð og við að búa til nýja stafla ramma fyrir það. Hins vegar í þessu stafla ramma, lýsa við int * afleysingamanneskja, sem mallocs 3 heiltölur fyrir okkur. Svo stærð int mun gefa okkur hversu mörg bæti þetta int er, og malloc gefur okkur að margir bæti af plássi á hrúga. Svo í þessu tilfelli, höfum við búið til nóg pláss fyrir 3 heiltölur og hrúga er vegur þarna, sem er ástæða þess að ég hef dregið hana ofar. Þegar við erum að gera, við komum aftur upp hér, þú þarft aðeins 3 ints skilað, og það skilar tölu, í þessu tilfelli yfir þar sem minni er. Og við sett músina = rofi, og þarna höfum við bara aðra músina. En hvað það skilar er staflað hér og hverfur. Svo hverfur Temp, en við höldum samt veffang þar sem þessir 3 heiltölur eru inni í mains. Þannig að í þessum hóp eru ábendingar scoped staðnum fyrir staflað ramma, en minningin sem þeir vísa í hrúga. 

Er það skynsamleg? [Nemandi] Gætirðu endurtekið þetta? >> [Joseph] Já. Svo ef ég fer aftur bara smá, sérðu að afleysingamanneskja úthlutað sumir minni á hrúga upp þarna. Svo þegar þessi aðgerð, giveMeThreeInts skilar þessi stafla hér er að fara að hverfa. Og með það einhverju breyta, í þessu tilfelli, þetta músina sem var úthlutað í staflað ramma. Það er að fara að hverfa, en þar sem við aftur afleysingamanneskja og við setjum músina = hitastig, bendill er nú að fara að benda á sama minni stað eins og Temp var. Svo nú, jafnvel þó að við missa afleysingamanneskja, að heimamenn músina, við halda enn minni heimilisfang þess sem hún er að benda á að innan þeirrar breytu músina. Spurningar? Það getur verið góður af ruglingslegt efni ef þú hefur ekki farið yfir það í kafla. Við getum, TF mun örugglega fara yfir það og að sjálfsögðu getum við svarað spurningum í lok endurskoðun fundur fyrir þetta. En þetta er svona flókið málefni, og ég hef fleiri dæmi sem eru að fara að mæta sem mun hjálpa skýra hvaða ábendingum raun eru. 

Í þessu tilviki eru ábendingum jafngildir fylki, þannig að ég get bara notað þetta músina sem sama sem int array. Þannig að ég er að flokkun í 0, og breyta fyrsta heiltölu á 1, breyta annarri heiltölu til 2, og 3 heiltala 3. Svo meira á ábendingum. Jæja, man Binky. Í þessu tilfelli höfum við úthlutað músina, eða við lýsti bendi, en í upphafi, þegar ég lýsti bara músina, það er ekki að benda á að einhvers staðar í minni. Það er bara sorp gildi innan þess. Þannig að ég hef ekki hugmynd um hvar þetta bendillinn bendir til. Það hefur netfang sem er bara fyllt með er 0 og er 1 þar sem það var upphaflega lýst. Ég get ekki gert neitt með þetta þangað til ég kalla malloc á það og þá gefur það mér smá pláss á hrúga þar sem ég get sett gildi inni. Þá aftur, ég veit ekki hvað er inni í þessum minni. Svo er það fyrsta sem ég þarf að gera að athuga hvort kerfið hefði nóg minni að gefa mér til baka 1 heiltölu í fyrsta sæti, sem er ástæða þess að ég er að gera þetta stöðva. Ef bendillinn er núll, sem þýðir að það var ekki nóg pláss eða einhver önnur villa kom upp, þannig að ég ætti að hætta út af kerfinu mínu.  En ef það gerði ná árangri, nú get ég notað þessi músina og hvað * bendillinn er er það þannig þar sem heimilisfangið er þar sem gildi er, og það setur það jafnt 1. Svo hérna, við erum að athuga hvort að minni hendi. 

Þegar þú veist að það er til, er hægt að setja inn í það Hvaða gildi sem þú vilt setja inn í það, í þessu tilviki 1. Þegar við erum búin með það, þú þarft að losa þessi músina vegna þess að við þurfum að fara aftur til the kerfi sem minni sem þú baðst um í fyrsta sæti. Vegna þess að tölvan er ekki að vita þegar við erum búin með það. Í þessu tilfelli erum við sérstaklega að segja það, allt í lagi, við erum búin með þessi minni. Ef einhver önnur aðferð þarf það, einhver önnur forrit þarf á henni, ekki hika við að fara á undan og taka það. Það sem við getum líka gert er að við getum bara fá heimilisfang staðbundnum breytur á tökustað. Svo int x er innan staflað ramma Main. Og þegar við notum þessa merkið, þetta og rekstraraðila, hvað það gerir er það tekur x og x er bara gögn í minni, en það er heimilisfang. Það er staðsett einhvers staðar. Svo með því að kalla & x, hvað þetta gerir er að hún gefur okkur veffang x. Með þessu erum við að gera músina benda til þar sem x er í minni. Nú erum við bara að gera eitthvað eins og * x, við erum að fara að fá 5 til baka. Stjarnan er kallað dereferencing það. Þú fylgja netfang og þú færð virði það geymt þar. 

Einhverjar spurningar? Já? [Nemandi] Ef þú gerir það ekki 3-bent hlutur, er það saman samt? Já. Ef þú gera ekki 3-músina hlutur, það er samt að fara að taka saman, en ég ætla að sýna ykkur hvað gerist í annað, og án þess að gera það, það er það sem við köllum minni leka. Þú ert ekki að gefa kerfinu aftur minni, svo eftir smá stund að forritið er að fara að safna minni að það er ekki að nota, og ekkert annað hægt að nota það. Ef þú hefur einhvern tíma séð Firefox með 1,5 milljónir kílóbæti á tölvunni þinni, í Task Manager, það er það sem er að gerast. Þú hefur minni leka í kerfinu að þeir eru ekki meðhöndlun. Svo hvernig hjartarskinn bendillinn tölur vinna? Jæja, bendillinn tölur er tegund af eins og flokkun í fylki. Í þessu tilfelli, ég er með músina, og það sem ég gera er ég að gera músina benda á fyrstu frumefni þessa fjölda 3 heiltölur sem ég hef úthlutað. Svo nú hvað ég geri, stjörnu bendillinn breytist bara í fyrsta frumefnið í listanum. Star músina 1 stig hérna. Svo er bendillinn hérna, músina 1 er hérna, bendillinn +2 er hérna. 

Svo bara að bæta 1 er það sama og að færa í þessu fylki. Það sem við gerum er þegar við músina 1 þú færð heimilisfang hérna, og til að fá verðmæti í hérna, þú setja stjörnu í frá öllu tjáningu að dereference það. Svo, í þessu tilfelli, ég er að setja í fyrsta stað í þessu fylki á 1, annað stað til 2, og þriðja stað 3. Þá er það sem ég er að gera hérna er ég að prenta músina okkar 1, sem gefur bara mér 2. Nú er ég incrementing músina, svo bendillinn jafngildir músina +1, sem flytur það áfram. Og svo núna ef ég prenta út músina +1, músina +1 er nú 3, sem í þessu tilfelli prentar út 3. Og í því skyni að losa eitthvað, bendillinn að ég gefi það verður að benda á the byrjun af the array sem ég fékk til baka frá malloc. Svo, í þessu tilfelli, ef ég væri að hringja 3 hérna, þetta væri ekki rétt, því það er í the miðja af the array. Ég verð að draga til að fá að upprunalegum stað fyrstu fyrst blettur áður en ég get losað hann. Svo, hér er meiri þátt dæmi. Í þessu tilfelli erum við að úthluta 7 stafi í staf fylkisins. 

Og í þessu tilfelli það sem við erum að gera er að við erum að lykkja yfir fyrstu 6 þeirra, og við erum að setja þá til Z. Svo, fyrir int i = 0, i> 6, i + +, Svo, bendill + ég mun bara gefa okkur, í þessu tilviki, músina, bendillinn +1, bendill +2, músina +3, og svo framvegis og svo framvegis í lykkju. Hvað það er að fara að gera er að það gerist þetta netfang, dereferences það til að fá gildi, og breytingar sem gildi til Z. Síðan í lok muna þetta er band, ekki satt? Allir strengir þurfa að enda með núll lúkningarenda staf. Svo, hvað ég er í músina 6 Ég setti null Terminator staf inn Og nú það sem ég er í rauninni að gera hérna er að innleiða printf fyrir band, ekki satt? 

Svo, þegar er printf nú þegar hún er komin að enda á band? Þegar það hits the núll uppsögn staf. Svo, í þessu tilfelli, upprunalega bendillinn minn bendir á í upphafi þessa fylkisins. Ég prenta fyrstu persónu út. Ég færa hana yfir einn. Ég prenta þessi karakter út. Ég flyt það yfir. Og ég halda að gera þetta þangað til ég ná til enda. Og nú * endir bendillinn dereference þetta og fá núll uppsögn staf aftur. Og svo rekur meðan lykkja mína aðeins þegar þessi gildi er ekki tómt uppsögn staf. Svo nú er ég hætta út af þessu lykkju. Og svo ef ég draga 6 af þessum músina, Ég fer til baka alla leið að í upphafi. Mundu ég að gera þetta vegna þess að ég þarf að fara í upphafi til þess að losa það. 

Svo veit ég að var mikið. Eru einhverjar spurningar? Vinsamlegast, já? [Námsmaður spurning óskiljanlegur] Getur þú sagt að hávær? Því miður. [Nemandi] Á síðasta mynd rétt áður en þú leysti músina, Hvar varst þú að breyta í raun verðmæti músina? [Joseph] Svo, hérna. >> [Nemandi] Ó, allt í lagi. [Joseph] Svo ég bendi mínus mínus, hægri, sem flytur málið til baka einn, og þá skal ég losa það, vegna þess að þetta bendi að að benda á byrjun fylkisins. [Nemandi] En það yrði ekki þörf hefði þú hætt eftir þeirri línu. [Joseph] Þannig að ef ég hefði hætt eftir þetta, myndi þetta teljast minni leka, vegna þess að ég hafði ekki keyrt frjáls. [Nemandi] I [óskiljanlegur] eftir fyrstu þrjár línur þar sem þú hafði músina +1 [óskiljanlegur]. [Joseph] Uh-ha. Svo, hvað er spurning þarna? Því miður. Nei, nei. Fara, fara, vinsamlegast. [Nemandi] Svo, þú ert ekki að breyta gildi ábendingum. Þú vilt ekki hafa þurft að gera músina mínus mínus. [Joseph] Já, nákvæmlega. Svo, þegar ég bendi +1 og bendilinn 2, Ég er ekki að gera músina jafngildir músina +1. Svo, bendillinn bara helst að benda á í byrjun fylkisins. Það er aðeins þegar ég plús plús að það setur gildi aftur inn í músina, að það færist í raun þetta eftir. Allt í lagi. Fleiri spurningar? 

Aftur, ef þetta er svona yfirþyrmandi, þetta verður fjallað á fundi. Spurðu kennslu félaga þína um það, og við getum svarað spurningum í lokin. Og yfirleitt erum við ekki eins og að gera þetta mínus hlutur. Þetta hefur að krefjast mér að halda utan um hversu mikið ég hef á móti í fylki. Svo almennt, þetta er bara til að útskýra hvernig Pointer tölur virkar. En það sem við eins og venjulega að gera er að við eins og til að búa til afrit af músina, og þá munum við nota það eintak þegar við erum að flytja í kring í the band. Svo, í þessum tilfelli þú nota afrita til að prenta allt band, en við þurfum ekki að gera eins og músina mínus 6 eða halda utan um hversu mikið við fluttum í þetta, bara vegna þess að við vitum að upprunalega lið okkar er enn bent á byrjun lista og allt sem við breytt var þetta eintak. Svo almennt, breytt afrit af upprunalegu músina þína. Ekki reyna að raða í svona - áttina breyta frumritum. Reynt að breyta aðeins afrit af upprunalegu. Svo, eftir að þú þegar við framhjá band inn printf þú þarft ekki að setja stjörnu fyrir framan það eins og við gerðum með öllum öðrum dereferences, ekki satt? Svo, ef þú hefur prentað út allt band% s ráð er heimilisfang, og í þessu tilfelli músina eða í þessu tilfelli eins og fylki af stöfum. 

Íþróttir, char * s, og fylki eru það sama. Bendillinn er að stafi, og eðli fylki eru það sama. Og svo, allt sem við þurfum að gera er að fara í músina. Við þurfum ekki að fara í eins og músina * eða eitthvað svoleiðis. Svo eru fylki og ábendingum sama. Þegar þú ert að gera eitthvað eins og x [Y] hérna í fylki, hvað það er að gera undir hetta er það er að segja, allt í lagi, það er eðli array, svo það er bendi. Og svo x er það sama, og svo hvað það gerir er að það bætir Y til X, sem er það sama og áfram í minni það mikið. Og nú gefur x + y okkur einhvers konar heimilisfang, og við dereference heimilisfang eða fylgja á örina þar sem staðsetning í minni er og við fá verðmæti út úr þeim stað í minni. Svo, svo þessir tveir eru nákvæmlega það sama. Það er bara syntactic sykur. Þeir gera það sama. Þeir eru bara mismunandi syntactics fyrir hvert öðru. 

Svo, hvað getur farið úrskeiðis við ábendingum? Eins og a einhver fjöldi. Allt í lagi. Svo slæmur hlutur. Sumir slæmur hlutur þú geta gera er ekki að haka ef malloc símtöl skilar null, ekki satt? Í þessu tilfelli er ég að spyrja kerfið að gefa mér - það er að tala? Eins og 2 milljarða sinnum 4, vegna þess að stærð heiltala er 4 bæti. Ég er að biðja hann um eins og 8 milljarðar bæti. Auðvitað tölvan mín er ekki að fara að vera fær um að gefa mér það mikið minni til baka. Og við ekki athuga hvort það er núll, þannig að þegar við reynum að dereference það þarna - fylgja á örina til þar sem það er að fara að - við höfum ekki þessi minni. Þetta er það sem við köllum dereferencing núll músina. Og þetta veldur fyrst og fremst að segfault. Þetta er ein af þeim leiðum sem þú getur segfault. Aðrir slæmir hlutir sem þú getur gert - ó vel. Það var dereferencing núll músina. Allt í lagi. Annað slæmur hlutur - vel, að festa sem þú setur bara ávísun á það sem athugar hvort bendillinn er null og fara út úr kerfinu ef það gerist að malloc skilar núll músina. Það er XKCD grínisti. Fólk skilur það núna. Konar. 

Svo minni. Og ég fór yfir þetta. Við köllum malloc í lykkju, en í hvert skipti sem við köllum malloc Við erum að missa utan um hvar þetta bendillinn er að benda á að, vegna þess að við erum clobbering það. Svo fyrstu kalla til malloc gefur mér minni hérna. Bendillinn ábendingum mín til þessa. Nú, ég losa ekki það, svo nú er ég kalla malloc aftur. Nú bendir það hérna. Nú minni mitt er að benda á hérna. Bendir hérna. Bendir hérna. En ég hef misst utan um heimilisföng allra minni hérna að ég úthlutað. Og svo núna er ég ekki neina tilvísun til þeirra lengur. Svo get ég ekki losa þá við þessa lykkju. Og svo til þess að festa eitthvað eins og þetta, Ef þú gleymir að losa um minni og þú færð þetta minni leka, Þú þarft að losa minni innan þessa lykkju þegar þú ert búinn með það. Jæja, þetta er það sem gerist. Ég veit fullt af þú hata þetta. En nú - yay! Þú færð eins og 44.000 kílóbæti. Svo, losa þú það í lok lykkju, og það er að fara að bara losa minni í hvert skipti. Í meginatriðum, program þinn styður ekki hafa minni leka lengur. 

Og nú er eitthvað annað sem þú getur gert losa minni sem þú hefur beðið um tvisvar. Í þessu tilfelli, þú malloc eitthvað, breyta þú gildi. Þú losa hana einu sinni af því að þú sagðir að þú værir búinn með það. En þá erum við losna aftur. Þetta er eitthvað sem er ansi slæmt. Það er ekki að fara að byrja segfault, en eftir smá stund hvað þetta gerir er tvöfaldur frjáls þetta sé spillir hrúga uppbygging, og þú munt læra svolítið meira um þetta ef þú velur að taka bekk eins CS61. En fyrst og fremst eftir smá stund tölvan er að fara að fá rugla hvað minni stöðum eru þar og þar sem það er geymt - þar sem gögn eru geymd í minni. Og svo frjáls bendi tvisvar er a slæmur hlutur sem þú vilt ekki gera. 

Annað atriði sem getur farið úrskeiðis er ekki að nota sizeof. Svo, í þessu tilfelli þú malloc 8 bæti, og það er það sama og tvær heiltölur, ekki satt? Svo, það er alveg öruggt, en er það? Jæja, eins og Lucas talaði um á mismunandi arkitektúr, heiltölur eru af ýmsum lengdum. Svo, á tæki sem þú ert að nota, eru heiltölur um 4 bæti, en á nokkrum öðrum kerfi sem þeir gætu verið 8 bytes eða þeir gætu verið 16 bæti. Svo, ef ég nota bara þessa tölu hérna, Þetta forrit gæti vinna á tækinu, en það er ekki að fara að úthluta nóg minni á einhverju öðru kerfi. Í þessu tilfelli, þetta er það sem sizeof rekstraraðili er notað. Þegar við köllum sizeof (int), hvað þetta gerir er  það gefur okkur stærð heiltala á kerfi sem forritið er í gangi. Svo, í þessu tilfelli, sizeof (int) aftur 4 um eitthvað eins og tæki, og nú mun 4 * 2, sem er 8, sem er bara pláss nauðsynlegt fyrir tvær heiltölur. Á mismunandi kerfi, ef int er eins 16 bæti eða 8 bæti, það er bara að fara að skila nógu bæti til að geyma þá upphæð. 

Og að lokum, structs. Svo, ef þú vildir geyma Sudoku borð í minni, hvernig gætum við gert þetta? Þú might hugsa um eins og breytu í fyrsta hlutur, breytu fyrir annað hlutur, breytu í þriðja hlutur, breytu fyrir fjórða hlutur - slæmt, ekki satt? Svo, einn framför sem þú getur gert á toppur af það er að gera 9 x 9 fylki. Það er allt í lagi, en hvað ef þú vildir að tengja annað við Sudoku borð eins og það að erfitt er að borð er, eða, til dæmis, hvað stigafjöldi þinn er, eða hversu mikinn tíma það hefur tekið að leysa þetta borð? Jæja, hvað er hægt að gera er að þú getur búið til strúktúr. Það sem ég er í rauninni að segja er að ég er að skilgreina þessa uppbyggingu hérna, og ég er að skilgreina Sudoku borð sem samanstendur af stjórn sem er 9 X 9. 

Og hvað það hefur það hefur ábendingum á nafni vettvangi. Það hefur einnig x og y, sem eru hnit þar sem ég er núna. Það hefur líka tími [óskiljanlegur], og það hefur heildarfjölda færist ég hef inputted svo langt. Og svo í þessu tilfelli, get ég raða a heild búnt af gögnum inn bara eina byggingu í stað þess að hafa það eins og að fljúga í kring í eins mismunandi breytur sem ég get ekki í raun halda utan um. Og þetta gerir okkur hafa bara gott setningafræði fyrir konar tilvísun mismunandi hluti inni þessa strúktúr. Ég get bara gert board.board, og ég fá Sudoku borð aftur. Board.level, fæ ég hversu erfitt það er. Board.x og board.y gefa mér hint um hvar ég væri í stjórn. Og svo ég opna það sem við köllum sviðum í strúktúr. Þetta skilgreinir sudokuBoard, sem er ein tegund sem ég hef. Og nú erum við hér. Ég er með breytu sem heitir "Stjórn" í sudokuBoard tegund. Og svo nú get ég aðgang að öllum sviðum sem gera upp þetta skipulag hérna. 

Einhverjar spurningar um structs? Já? [Nemandi] Fyrir int x, y, lýst þér bæði í einni línu? >> [Joseph] Uh-ha. [Nemandi] Svo getur þú bara með þeim öllum? Eins og í X, Y comma sinnum það samtals? [Joseph] Já, þú gætir örugglega gert það, en ástæðan ég setti x og y á sömu línu - og spurningin er hvers vegna getum við ekki bara þetta á sömu línu? Hvers vegna eigum við ekki að setja bara allt þetta í sömu línu er x og y eru tengdar við hvert annað, og þetta er bara stylistically réttari, í vissum skilningi, því það er hópar tvennt á sömu línu sem eins konar varða á sama. Og ég skipt bara þetta sundur. Það er bara stíll hlutur. Það gerir virkni ekki máli af neinu tagi. Einhverjar fleiri spurningar um structs? Þú getur slegið inn Pokédex með strúktúr. A Pokémon hefur númer og það hefur bréf, sem eiganda, tegund. Og svo ef þú ert óákveðinn greinir í ensku fylking af Pokémon, er hægt að gera upp Pokédex, ekki satt? Allt í lagi, svalt. Svo spurningar um structs. Þeir eru tengjast structs. 

Að lokum, GDB. Hvað er GDB láta þig gera? Það gerir þér kleift að kemba program. Og ef þú hefur ekki notað gdb, hefði ég mælt með að horfa til skamms og bara að fara yfir það GDB er, hvernig þú vinnur með það, hvernig þú getur notað það, og prófa það á dagskrá. Og svo er það GDB leyfir þér að gera það gerir hlé á [óskiljanlegur] UP program og verklegt línu. Til dæmis, ég vil hlé framkvæmd á eins og línu 3 af áætlun minni, og á meðan ég er á línu 3 sem ég get prentað út öll þau gildi sem eru þar. Og svo það sem við köllum eins og stansa í línu er að við köllum þetta að setja breakpoint á þeirri línu og þá getum við prentað út breytur á the ástand af the program á þeim tíma. 

Við getum þá þaðan stíga í gegnum forritið línu-við-línu. Og þá getum við litið á stöðu stafla á þeim tíma. Og svo til að nota gdb, það sem við gerum er að við köllum clang á C skrá, en við verðum að fara framhjá það á-ggdb fána. Og þegar við erum búin með því að við að keyra bara gdb á leiðir framleiðsla skrá. Og svo þú fá eins massa texta svona, en í raun allt sem þú þarft að gera er að slá inn skipanir í upphafi. Brot helstu setur breakpoint á helstu. Listi 400 taldar línur af kóða í kringum línu 400. Og svo í þessu tilviki getur þú bara líta í kring og segja, ó, Mig langar að setja breakpoint í línu 397, sem er í línu, og þá keyrir forritið þitt inn í þessi skref og það er að fara að brjóta. Það er að fara að staldra við þar, og hægt er að prenta út, til dæmis gildi lágt eða hátt. Og þannig að það eru fullt af skipunum sem þú þarft að vita, og þessi myndasýning mun fara upp á heimasíðu, þannig að ef þú vilt bara að vísa þessum eða eins og setja þá á svindlari lak þína, ekki hika. 

Cool. Það var Quiz Review 0, og við munum halda fast í kring ef þú hefur einhverjar spurningar. Allt í lagi. 

 [Lófaklapp] 

[CS50.TV]