[Powered by Google Translate] [Агляд] [Віктарына 0]
>> [Lexi Рос, Томі MacWilliam, Лукас Фрейтас, Іосіф Ong] [Harvard University]
>> [Гэта CS50.] [CS50.TV]
>> Прывітанне, усім.
Сардэчна запрашаем на разгляд сесіі Віктарына 0, якое праходзіць у сераду.
Што мы збіраемся рабіць сёння вечарам, я з 3 іншымі ТФ,
і разам мы збіраемся прайсці праз агляд таго, што мы зрабілі ў ходзе гэтага часу.
Гэта не збіраецца быць на 100% ўсёабдымнай, але яна павінна даць вам больш поўнае ўяўленне
аб тым, што ў вас ужо ёсць ўніз і тое, што вы ўсё яшчэ трэба вывучыць, перш чым у сераду.
І не саромейцеся падымаць руку з пытаннямі, калі мы збіраемся разам,
але майце на ўвазе, што мы будзем мець трохі часу ў канцы-
калі мы пройдзем з некалькіх хвілін, каб запасных, каб зрабіць агульныя пытанні,
так што майце гэта на ўвазе, і таму мы збіраемся пачаць у пачатку тыдня з 0.
>> [Віктарына 0 Агляд] [Частка 0] [Lexi Ross] Але перш чым мы гэта зробім, давайце пагаворым аб
матэрыяльна-тэхнічнае забеспячэнне віктарыны.
>> [Лагістыка] [віктарыны адбудзецца ў сераду 10/10 замест лекцыі]
>> [(Гл. http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf падрабязнасці)] Гэта ў сераду, 10 кастрычніка.
>> Вось у гэтую сераду, і калі вы ідзяце на гэты адрас тут,
які таксама даступны з CS50.net-Там спасылка на яго-
Вы можаце ўбачыць інфармацыю аб тым, куды пайсці на аснове
Вашу прозвішча або школу прыналежнасці, а таксама
ён кажа менавіта пра тое, што тэст будзе ахопліваць і тыпаў пытанняў, што вы збіраецеся атрымаць.
Майце на ўвазе, што вы таксама будзеце мець магчымасць прагледзець на віктарыну ў раздзеле
так што вашыя ТФ павінны ісці на некаторыя практыкі праблемы,
і гэта яшчэ адзін добры шанец, каб убачыць, дзе вы ўсё яшчэ трэба вывучыць для віктарыны.
Давайце пачнем з самага пачатку з Б-н-біт.
Памятаеце, як толькі 0 або 1,
і байт ўяўляе сабой набор з 8 гэтых бітаў.
Давайце паглядзім на гэтую калекцыю бітаў прама тут.
Мы павінны быць у стане высветліць, колькі біт ёсць.
Дзе мы разлічваем ёсць толькі 8 з іх восем 0 або 1 шт.
А так як ёсць 8 біт, гэта 1 байт,
і давайце пераўтварыць яго ў шаснаццатковы.
Шаснаццаткавыя з'яўляецца падставай 16, і гэта даволі лёгка пераўтварыць
Лік у двайковай сістэме, якая з'яўляецца, што гэта такое, і іх лік у шаснаццатковае.
Усё, што мы робім, мы глядзім на групы па 4,
і мы канвертаваць іх у адпаведны шаснаццатковы.
Пачнем з самай правай групе 4, таму 0011.
Гэта будзе адна 1 і 1 2, так разам, што робіць 3.
А потым давайце паглядзім на іншы блок 4.
1101. Гэта будзе адна 1, 1 4, і адзін 8.
Разам што гэта будзе 13, што робіць D.
І мы будзем памятаць, што ў шаснаццатковай мы не проста ісці ад 0 да 9.
Мы ідзём ад 0 да F, так што пасля 9, 10 адпавядае,
Ад 11 да B, і гэтак далей, дзе F 15.
Тут 13 ўяўляе сабой D,
так, каб пераўтварыць яго ў дзесятковы усё што мы робім, мы на самай справе
ставіцца адзін да пазіцыі сілы 2.
Гэта адна 1, адна 2, нулявы 4s, 8s нуля, адной 16, і гэтак далей,
і гэта трохі цяжка вылічыць ў вашай галаве, але калі мы ідзем да наступнага слайд
мы бачым, адказ на гэтае пытанне.
>> Па сутнасці, мы збіраемся насупраць права вярнуцца да левых,
і мы памнажаючы кожную лічбу адпаведнай ступенню 2.
І памятайце, для шаснаццатковых пазначыць гэтыя лічбы з 0x ў пачатку
таму мы не блытайце яго з дзесятковы лік.
Працягваючы, гэта ASCII табліцы,
і тое, што мы выкарыстоўваем для ASCII з'яўляецца пераўтварэнне з знакаў у лікавыя значэння.
Памятаеце, у PSET крыптаграфіі мы шырока выкарыстоўвалі ASCII табліцы
Для выкарыстання розных метадаў крыптаграфіі,
Цэзар і шыфр Виженера, канвертаваць розныя літары
У радок у адпаведнасці з ключавымі задаецца карыстачом.
Давайце паглядзім на трохі ASCII матэматыцы.
Гледзячы на ​​'P' + 1, у знакавай форме, якая была б Q,
і памятайце, што '5 '≠ 5.
І як бы мы дакладна канвертаваць паміж гэтымі 2 формы?
Гэта на самай справе не занадта цяжка.
Для таго, каб атрымаць 5 мы адымаем '0 '
таму што ёсць 5 месцаў паміж '0 'і '5.
Для таго, каб пайсці па іншым шляху, мы проста дадамо 0,
так што гэта накшталт як рэгулярныя арыфметыка.
Толькі памятайце, што, калі нешта двукоссі, гэта характар
і, такім чынам, адпавядае значэнню ў табліцы ASCII.
Перамяшчэнне ў больш агульныя тэмы па інфарматыцы.
Мы даведаліся, што такое алгарытм і як мы выкарыстоўваем праграмаванні
для рэалізацыі алгарытмаў.
Некаторыя прыклады алгарытмаў нешта простае, як
праверкі, ці з'яўляецца лік цотных або няцотных.
Для гэтага памятаеце, што мы мода лік на 2 і праверыць, калі вынік роўны 0.
Калі гэта так, то гэта яшчэ. Калі няма, то гэта дзіўна.
І гэта прыклад сапраўды асноўны алгарытм.
>> Крыху больш складана 1 бінарны пошук,
якія мы разгледзім пазней у аглядзе сесіі.
І праграмаванні тэрмін, які мы выкарыстоўваем для прыняцця алгарытму
і пераўтварэнне яго ў код, кампутар можа чытаць.
2 прыкладу праграмавання Scratch,
што мы і зрабілі ў тыдзень 0.
Нават калі мы на самай справе не ўдрукуешся код гэта спосаб рэалізацыі
Гэты алгарытм, які друкуе нумары 01/10,
і тут мы зрабіць тое ж самае на мове праграмавання Сі.
Гэтыя функцыянальна эквівалентныя, толькі што напісаныя на розных мовах або сінтаксісу.
Затым мы даведаліся пра лагічных выразаў,
і лагічнае з'яўляецца значэнне, якое альбо праўду, альбо ілжыва,
і тут часта лагічныя выразы
Заходзім унутр умовах, так што калі (х ≤ 5),
Ну, мы ўжо ўсталяваныя х = 5, так што ўмова будзе ацаніць, дакладна.
І калі гэта праўда, што код пад ўмова
будзе ацэньвацца з дапамогай кампутара, так што радок будзе друкавацца
на стандартны вывад, а тэрмін ўмова
ставіцца да таго, што знаходзіцца ўнутры дужкі, калі заяву.
Памятаеце, што ўсе аператары.
Памятаеце, што гэта && і | |, калі мы спрабуем аб'яднаць 2 або больш умоў,
Ня === праверыць 2 рэчы роўныя.
Памятаеце, што = для прызначэння ў той час як == гэта лагічны аператар.
≤, ≥, а затым канчатковы 2 гавораць самі за сябе.
Агульны агляд булевай логікі тут.
І лагічныя выразы таксама з'яўляюцца важнымі ў завесах,
якія мы разгледзім цяпер.
Мы даведаліся аб 3 выгляду завес да гэтага часу ў CS50, бо, у той час як, і зрабіць у той час.
І гэта важна ведаць, што ў той час як для большасці мэтаў
мы сапраўды можам выкарыстоўваць любы тып цыкла ў цэлым
Ёсць пэўныя тыпы мэтаў або агульных заканамернасцяў
у праграмаванні, што канкрэтны заклік да аднаго з гэтых завес
, Якія робяць яго найбольш эфектыўным і элегантным, каб закадаваць яго такім чынам.
Давайце паглядзім, што кожная з гэтых завес, як правіла, выкарыстоўваецца для найбольш часта.
>> У цыкл мы ў цэлым ужо ведаю, колькі разоў мы хочам перабраць.
Гэта тое, што мы ўкладваем у стане.
Бо, я = 0, <10, напрыклад.
Мы ўжо ведаем, што мы хочам зрабіць нешта ў 10 разоў.
Зараз, у той час як цыкл, як правіла, мы не абавязкова
ведаю, колькі разоў мы хочам, каб пятля для запуску.
Але мы ведаем, свайго роду ўмова, што мы хочам, каб
Заўсёды быць сапраўдным або ілжывых заўсёды.
Напрыклад, у той час ўстаноўлена.
Давайце казаць, што гэта лагічная зменная.
Хоць гэта праўда, мы хочам, каб код, каб ацаніць,
так што трохі больш пашыраецца, трохі больш агульнае, чым цыкл,
але любы цыкл можа быць пераўтворана ў той час як пятля.
І, нарэшце, рабіць, пакуль завесы, якая можа быць самая складаная зразумець адразу,
часта выкарыстоўваецца, калі мы хочам ацаніць Спачатку код
Перад Упершыню мы правяраем стан.
Агульны выпадак выкарыстання рабіць падчас цыклу
калі вы хочаце атрымаць карыстацкі ўвод, і вы ведаеце, вы хочаце спытаць карыстальніка
для ўводу крайняй меры адзін раз, але калі яны не даюць вам добрыя ўваходныя адразу
Вы хочаце працягваць прасіць іх, пакуль яны даюць вам добры ўваход.
Гэта самы распаўсюджаны спосаб выкарыстання гэтага час цыклу,
і давайце паглядзім на рэальную структуру гэтых завес.
Як правіла, яны заўсёды імкнуцца прытрымлівацца гэтым патэрны.
>> На цыкл ўнутры вас ёсць 3 кампанента:
ініцыялізацыі, як правіла, нешта накшталт Int я = 0, дзе я ёсць лічыльнік,
стан, у якім мы хочам сказаць, запусціць гэты цыкл, пакуль гэта ўмова застаецца ў сіле,
як я <10, і, нарэшце, абнаўленне, які з'яўляецца, як мы павялічваем
зменная лічыльніка ў кожнай кропцы цыклу.
Звычайная рэч, каб бачыць, што ёсць толькі я + +,
што азначае павялічваць я на 1 кожны раз.
Вы таксама можаце зрабіць нешта накшталт я + = 2,
што азначае, дадайце 2 да я кожны раз вы ідзяце праз пятлю.
І тады зрабіць гэта толькі ставіцца да любой код, які фактычна працуе як частка цыкла.
І на некаторы час цыклу, на гэты раз у нас сапраўды ёсць ініцыялізацыя па-за цыклу,
Так, напрыклад, выкажам здагадку, што мы спрабуем зрабіць тое ж самае тып цыкла, як я толькі што апісаў.
Мы хацелі б сказаць Int = 0 перад пачаткам цыклу.
Тады мы маглі б сказаць, калі я <10 гэтага
гэтак жа блок кода, як і раней,
і на гэты раз абнаўленне часткі кода, напрыклад, я + +,
на самай справе адбываецца ўнутры цыклу.
І, нарэшце, у той час як рабіць, гэта падобна на час цыклу,
але мы павінны памятаць, што код будзе ацэньваць разы
Перад ўмова правяраецца, таму ён робіць нашмат больш сэнсу
калі вы паглядзіце на яе ў парадку зверху ўніз.
У той час як цыкл зрабіць код ацэньвае перш, чым вы нават глядзець на гэты час умовы,
у той час як час цыклу, яна правярае ў першую чаргу.
Заявы і зменныя.
Калі мы хочам стварыць новую зменную, мы спачатку хочам ініцыялізаваць яго.
>> Напрыклад, унутр бар ініцыялізуе зменную бар,
але гэта не дае ёй значэнне, так што значэнне бары цяпер?
Мы не ведаем.
Гэта можа быць нейкая фігня значэнне, якое захоўваецца ў памяці там,
і мы не хочам выкарыстоўваць гэтую зменную
пакуль мы фактычна не даць яму значэння,
такім чынам, мы аб'явім яго тут.
Затым мы ініцыялізуем, што гэта будзе 42 ніжэй.
Цяпер, вядома, мы ведаем, што гэта можа быць зроблена на адной лініі, унутр бар = 42.
Але Проста каб быць ясна некалькіх крокаў, што адбываецца,
Дэкларацыя і ініцыялізацыя адбываецца паасобна.
Гэта адбываецца на адзін крок, і наступны, унутр Баз = бар + 1,
гэта зацвярджэнне ніжэй, якое павялічвае Баз, так што ў канцы гэтага блока кода
калі б мы былі на друк значэнне Баз было б 44
таму што мы аб'явіць і ініцыялізаваць, што гэта будзе 1> бара,
і тады мы павялічваем яго яшчэ раз з + +.
Мы пайшлі на гэта даволі коратка, але гэта добра, каб мець агульнае
разуменне таго, што тэмы і падзеі.
У асноўным мы зрабілі гэта ў Scratch,
так што вы можаце думаць аб тэмы, як некалькі паслядоўнасцяў кода
працуе ў той жа час.
На самай справе, гэта, верагодна, не працуе, у той жа час,
а як бы абстрактна мы можам думаць пра гэта такім чынам.
>> У Scratch, напрыклад, у нас было некалькі спрайт.
Гэта можа быць выкананне іншага кода, у той жа час.
Можна было хадзіць, а другі кажа нешта
У другой частцы экрана.
Падзеі яшчэ адзін спосаб вылучэння логікі
паміж рознымі элементамі кода,
і драпінам, мы змаглі змадэляваць падзеі з дапамогай трансляцыі,
і што на самой справе, калі я атрымліваю, а не калі я чую,
але па сутнасці гэта спосаб перадачы інфармацыі
ад аднаго спрайт на іншы.
Напрыклад, вы можаце перадаць гульню на сябе,
і калі іншы спрайт атрымлівае за гульню,
ён рэагуе пэўным чынам.
Гэта важная мадэль для разумення праграмавання.
Проста перайсці на асноўную тыдзень 0, то, што мы перайшлі да гэтага часу,
давайце паглядзім на гэты просты праграмы на Сі.
Тэкст можа быць трохі невялікім адсюль, але я пайду на гэта вельмі хутка.
Мы ў тым ліку 2 файлы загалоўкаў у верхняй частцы, cs50.h і stdio.h.
Мы тады вызначэнні пастаяннай завецца мяжой у 100.
Мы тады ажыццяўленні нашай галоўнай функцыі.
Так як мы не будзем выкарыстоўваць аргументы каманднага радка тут мы павінны паставіць несапраўднымі
у якасці аргументаў для асноўнага.
Мы бачым Int вышэй асноўнага. Гэта тып якое вяртаецца значэння, таму вяртаць 0 у ніжняй часткі.
І мы выкарыстоўваем CS50 функцыі бібліятэкі атрымліваюць Int
спытаць карыстальніка для ўваходу, і мы захоўваем яго ў гэтай зменнай х,
такім чынам, мы заяўляем х вышэй, і мы ініцыялізаваць яго з х = GetInt.
>> Затым мы правяраем, калі карыстальнік даў нам добры ўваход.
Калі гэта ≥ LIMIT мы хочам вярнуць код памылкі 1 і друкаваць паведамленне пра памылку.
І, нарэшце, калі карыстальнік даў нам добры ўваход
мы збіраемся ўзвесці ў квадрат ліку і раздрукаваць гэты вынік.
Проста каб пераканацца, што тыя ўсе хіт дадому
Вы можаце бачыць этыкеткі розных частак кода тут.
Я згадваў пастаянна, файлы загалоўкаў.
О, Int х. Пераканайцеся ў тым, памятаеце, што гэта лакальная зменная.
Гэта кантрастуе яго ад глабальных зменных, якія мы будзем казаць пра
Крыху пазней у аглядзе сесіі
і мы заклікаем бібліятэчныя функцыі Printf,
так што, калі б мы не ўключылі загалоўкавых файл stdio.h
мы не былі б у стане назваць Printf.
І я лічу, што стрэлка, якая атрымала адрэзаць тут паказвае на% D,
якая з'яўляецца фарматавання радкі ў Printf.
Ён кажа, раздрукуйце гэтую зменную як лік,% D.
І гэта ўсё за тыдзень 0.
Цяпер Лукас мае намер працягваць.
Гэй, хлопцы. Мяне клічуць Лукас.
Я на другім курсе ў лепшым доме на тэрыторыі кампуса, Mather,
і я хачу пагаварыць трохі аб тыдзень 1 і 2,1.
[Тыдзень 1 і 2,1!] [Лукас Фрейтас]
Як Lexi казаў, калі мы пачалі перакладаць код з нуля C
адна з рэчаў, якія мы заўважылі, што вы не можаце проста
напісаць свой код і запусціць яго з дапамогай зялёнага сцяга больш.
На самай справе, вы павінны выкарыстоўваць некаторыя крокі, каб зрабіць вашу праграму C
сталі выкананы файл.
У асноўным, што вы робіце, калі вы пішаце праграмы з'яўляецца тое, што
Вы перакладаеце вашыя ідэі на мову, кампілятар можа зразумець,
таму, калі вы пішаце праграму ў C
што вы робіце на самай справе нешта пісаў, што кампілятар будзе разумець,
, А затым кампілятар збіраецца перавесці гэты код
у тое, што ваш кампутар будзе разумець.
>> А справа ў тым, кампутар на самай справе вельмі па-дурному.
Ваш кампутар можа зразумець толькі 0 і 1,
так на самай справе ў першыя кампутары звычайна людзі запраграмаваныя
выкарыстанне 0 і 1, але не больш, дзякуй Богу.
Мы не трэба запамінаць паслядоўнасці 0 і 1
за цыкл або цыкл, пакуль і так далей.
Вось чаму ў нас ёсць кампілятар.
Які кампілятар робіць гэта ў асноўным перакладае код C,
У нашым выпадку, да мовы, што ваш кампутар будзе разумець,
якая з'яўляецца аб'ектны код, а кампілятар, які мы выкарыстоўваем
называецца звон, так што гэта на самай справе сімвал ляск.
Калі ў вас ёсць праграма, што вам трэба зрабіць 2 рэчы.
Па-першае, вы павінны кампіляваць вашу праграму, а затым вы збіраецеся запусціць праграму.
Для кампіляцыі праграмы ў вас ёсць шмат варыянтаў, каб зрабіць гэта.
Першы рабіць ляск program.c
У якой праграме гэта назва вашай праграмы.
У гэтым выпадку вы можаце бачыць, што яны проста кажуць: "Гэй, кампіляцыі маёй праграмы".
Вы не кажаце "я хачу гэта назва для маёй праграмы", ці нічога.
>> Другі варыянт дае назву вашай праграмы.
Можна сказаць, ляск-O, а затым імя, якое вы хочаце
выкананы файл будзе называцца, як і program.c.
І вы таксама можаце зрабіць зрабіць праграму, і паглядзець, як у першых 2-х выпадках
Я стаўлю. С, а ў трэцім ў мяне толькі праграмы?
Так, вы на самой справе не варта ставіць. З, калі вы выкарыстоўваеце зрабіць.
У адваротным выпадку кампілятар на самай справе адбываецца, каб крычаць на вас.
А таксама, я не ведаю, калі вы, хлопцы, памятаеце,
але шмат раз мы таксама выкарысталі lcs50-ці-лм.
Гэта называецца сувязяў.
Ён проста паведамляе кампілятару, што вы будзеце выкарыстоўваць гэтыя бібліятэкі тут жа,
так што калі вы хочаце выкарыстоўваць cs50.h вы на самой справе павінны ўвесці
ляск program.c-lcs50.
Калі вы не зробіце гэтага, кампілятар не будзе ведаць,
што вы выкарыстоўваеце гэтыя функцыі ў cs50.h.
І калі вы хочаце запусціць вашу праграму ў вас ёсць 2 варыянты.
Калі вы зрабілі ляск program.c Вы не даць назву вашай праграмы.
Вы павінны запусціць яго з дапамогай. / A.out.
A.out з'яўляецца стандартным імем, ляск дае вашай праграме, калі вы не даеце яму імя.
У адваротным выпадку вы збіраецеся рабіць. / Праграма, калі вы далі назву вашай праграмы,
а таксама, калі вы рабілі праграму імя, якое праграма будзе атрымаць
ўжо будзе запраграмаваны тым жа імем, што і файл з.
Тады мы гаварылі пра тыпы дадзеных і дадзеных.
>> Асноўным тыпаў дадзеных адны і тыя ж рэчы, як маленькія скрыначкі яны выкарыстоўваюць
для захоўвання значэнняў, так што тыпы дадзеных на самай справе так жа, як покемонов.
Яны бываюць розных памераў і тыпаў.
Я не ведаю, што аналогія мае сэнс.
Памер дадзеных на самай справе залежыць ад архітэктуры машыны.
Усе дадзеныя памераў, што я збіраюся паказаць тут
на самай справе для 32-бітных машын, якія ў выпадку нашага прыбора,
Але калі вы на самой справе кадавання вашага Mac або Windows, у таксама
верагодна, вы будзеце мець 64-разрадныя машыны,
так што не забудзьцеся, што дадзеныя памеры, якія я збіраюся паказаць тут
прызначаны для 32-разрадных машын.
Першае, што мы ўбачылі, было INT,
які з'яўляецца даволі простым.
Вы можаце выкарыстоўваць Int для захоўвання цэлага ліку.
Мы таксама бачылі сімвал, знак.
Калі вы жадаеце выкарыстоўваць літары або знака мала вы, верагодна, будзеце выкарыстоўваць знак.
Сімвал мае 1 байт, што азначае 8 біт, як сказала лексем.
У асноўным мы павінны ASCII табліцы, што мае 256
магчымыя камбінацыі 0 і 1,
, А затым, калі вы ўводзіце сімвал ён збіраецца перакладаць
сімвал, які вы уваходаў нумар, які вы маеце на ASCII табліцы, як лексем сказала.
У нас таксама ёсць паплавок, які мы выкарыстоўваем для захоўвання дзесятковых лікаў.
Калі вы жадаеце абраць 3.14, напрыклад, вы збіраецеся выкарыстоўваць паплавок
ці двайны, які мае больш дакладнасці.
Паплавок мае 4 байт.
Падвойнае мае 8 байт, таму розніца толькі ў тым дакладнасцю.
У нас таксама ёсць доўгі, які выкарыстоўваецца для цэлых лікаў,
і вы можаце бачыць на 32-бітнай машыне Int і доўгі маюць аднолькавы памер,
такім чынам, гэта сапраўды не мае сэнсу выкарыстоўваць доўгі ў 32-бітнай машыне.
>> Але калі вы выкарыстоўваеце Mac і 64-разрадных машын, на самай справе даўно мае памер 8,
так што гэта сапраўды залежыць ад архітэктуры.
Для 32-бітнай машыне ён не мае сэнсу выкарыстоўваць доўгі рэчаіснасці.
А потым доўга-доўга, з другога боку, мае 8 байт,
так што гэта вельмі добра, калі вы хочаце мець больш цэлага.
І, нарэшце, у нас ёсць радок, якая з'яўляецца на самай справе сімвал *,
, Які з'яўляецца паказальнікам на знак.
Гэта вельмі лёгка думаць, што памер радка будзе, як
Колькасць знакаў, якія ў вас там,
але на самой справе сімвал * сама
мае памер паказальніка на знак, які складае 4 байта.
Памер сімвал * 4 байта.
Гэта не мае значэння, калі ў вас ёсць невялікі словам ці лістом ці нічога.
Гэта будзе 4 байт.
Мы таксама даведаліся трохі аб ліцця,
так як вы можаце бачыць, калі ў вас, напрыклад, праграму, якая кажа
Int х = 3, а затым Е ("% D", х / 2)
вы, хлопцы, ведаеце, што ён збіраецца друкаваць на экране?
>> Хтосьці? >> [Студэнты] 2.
1. >> 1, так.
Калі вы робіце 3/2 ён збіраецца атрымаць 1,5,
але так як мы выкарыстоўваем цэлае яна збіраецца ігнараваць дробавай часткі,
і вы будзеце мець 1.
Калі вы не хочаце, каб гэта здарылася, што вы можаце зрабіць, напрыклад,
гэта аб'явіць паплавок у = х.
Тады х, што раней было 3, цяпер будзе 3,000 у год.
І тады вы можаце друкаваць у / 2.
На самай справе, я павінен мець 2. там.
Ён збіраецца зрабіць 3.00/2.00,
і вы будзеце атрымліваць 1,5.
А ў нас гэта 0,2 F проста пытацца 2 дзесятковых адзінак у дзесятковай часткі.
Калі ў вас ёсць 0,3 F, што гэта будзе мець на самай справе 1.500.
Калі гэта 2 гэта будзе 1,50.
У нас таксама ёсць гэта ў дадзеным выпадку.
Калі вы паплавок х = 3,14, і тады вы Printf х
Вы збіраецеся атрымаць 3,14.
І калі вы робіце х = Int х,
, Што азначае лячэнне х у выглядзе цэлага ліку і друку х зараз
Вы будзеце мець 3,00.
Ці мае гэта сэнс?
Таму што вы першы лячэнні х як цэлае, так што вы не звяртаючы ўвагі на дробавыя частка,
а затым вы друкуеце х.
І, нарэшце, вы таксама можаце зрабіць гэта,
Int х = 65, а затым аб'явіць сімвал з = х,
а затым, калі вы друкуеце з вы на самой справе збіраецеся атрымаць
, Таму ў асноўным тое, што вы тут робіце
перакладае цэлае лік у знак,
як ASCII табліцы робіць.
Мы таксама казалі пра матэматыцы аператараў.
Большасць з іх даволі простыя, таму +, -, *, /,
а таксама мы гаварылі пра моду, якая з'яўляецца рэшту ад дзялення 2-х нумароў.
Калі ў вас ёсць 10% 3, напрыклад,
гэта азначае, падзеліце 10 на 3, а што астатнія?
Гэта будзе 1, так што гэта на самай справе вельмі карысна для многіх праграм.
Для Виженера і Цэзара я ўпэўнены, што ўсе вы, хлопцы выкарыстоўвалі мод.
Аб матэматычныя аператары, будзьце вельмі асцярожныя пры камбінаванні * і /.
>> Напрыклад, калі вы робіце (3/2) * 2, што вы збіраецеся атрымаць?
[Студэнты] 2.
Так, 2, так як 3/2 будзе 1,5,
але так як вы робіце аперацыі паміж 2 цэлых лікаў
на самай справе вы толькі збіраецеся лічыць 1,
і 1 * 2 будзе 2, так што будзьце вельмі, вельмі асцярожныя
калі рабіць арыфметычныя дзеянні з цэлымі лікамі, таму што
Вы маглі б атрымаць, што 2 = 3, у гэтым выпадку.
А таксама быць вельмі асцярожным прыярытэт.
Вы павінны звычайна выкарыстоўваць дужкі, каб быць упэўненым, што вы ведаеце, што вы робіце.
Некаторыя карысныя цэтлікі, вядома, адзін я + + ці я + = 1
або з дапамогай + =.
Гэта тое ж самае, што рабіў I = I + 1.
Вы таксама можаце зрабіць я - ці я - = 1,
што тое ж самае, што і I = -1,
нешта вы, хлопцы выкарыстоўваюць шмат у цыклы, па меншай меры.
Акрамя таго, для *, калі вы выкарыстоўваеце * = і, калі вы, напрыклад,
я * = 2, тое ж самае, кажучы, што я = I * 2,
і тое ж самае для дзялення.
Калі ў вас у / = 2 гэта тое ж самае, што я = я / 2.
>> Зараз аб функцыях.
Вы, хлопцы даведаліся, што функцыі з'яўляюцца вельмі добрай стратэгіяй для захавання кода
у той час як вы программируете, таму, калі вы хочаце выканаць тую ж задачу
у код зноў і зноў, верагодна, вы хочаце выкарыстоўваць функцыю
проста так вам не прыйдзецца скапіяваць і ўставіць код зноў і зноў.
На самай справе, асноўная функцыя, і калі я пакажу вам фармат функцыі
Вы ўбачыце, што гэта даволі відавочна.
Мы таксама выкарыстоўваем некаторыя функцыі з бібліятэкі,
Напрыклад, Printf, Getin, што з бібліятэкі CS50,
і іншыя функцыі, такія як ToUpper.
Усе гэтыя функцыі рэалізуюцца на практыцы ў іншых бібліятэках,
і калі вы змясціць гэтыя файлы троса ў пачатку вашай праграмы
Вы кажаце, не маглі б вы даць мне код для гэтых функцый
так што я не павінна рэалізоўваць іх самастойна?
Таксама вы можаце напісаць свае ўласныя функцыі, таму, калі вы пачынаеце праграмаванне
Вы разумееце, што бібліятэкі ня маюць усе функцыі, якія вам трэба.
За апошнія PSET, напрыклад, мы пісалі маляваць, барацьба і пошук,
, І гэта вельмі, вельмі важна, каб мець магчымасць пісаць функцыі
таму што яны карысныя, і мы выкарыстоўваем іх увесь час у праграмаванні,
і гэта эканоміць шмат кода.
Фармат функцыі гэтага.
У нас ёсць вяртаецца тыпу ў самым пачатку. Які тып якое вяртаецца значэння?
Гэта проста, калі ваша функцыя будзе вяртаць.
Калі ў вас ёсць функцыя, напрыклад, фактарнага,
, Якая будзе вылічаць факториал цэлага ліку,
верагодна, ён збіраецца вяртаць цэлы лік, таксама.
Тады вяртаецца тыпу будзе Int.
Printf на самай справе мае пустэчу вяртаецца тыпу
таму што вы не вяртаецца нічога.
Ты проста друкаваць рэчы на ​​экране
і выхад з функцыі пасля гэтага.
Тады ў вас ёсць імя функцыі, якія вы можаце абраць.
Вы павінны быць трохі разумныя, як не выбіраюць імя, як XYZ
або як х2.
Паспрабуйце зрабіць сабе імя, якое мае сэнс.
>> Напрыклад, калі гэта факториал, скажам факториал.
Калі гэта функцыя, якая будзе маляваць нешта, назавіце яго маляваць.
І тады ў нас ёсць параметры, якія таксама называюцца аргументамі,
, Якія, як рэсурсы, што ваша функцыя павінна
з вашага кода для выканання сваіх задач.
Калі вы хочаце, каб вылічыць факториал ліку
верагодна, у Вас павінен быць побач, каб вылічыць факториал.
Адзін з аргументаў, якія вы збіраецеся ёсць, сам нумар.
І тады гэта будзе нешта рабіць, і вяртаць значэнне ў канцы
калі гэта не пустэча функцыі.
Давайце паглядзім на прыкладзе.
Калі я хачу напісаць функцыю, якая сумуе ўсе лікі ў масіў цэлых лікаў,
Перш за ўсё, вяртаецца тыпу будзе Int
таму што ў мяне ёсць масіў цэлых лікаў.
І тады я буду мець імя функцыі, як sumArray,
а затым ён збіраецца ўзяць сам масіў, у цэлае НУМС,
, А затым даўжыню масіва, таму я ведаю, як шмат лікаў, у мяне падвесці.
Тады ў мяне ёсць для ініцыялізацыі зменнай называюць суму, напрыклад, 0,
і кожны раз, калі я бачу элемент у масіве я павінен дадаць яго ў суму, таму я зрабіў цыкл.
Гэтак жа, як лексем сказала, вы робіце Int я = 0, <даўжыня і я + +.
І для кожнага элемента ў масіве я зрабіў суму + = НУМС [я],
а потым я вярнуўся суму, так што гэта вельмі проста, і гэта эканоміць шмат кода
калі вы выкарыстоўваеце гэтую функцыю шмат разоў.
Затым мы разгледзелі ўмовы.
У нас, калі, яшчэ, і яшчэ, калі.
Давайце паглядзім, у чым розніца паміж тымі, хто.
Зірніце на гэтыя 2 коды. У чым розніца паміж імі?
Першая была ў асноўным-коды хачу, каб ты
калі лік +, - або 0.
Першы кажа, што калі ён> 0, то гэта станоўча.
Калі гэта = 0, то гэта 0, а калі <0, то гэта адмоўна.
>> А іншы робіць, калі, інакш, калі іншае.
Розніца паміж імі складаецца ў тым, што гэты чалавек на самай справе збіраецца
праверыць, калі> 0, <0 = 0 або тры разы,
так што калі ў вас ёсць нумар 2, напрыклад, ён збіраецца прыехаць сюды і сказаць:
Калі (X> 0), і ён скажа так, так я друкаваць станоўчыя.
Але, хоць я ведаю, што гэта> 0, і ён не збіраецца быць 0 або <0
Я ўсё яшчэ збіраюся рабіць гэта 0, то <0,
так што я на самой справе адбываецца ўнутры IFS, што я не павінна
таму што я ўжо ведаю, што ён не збіраецца, каб задаволіць любое з гэтых умоў.
Я магу выкарыстоўваць, калі, інакш, калі іншае заяву.
Гэта ў асноўным кажа, што калі х = 0 надрукаваць станоўчыя.
Калі гэта не так, я буду таксама праверыць гэта.
Калі гэта 2 не я збіраюся гэта зрабіць.
У прынцыпе, калі ў мяне было х = 2 вы маглі б сказаць
Калі (X> 0), так, так друкаваць.
Цяпер, калі я ведаю, што гэта> 0 і што ён задаволены першым, калі
Я нават не збіраюся запусціць гэты код.
Код працуе хутчэй, на самай справе, у 3 разы хутчэй, калі вы выкарыстоўваеце гэта.
Мы таксама даведаліся пра і і або.
Я не збіраюся прайсці праз гэта, таму што лексем ўжо казалі пра іх.
Гэта проста && і | | аператара.
>> Адзінае, што я скажу, будзьце асцярожныя, калі ў вас ёсць 3 ўмовы.
Выкарыстоўвайце дужкі, таму што гэта вельмі заблытаным, калі ў Вас ёсць умова
і яшчэ адно ці іншае.
Выкарыстоўвайце дужкі проста каб быць упэўненым, што вашы ўмовы сэнсу
таму што ў гэтым выпадку, напрыклад, вы можаце сабе ўявіць, што
гэта можа быць першым умовай і адным ці іншым
або 2 ўмовы аб'яднаных ў і
або трэцяе, так што будзьце асцярожныя.
І, нарэшце, мы гаварылі пра камутатарах.
Выключальнік вельмі карысна, калі ў вас ёсць пераменная.
Давайце выкажам здагадку, што ў вас ёсць зменная, як п
што можа быць 0, 1 або 2, і для кожнага з гэтых выпадкаў
Вы збіраецеся выканаць задачу.
Вы можаце сказаць пераключэння зменнай, а гэта азначае, што
значэнне тое, як value1 я збіраюся зрабіць гэта,
а потым ламаецца, які азначае, што я не буду глядзець на любую з іншых выпадках
таму што мы ўжо задаволены тым, што справа
, А затым value2 і гэтак далей, і я таксама можа мець значэнне па змаўчанні пераключальніка.
Гэта азначае, што, калі ён не задавальняе ні аднаму з спраў, якія ў мяне былі
што я збіраюся зрабіць нешта яшчэ, але гэта неабавязкова.
Гэта ўсё для мяне. Зараз давайце Томі.
Усё правільна, гэта будзе тыдзень 3-иш.
Вось некаторыя з тэм, якія мы будзем пакрыццё, крыпта, сферы ўжывання, масівы, і гэтак далей.
Проста слоў пра крыптаграфіі. Мы не збіраемся забіваць гэтым домам.
>> Мы зрабілі гэта ў PSET 2, але для тэст пераканайцеся, што вы ведаеце розніцу
паміж шыфр Цэзара і шыфр Виженера,
як абедзве гэтыя работы шыфраў і што гэта такое для шыфравання
і расшыфраваць тэкст, выкарыстоўваючы гэтыя 2 шыфры.
Памятаеце, што шыфр Цэзара проста паварочвае кожны знак на тую ж суму,
пераканаўшыся, што вы мода на колькасць літар у алфавіце.
І шыфра Виженера, з другога боку, круціцца кожны знак
па іншую суму, так што замест таго, каб гаварыць
кожны персанаж павернуты на 3 Виженера будзе круціць кожны знак
на розны колькасць у залежнасці ад некаторых ключавых слоў
дзе кожная літара ў ключавое слова ўяўляе сабой некаторую іншую суму
каб павярнуць адкрытым тэкстам па.
Давайце спачатку пагаворым пра зменнай вобласці.
Ёсць 2 розных тыпаў зменных.
У нас ёсць лакальныя зменныя, і гэтыя будуць вызначаны
за межамі асноўнага або па-за якой-небудзь функцыі або блока,
і яны будуць даступныя ў любым месцы праграмы.
Калі ў вас ёсць функцыя, і ў гэтай функцыі з'яўляецца час цыклу
вялікія глабальныя зменныя даступныя ўсюды.
Лакальная зменная, з другога боку, з'яўляецца вобласцю да месца, дзе яна вызначана.
>> Калі ў вас ёсць функцыя Вось, напрыклад, у нас ёсць гэтая функцыя г,
і ўнутры G ёсць пераменная тут называецца у,
і гэта азначае, што гэта лакальная зменная.
Нават калі гэтая пераменная называецца ў
і гэтая пераменная называецца у гэтых 2 функцый
не ведаю, што адзін аднаго лакальных зменных.
З іншага боку, тут мы гаворым Int х = 5,
і гэта выходзіць за рамкі любой функцыі.
Гэта выходзіць за рамкі асноўнага, так гэта глабальная зменная.
Гэта азначае, што ўнутры гэтых 2 функцый, калі я кажу х - ці х + +
Я доступ да той жа х прычым гэта ў і ў гэтага з'яўляюцца рознымі зменнымі.
Вось у чым розніца паміж глабальных зменных і лакальных зменных.
Што тычыцца дызайну, то, часам гэта добрай ідэяй
захаваць лакальныя зменныя, калі вы, магчыма, можа
так як з кучай глабальных зменных можна атрымаць вельмі заблытанай.
Калі ў вас ёсць куча функцый ўсе змены адно і тое ж
Вы можаце забыць, што, калі гэтая функцыя выпадковага змяняе гэты глабальны,
і гэтая іншая функцыя не ведае пра гэта,
і гэта сапраўды становіцца даволі заблытаным, як вы атрымаеце больш кода.
Захаванне лакальных зменных, калі вы, магчыма, можа
проста добры дызайн.
Масівы, памятаеце, што гэта проста спісы з элементаў таго ж тыпу.
Усярэдзіне CI не можа мець спіс, як 1, 2,0, добры дзень.
Мы проста не можам гэтага зрабіць.
>> Калі мы аб'яўляем масіў у C ўсе элементы павінны быць таго ж тыпу.
Тут у мяне ёсць масіў з 3 цэлых лікаў.
Вось у мяне ёсць даўжыня масіва, але калі я проста аб'явіць яго ў гэты сінтаксіс
дзе я паказваю, што ўсе элементы я тэхнічна не патрэбна гэтая 3.
Кампілятар досыць разумны, каб зразумець, наколькі вялікі масіў павінен быць.
Цяпер, калі я хачу, каб атрымаць ці ўсталяваць значэнне масіва
гэта сінтаксіс, каб зрабіць гэта.
Гэта на самай справе змяніць Другі элемент масіва, таму што, памятаеце,
Нумарацыя пачынаецца з 0, а не з 1.
Калі я хачу прачытаць, што значэнне я магу сказаць нешта накшталт Int х = масіў [1].
Ці, калі я хачу ўсталяваць гэта значэнне, як я тут раблю,
Я магу сказаць, масіў [1] = 4.
У гэты час доступ да элементаў па індэксу
або іх становішча ці дзе яны знаходзяцца ў масіве,
і што ў каталогу пачынаецца з 0.
Мы можам таксама ёсць масівы масіваў,
і гэта завецца шматмерным масівам.
Калі ў нас ёсць мнагамерны масіў
гэта азначае, што мы можам мець нешта накшталт радкоў і слупкоў,
і гэта толькі адзін з спосабаў візуалізацыі гэтага ці думаць пра гэта.
Калі ў мяне ёсць мнагамерны масіў, які азначае, што я збіраюся пачаць маюць патрэбу
больш чым на 1 індэкс, таму што калі ў мяне ёсць сетка
проста кажу, што радок вы знаходзіцеся ў не дае нам нумар.
Гэта сапраўды проста хачу, каб даць нам спіс нумароў.
Скажам, у мяне ёсць гэты масіў тут.
У мяне ёсць масіў завецца сетка, і я кажу, што гэта 2 радкі і 3 слупка,
і такім чынам, гэта з'яўляецца адным з спосабаў візуалізацыі яго.
Калі я кажу, я хачу, каб элемент [1] [2]
гэта азначае, што, паколькі гэтыя радкі, а затым слупкі
Я збіраюся перайсці на радок 1, таму што я сказаў 1.
>> Тады я збіраюся прыехаць сюды ў калонцы 2, і я збіраюся атрымаць значэнне 6.
Сэнс?
Шматмерныя масівы, памятаеце, што тэхнічна проста масіў масіваў.
Мы можам мець масівы масіваў масіваў.
Мы можам працягваць, але сапраўды адзін спосаб думаць аб
як гэта ў цяперашні час закладзены, і тое, што адбываецца, каб візуалізаваць
у сетцы, як гэта.
Калі мы перадаем масіваў у функцыі, яны будуць паводзіць сябе
крыху па-іншаму, чым калі мы пераходзім рэгулярных зменных функцыі
як перадача Int або з якая плавае кропкай.
Калі мы перадаем у Int або знак ці любы з гэтых іншых тыпаў дадзеных
мы толькі што разгледзелі, калі функцыя змяняе
значэнне гэтай зменнай, што змены не збіраюся распаўсюджвацца ўверх
у выклікае функцыю.
З масівам, з другога боку, што будзе адбывацца.
Калі б я перадаць масіў да некаторай функцыі і функцыя змяняе некаторыя элементы,
калі я вярнуся да функцыі, якія назвалі яго
мой масіў цяпер будзе па-іншаму, і слоўнік для гэтага
гэта масівы перадаюцца па спасылцы, як мы ўбачым пазней.
Гэта звязана як паказальнікі працы, дзе гэтыя асноўныя тыпы дадзеных,
З іншага боку, перадаюцца па значэнні.
>> Мы можам думаць аб тым, як зрабіць копію некаторыя зменныя і пераходзячы затым у копіі.
Не мае значэння, што мы робім з гэтай зменнай.
Выклікае функцыя не будзе ведаць, што ён змяніўся.
Масівы з'яўляюцца толькі трохі адрозніваецца ў гэтым стаўленні.
Напрыклад, як мы толькі што бачылі, асноўным з'яўляецца проста функцыяй
што можна ўзяць у 2 аргументаў.
Першы аргумент асноўнай функцыяй з'яўляецца агдс, або колькасць аргументаў,
а другі аргумент называецца ARGV,
і тыя фактычныя значэння гэтых аргументаў.
Скажам, у мяне ёсць праграма пад назвай this.c,
і я кажу гэта зрабіць, і я збіраюся запусціць у камандным радку.
Зараз, каб прайсці ў некаторыя аргументы, каб мая праграма называецца гэта,
Я мог бы сказаць нешта падобнае. / Гэта CS 50.
Гэта тое, што мы сабе ўяўляем, Дэвід рабіць кожны дзень на тэрмінале.
Але цяпер асноўная функцыя ўнутры гэтай праграмы
мае наступныя значэнні, так агдс роўная 4.
Гэта можа быць трохі заблытаным, таму што на самой справе мы толькі якія праходзяць у гэта CS 50.
Вось толькі 3.
Але памятайце, што першы элемент ARGV або першы аргумент
гэтае імя самой функцыі.
Такім чынам, гэта азначае, што ў нас ёсць 4 рэчы тут,
і першы элемент будзе. / гэта.
І гэта будзе прадстаўлена ў выглядзе радка.
Тады астатнія элементы таго, што мы набралі пасля назвы праграмы.
Гэтак жа, як у баку, так як мы, напэўна, бачылі ў PSET 2,
памятаеце, што радок 50, ≠ цэлых 50.
Таму мы не можам сказаць нешта накшталт: "INT X = ARGV 3".
>> Вось толькі не збіраецца сэнсу, таму што гэта радок, і гэта лік.
Так што, калі вы хочаце канвертаваць паміж 2, памятаеце, што мы збіраемся
ёсць гэтая чароўная функцыя называецца atoi.
, Якая прымае радок і вяртае цэлы лік прадстаўлена ў гэтым радку.
Так што гэта лёгка зрабіць памылку ў віктарыне,
проста думаў, што гэта будзе аўтаматычна правільны тып.
Але дакладна ведаю, што гэта заўсёды будзе радкоў
нават калі радок утрымлівае толькі цэлы лік або знак ці з якая плавае кропкай.
Такім чынам, цяпер давайце пагаворым пра час працы.
Калі ў нас ёсць усе гэтыя алгарытмы, якія робяць усё гэтыя вар'яцкія рэчы,
гэта становіцца сапраўды карысна задацца пытаннем: «Як доўга яны прымаюць?"
Мы ўяўляем, што нешта, званае асімптатычнай абазначэнне.
Такім чынам, гэта азначае, што - ну, скажам, мы даем нашым алгарытмам
некаторыя вельмі, вельмі, вельмі вялікі ўклад.
Мы хочам задаць пытанне: "Як доўга гэта зойме?
Колькі крокаў зойме наш алгарытм для запуску
у залежнасці ад памеру ўваходных дадзеных? "
Такім чынам, першы спосаб, якім мы можам апісаць час выканання з вялікай О.
І гэта наш найгоршы ход часу.
Таму калі мы хочам, каб адсартаваць масіў, і мы даем нашым алгарытмам масіва
гэта ў парадку змяншэння, калі яно павінна быць у парадку ўзрастання,
што будзе ў горшым выпадку.
Гэта наша верхняя грань у максімальны час наш алгарытм будзе.
З іншага боку, гэтая Ω будзе апісваць лепшым выпадку час працы.
Так што, калі мы дамо ўжо адсартаваны масіў у алгарытм сартавання,
Як доўга гэта зойме, каб улагодзіць яго?
І гэта, то, апісвае ніжнюю мяжу на час працы.
Такім чынам, вось толькі некаторыя словы, якія апісваюць некаторыя агульныя працуе разы.
Гэта ў парадку ўзрастання.
Самы хуткі бег часу ў нас называецца сталым.
>> Гэта азначае, што незалежна ад таго, колькі элементаў мы даем нашым алгарытмам,
незалежна ад таго, наколькі вялікая наша масіў, сартаванне
ці рабіць тое, што мы робім у масіў заўсёды будзе такое ж колькасць часу.
Такім чынам, мы можам ўявіць, што толькі з 1, які з'яўляецца сталым.
Мы таксама паглядзелі на лагарыфмічнай час перспектыве.
Так нешта накшталт двайковага пошуку з'яўляецца лагарыфмічнай,
дзе мы скарацілі праблема ў два разы кожны раз, калі
а потым усё проста атрымаць вышэйшую адтуль.
І калі вы калі-небудзь пісьмова аб любых факториал алгарытм,
Вы, верагодна, не варта разглядаць гэта як сваю працу дня.
Калі мы параўноўваем часу працы вельмі важна мець на ўвазе гэтыя рэчы.
Так што, калі ў мяне ёсць алгарытм, які O (N), а нехта іншы
была алгарытму O (2n), гэта на самай справе асімптатычна эквівалентныя.
Такім чынам, калі ўявіць сабе, п быць вялікая колькасць, як eleventy млрд:
таму, калі мы параўноўваем eleventy млрд. нешта накшталт eleventy млрд. + 3,
3 раптам, што на самой справе не робяць вялікай розніцы больш.
Вось чаму мы збіраемся пачаць разглядаць гэтыя рэчы, каб быць эквівалентнымі.
Так што такія рэчы, як гэтыя канстанты тут, ёсць 2 х гэта, або даданне 3,
гэта проста канстанты, і яны збіраюцца кінуць ўверх.
Дык вось чаму ўсё гэтыя 3 разы перспектыве такія ж, як кажуць яны O (N).
Аналагічна, калі ў нас ёсць 2 іншыя часы перспектыве, скажам, O (N ³ + 2n ²), мы можам дадаць
+ П, + 7, а затым у нас ёсць яшчэ час выканання, што проста O (N ³).
зноў жа, гэта адно і тое ж, таму што гэта - гэта не тое ж самае.
Гэта тыя ж самыя рэчы, прабачце. Такім чынам, гэта тыя ж самыя, таму што
гэтая ³ п будзе дамінаваць у гэтым 2n ².
>> Што не адно і тое ж, калі мы ўжо запусцілі час, як O (N ³) і O (N ²)
таму што гэтая ³ п значна больш, чым гэта ² н.
Так што, калі ў нас ёсць паказчыкі, раптам гэта пачынае значэння,
Але калі мы проста справа з фактарамі, як мы тут,
то ён не збіраецца значэння, таму што яны толькі збіраюцца кідаць.
Давайце зірнем на некаторыя алгарытмы, якія мы бачылі да гэтага часу
і казаць пра іх выканання.
Першы погляд на нумар у спісе, які мы бачылі, быў лінейны пошук.
І рэалізацыя лінейнага пошуку супер проста.
Мы проста ёсць спіс, і мы будзем глядзець на кожны асобны элемент у спісе
пакуль мы не знойдзем лік, якое мы шукаем.
Такім чынам, гэта азначае, што ў горшым выпадку, гэта O (N).
А ў горшым выпадку тут магло б быць, калі элемент
Апошні элемент, то з дапамогай лінейнага пошуку, мы павінны глядзець на кожны асобны элемент
пакуль мы не атрымаем да апошняга, каб ведаць, што гэта было на самай справе ў спісе.
Мы не можам проста кінуць на паўдарогі і сказаць: "Гэта, напэўна, няма».
З лінейны пошук, мы павінны глядзець на ўсё гэта.
Лепшым выпадку час працы, з іншага боку, пастаянна
таму што ў лепшым выпадку элемент мы шукаем гэта толькі першы ў спісе.
Такім чынам, ён збіраецца ўзяць нас роўна на 1 крок, незалежна ад таго, наколькі вялікі спіс
калі мы шукаем першы элемент кожны раз.
>> Таму, калі вы будзеце шукаць, памятаеце, гэта не патрабуе, каб наш спіс будзе адсартаваны.
Таму што мы проста будзем глядзець на кожны асобны элемент, і гэта сапраўды не мае значэння
у якім парадку гэтыя элементы цалі
Больш за інтэлектуальны алгарытм пошуку нешта накшталт бінарнага пошуку.
Памятаеце, што рэалізацыя бінарнага пошуку, калі вы збіраецеся
працягвайце глядзець у сярэдзіну спісу.
І таму, што мы глядзім на сярэдзіне, мы патрабуем, каб спіс сартуецца
інакш мы не ведаем, дзе сярэдзіна, і мы павінны глядзець на
ўвесь спіс, каб знайсці яго, а затым на той момант мы проста губляем час.
Так што, калі ў нас ёсць адсартаваны спіс, і мы знаходзім сярэдзіну, мы збіраемся параўнаць сярэднія
да элемента мы шукаем.
Калі яна занадта высокая, то мы можам забыць правай паловы
таму што мы ведаем, што калі наш элемент ўжо занадта высокія
і ўсё, што правей гэтага элемента яшчэ вышэй,
то мы не павінны глядзець там больш.
Калі, з другога боку, калі наш элемент з'яўляецца занадта нізкай,
Мы ведаем усё, каб злева ад гэтага элемента таксама з'яўляецца занадта нізкай,
такім чынам, гэта сапраўды не мае сэнсу шукаць там, таксама.
Такім чынам, з кожным крокам, і кожны раз, калі мы глядзім на сярэдзіну спісу,
Мы збіраемся скараціць нашы праблемы ў палову, таму што раптам мы ведаем,
цэлую кучу лічбаў, што не можа быць той, які мы шукаем.
>> У псевдокоде гэта будзе выглядаць прыкладна так,
і таму, што мы рэзкі спісу ў два разы кожны раз,
нашы найгоршыя час выканання скачкоў з лінейнай да лагарыфмічнай.
Так нечакана мы маем ўваход у сістэму крокі для таго, каб знайсці элемент у спісе.
Лепшым выпадку ход часу, хоць, па-ранейшаму пастаяннай
таму што цяпер, давайце проста скажам, што элемент мы шукаем з'яўляецца
Заўсёды сапраўды пасярэдзіне першапачатковага спісу.
Так што мы можам развіваць наш спіс як вялікі, як мы хочам, але калі элемент мы шукаем знаходзіцца на сярэдзіне,
Затым яна толькі збіраецца ўзяць нас на 1 крок.
Дык вось чаму мы O (часопіс N) і Ω (1) ці сталымі.
Давайце рэальна працаваць бінарны пошук у гэтым спісе.
Так што давайце казаць, што мы шукаем элемент 164.
Першае, што мы збіраемся зрабіць, гэта знайсці сярэдзіну гэтага спісу.
Проста так атрымалася, што сярэдзіна будзе падаць паміж гэтымі 2 нумары,
так што давайце проста калі заўгодна казаць, кожны раз сярэдзіна знаходзіцца паміж 2 нумары,
Давайце проста акругліць.
Нам проста трэба пераканацца, што мы робім гэта кожны крок шляху.
Так што мы збіраемся зганяць, і мы збіраемся сказаць, што 161 з'яўляецца сярэднім з нашага спісу.
Так што 161 <164, і кожны элемент у левым з 161
Таксама <164, так што мы ведаем, што гэта не дапаможа нам на ўсіх
, Каб пачаць шукаць тут, таму што элемент мы шукаем не можа быць там.
Такім чынам, што мы можам зрабіць, мы можам проста забыць аб тым, што ўся левая палова спісу,
а цяпер разглядаць толькі з правага з 161 і далей.
>> Такім чынам, яшчэ раз, гэта сярэдзіна, давайце проста акругліць.
Цяпер 175 з'яўляецца занадта вялікі.
Такім чынам, мы ведаем, што гэта не дапаможа нам шукаць тут або тут,
таму мы можам проста кінуць, што далёка, і ў выніку мы трапілі ў 164.
Любыя пытанні па двайковага пошуку?
Давайце пяройдзем ад пошуку ва ўжо адсартаваны спіс
на самай справе прымае спіс лікаў у любым парадку
і зрабіць гэты спіс у парадку ўзрастання.
Першы алгарытм мы глядзелі на называлася пузырьковый сартавання.
І гэта будзе значна прасцей алгарытмаў, якія мы бачылі.
Bubble роду кажа, што калі любыя 2 элемента ўнутры спісу не на месцы,
гэта значыць ёсць большая колькасць злева ад меншага ліку,
Затым мы збіраемся памяняць іх месцамі, таму што гэта азначае, што спіс будзе
"Больш за спарадкаваныя", чым гэта было раней.
І мы проста будзем працягваць гэты працэс зноў і зноў, і зноў
пакуль у рэшце рэшт элементаў выгляду бурбалка на іх правільнае размяшчэнне і ў нас ёсць адсартаваны спіс.
>> Час выканання гэтага будзе O (N ²). Чаму?
Ну, таму што ў горшым выпадку, мы збіраемся ўзяць кожны элемент, і
мы збіраемся ў канчатковым выніку, параўноўваючы яе з любой іншай элемент у спісе.
Але ў лепшым выпадку, у нас ёсць ужо адсартаваны спіс, пузырьковый сартавання ў
толькі збіраецца прайсці адзін раз, сказаць: "Не. Я не рабіў ніякіх свопов, так што я зрабіў".
Такім чынам, мы маем лепшым выпадку час працы Ω (N).
Давайце запусцім пузырьковый сартавання ў спісе.
Ці спачатку, давайце проста паглядзім на некаторыя псевдокод вельмі хутка.
Мы хочам сказаць, што мы хочам адсочваць, у кожнай ітэрацыі цыклу,
адсочваць ці мы змянілі якія-небудзь элементы.
Такім чынам, прычына гэтага ў тым, што мы збіраемся спыніцца, калі мы не памяняліся месцамі любыя элементы.
Такім чынам, у пачатку нашага цыклу мы не памяняліся месцамі нічога, таму мы будзем казаць, што гэта хлусня.
Зараз, мы збіраемся прайсціся па спісе і параўнаць элемента да элемента я я + 1
і калі гэта так, што ёсць большая колькасць злева ад меншага ліку,
Затым мы толькі збіраемся, каб памяняць іх месцамі.
>> І тады мы будзем памятаць, што мы памяняліся месцамі элемент.
Гэта азначае, што мы павінны ісці па спісе, па меншай меры, яшчэ 1 раз
таму што стан, у якім мы спыніліся, калі ўвесь спіс ужо адсартаваны,
азначае, што мы не зрабілі ніякіх свопов.
Дык вось чаму нашы ўмовы тут з'яўляецца «у той час як некаторыя элементы былі замененыя.
Такім чынам, цяпер давайце паглядзім на гэта працуе на спіс.
У мяне ёсць спіс 5,0,1,6,4.
Bubble роду збіраецца пачаць ўвесь шлях злева, і гэта будзе для параўнання
я элементаў, так ад 0 да + 1, якое з'яўляецца элементам 1.
Ён скажа, ну 5> 0, але прама зараз 5 знаходзіцца злева,
так што мне трэба памяняць месцамі 5 і 0.
Калі я памяняць іх месцамі, раптам я атрымліваю гэта іншае спіс.
Зараз 5> 1, так што мы збіраемся памяняць іх месцамі.
5 не> 6, таму мы не павінны нічога рабіць тут.
Але 6> 4, так што мы павінны памяняць.
Зноў жа, нам трэба запусціць ўвесь спіс, каб у рэшце рэшт выявіць
што гэтыя выйшлі з ладу, мы памяняць іх месцамі,
і ў гэты момант нам трэба запусціць праз спіс яшчэ 1 раз
каб пераканацца, што ўсё ў яго распараджэнні, і ў гэты момант пузырьковый сартавання скончаны.
Розных алгарытмаў для прыняцця некаторых элементаў і сартаванне іх з'яўляецца выбар роду.
Ідэя выбару роду з'яўляецца тое, што мы збіраемся пабудаваць адсартаваны частку спісу
1 элемент адначасова.
>> І тое, як мы збіраемся зрабіць гэта шляхам стварэння левай частцы спісу.
А ў прынцыпе, кожны - на кожным кроку, мы збіраемся ўзяць найменшы элемент мы пакінулі
, Якія не былі адсартаваныя яшчэ, і мы збіраемся, каб перамясціць яго ў гэты адсартаваны сегменце.
Гэта азначае, што мы павінны пастаянна знаходзіць мінімальны элемент несортированные
, А затым прыняць, што мінімальны элемент і памяняць яго з тым, што
левы элемент, які не сартуецца.
Час выканання гэтага будзе O (N ²), таму што ў горшым выпадку
мы павінны параўнаць кожны элемент любой іншай элемент.
Таму што мы кажам, што калі мы пачнем ў левай палове спісу, мы павінны
прайсці праз увесь правы сегмент, каб знайсці найменшы элемент.
А потым, зноў жа, мы павінны ісці на працягу ўсяго правага сегмента і
працягваць над гэтым зноў і зноў, і зноў.
Гэта будзе п ². Мы збіраемся трэба цыкл ўнутры іншага цыклу
што сведчыць аб п ².
У лепшым выпадку думка, скажам, мы даем яму ўжо адсартаваны спіс;
мы на самай справе не робяць лепш, чым ² н.
Таму што выбар роду не мае магчымасці даведацца, што
мінімальны элемент толькі адзін я, здараецца, глядзіць.
Ён па-ранейшаму павінен пераканацца, што гэта сапраўды мінімум.
>> І адзіны спосаб, каб пераканацца, што гэта мінімум, з дапамогай гэтага алгарытму,
, Каб глядзець на кожны асобны элемент зноў.
Так на самай справе, калі вы даеце яму - калі вы дасце выбар кшталту ўжо адсартаваны спіс,
ён не збіраецца рабіць лепш, чым даць яму сьпіс, што не адсартаваны яшчэ няма.
Дарэчы, калі яно адбудзецца, будзе выпадак, што нешта O (нешта)
і амега-то, мы можам толькі сказаць, больш коратка, што гэта θ чагосьці.
Так што калі вы бачыце, што прыдумаць у любым месцы, гэта тое, што гэта проста азначае.
>> Калі нешта тэта-н ², гэта і вялікая O (N ²) і Ω (N ²).
Так лепшым выпадку, а горшым выпадку, гэта не робіць розніцы,
Алгарытм збіраецца зрабіць тое ж самае кожны раз.
Так гэта тое, што псевдокод для выбару роду магла б выглядаць.
Мы ў асноўным будзем казаць, што я хачу прайсці па спісе
злева направа, і на кожнай ітэрацыі цыклу, я збіраюся пераехаць
мінімальны элемент у гэтай адсартаваныя частка спісу.
І як толькі я пераходжу нешта там, я ніколі не павінны глядзець на гэты элемент зноў.
Таму што як толькі я памяняць элемент у левай частцы спісу, гэта адсартаваны
таму што мы робім усё, што ў парадку павелічэньня з выкарыстаннем мінімуму.
Таму мы сказалі, добра, што мы ў становішчы я, і мы павінны глядзець на ўсе элементы
справа ад мяне, каб знайсці мінімум.
Такім чынам, гэта азначае, што мы хочам глядзець з г + 1 у канец спісу.
І зараз, калі элемент, які мы ў цяперашні час глядзім на гэта менш, чым нашы мінімальныя да гэтага часу,
які, памятаеце, што мы пачынаем з мінімальным проста быць
любога элемента мы ў цяперашні час, я буду лічыць, што гэта мінімум.
Калі я знайду элемент, які менш, чым гэта, то я буду казаць, добра,
Ну, я знайшоў новы мінімум.
Я буду памятаць, дзе што было мінімальным.
>> Так што цяпер, калі я прайшоў праз гэта права несортированные сегменце,
Я магу сказаць, што я збіраюся памяняць месцамі мінімальны элемент з элементам, які знаходзіцца ў становішчы я.
Гэта збіраецца пабудаваць мой спіс, адсартаваны маёй частцы спісу злева направа,
і мы ніколі не павінны глядзець на элемент зноў, як толькі яна ў гэтай частцы.
Як толькі мы змяніў яго.
Так што давайце працаваць выбар роду ў гэтым спісе.
Сінія элементам тут будзе я, а чырвоны элемент будзе мінімальным элементам.
Так што я ўсё пачынаецца шлях у левай частцы спісу, так на 5.
Цяпер нам трэба знайсці мінімум несортированные элемент.
Таму мы кажам, 0 <5, так што 0 з'яўляецца мой новы мінімум.
>> Але я не магу спыніцца, таму што нават калі мы можам прызнаць, што 0 з'яўляецца найменшай,
нам трэба запусціць праз любы іншы элемент спісу, каб пераканацца.
Такім чынам, 1 больш, 6 больш, 4 больш.
Гэта азначае, што пасля таго, гледзячы на ​​ўсе гэтыя элементы, я вызначалі 0 з'яўляецца найменшай.
Так што я збіраюся памяняць 5 і 0.
Аднойчы я памяняць, што я збіраюся атрымаць новы спіс, і я ведаю, што я ніколі не трэба глядзець на што 0 раз
таму што як толькі я змяніў яго, я дамовіўся яго, і мы зрабілі.
Цяпер так ужо здарылася, што сіні элемент зноў 5,
і мы павінны глядзець на 1, 6 і 4, каб вызначыць, што 1
з'яўляецца найменшай мінімальным элементам, таму мы перастаўляць 1 і 5.
Зноў жа, мы павінны глядзець на - параўнаць ад 5 да 6 і 4,
і мы збіраемся памяняць 4 і 5, і, нарэшце, параўнаць
гэтыя 2 нумары і памяняць іх месцамі, пакуль мы не атрымаем нашы адсартаваны спіс.
Любыя пытанні па выбары роду?
Добра. Давайце пяройдзем да апошняй тэме тут, і гэта Рэкурсія.
>> Рэкурсія, памятаеце, што гэта сапраўды мета рэч, дзе функцыя
неаднаразова называе сябе.
Так што ў нейкі момант, у той час як нашы Fuction неаднаразова называе сябе,
там павінна быць некаторы кропцы, у якой мы перастаць называць сябе.
Таму што калі мы не зробім гэтага, то мы проста будзем працягваць рабіць гэта вечна,
і наша праграма проста не будзе спыняцца.
Мы называем гэта стан базавага варыянту.
І базавы варыянт, кажа, замест выкліку функцыі зноў,
Я проста хачу вярнуць некаторы значэнне.
Таму, як толькі мы вярнуліся значэнне, мы перасталі называць сябе,
і астатнія выклікі мы зрабілі да гэтага часу можна вярнуць.
У супрацьлегласць базу выпадку з'яўляецца рэкурсіўнага выпадку.
І гэта, калі мы хочам зрабіць яшчэ адзін выклік функцыі, якія мы ў цяперашні час цалі
І мы, верагодна, хоць і не заўсёды, хочуць выкарыстоўваць розныя аргументы.
>> Так што, калі ў нас ёсць функцыя пад назвай F і F толькі што патэлефанаваў прымаць па 1 аргумент,
і мы проста тэлефануюць F (1), F (1), F (1), і так ужо здарылася, што
аргумент 1 трапляе ў рэкурсіўнага выпадку, мы яшчэ ні разу не збіраецца спыняцца.
Нават калі ў нас ёсць базавы варыянт, мы павінны пераканацца, што ў канчатковым рахунку мы збіраемся ударыць, што базавы варыянт.
Мы не проста захаваць, якія пражываюць у гэтым выпадку рэкурсіўнай.
Наогул, калі мы называем сябе, мы, верагодна, будзем мець іншы аргумент кожны раз.
Вось вельмі просты рэкурсіўнай функцыі.
Так што гэта будзе вылічыць факториал ліку.
Да пачатку тут мы маем нашу базу выпадку.
У выпадку, калі п ≤ 1, мы не будзем называць факториальным зноў.
Мы збіраемся спыняцца, мы проста збіраемся вярнуць некаторы значэнне.
Калі гэта не так, то мы збіраемся ударыць нашым выпадку рэкурсіўнай.
Заўважце, што тут мы не проста выклікам факториал (п), таму што гэта было б вельмі карысна.
Мы будзем называць факториал нешта іншае.
>> І таму вы можаце ўбачыць, у рэшце рэшт, калі мы перадамо факториал (5) або нешта,
мы будзем называць факториал (4) і гэтак далей, і ў рэшце рэшт мы збіраемся ударыць гэтую базу выпадку.
Такім чынам, гэта добра выглядае. Давайце паглядзім, што адбываецца, калі мы рэальна працаваць гэта.
Гэта стэка, і давайце скажам, што асноўным будзе выклікаць гэтую функцыю з аргументам (4).
Таму, як толькі бачыць і факториал = 4, фактарнага будзе называць сябе.
Цяпер, раптам, у нас ёсць факториал (3).
Такім чынам, гэтыя функцыі будзе працягваць расці, пакуль у рэшце рэшт мы патрапілі нашу базу выпадку.
На дадзены момант, вяртае значэнне гэтага з'яўляецца вяртанне (NX вяртаецца значэння гэтага),
Вяртаецца значэнне гэтага NX вяртаецца значэння гэтаму.
У канчатковым рахунку мы павінны ўразіць некаторы лік.
У верхняй тут, мы кажам, вяртае 1.
Гэта азначае, што, калі мы вернемся гэты лік, мы можам поп гэтым з стэка.
Так што гэта факториал (1), то зроблена.
Калі 1 вяртаецца, гэта факториал (1) вяртаецца, гэта вяртанне да 1.
Вяртаецца значэнне гэтага, памятаю, быў NX вяртаецца значэння гэтаму.
Так нечакана, гэты хлопец ведае, што я хачу вярнуць 2.
>> Так што памятаеце, вярнуць значэнне гэта проста NX вяртаецца значэння тут.
Так што цяпер мы можам сказаць, 3 х 2 і, нарэшце, тут мы можам сказаць,
гэта проста будзе 4 х 3 х 2.
І як толькі гэта вяртаецца, мы спускаемся да аднаго ўнутры цэлага асноўны.
Любыя пытанні па рэкурсіі?
Добра. Такім чынам, ёсць больш часу на пытанні ў канцы,
але цяпер Джозэф пакрые тыя, што засталіся пытанні.
>> [Джозэф Ong] Усё ў парадку. Так што цяпер мы казалі аб рэкурсіі,
Давайце трохі пагаворым аб тым, што зліццё сартавання.
Зліццё роду ў асноўным іншы спосаб сартавання спісу лікаў.
І як гэта працуе, з сартавання зліццём у вас ёсць спіс, і тое, што мы робім,
мы кажам, давайце падзяліць гэта на 2 палоўкі.
Мы спачатку запусціць сартавання зліццём зноў на левай палове,
Затым мы запусцім сартавання зліццём на правай палове,
і гэта дае нам цяпер 2 палоўкі, якія сартуюцца, і зараз мы збіраемся аб'яднаць гэтыя палоўкі разам.
Гэта трохі цяжка зразумець без прыкладу, таму мы будзем праходзіць праз руху і паглядзець, што адбываецца.
Такім чынам, вы пачынаеце з гэтага спісу, мы падзялілі яго на 2 палоўкі.
Мы праводзім сартавання зліццём на левай палове першай.
Дык вось левую палову, і цяпер мы прапусціць іх праз гэты спіс яшчэ раз
які перадаецца ў сартавання зліццём, а затым мы паглядзім, зноў жа,
у левай частцы гэтага спісу, і мы пабеглі сартавання зліццём на ім.
Цяпер мы пяройдзем да спісу з 2 лічбаў,
і цяпер левая палова ўсяго 1 элемент доўгі, і мы не можам
падзяліць спіс, у якім толькі 1 элемент у палову, так што мы проста скажам, раз у нас ёсць 50,
які знаходзіцца ўсяго ў 1 элемент, ён ужо адсартаваны.
>> Як толькі мы скончым з гэтым, мы бачым, што мы можам
перайсці на правую палову гэтага спісу,
і 3 таксама сартуюцца, і таму цяпер, што абедзве паловы гэтага спісу сартуюцца
мы можам аб'яднаць гэтыя лічбы разам.
Такім чынам, мы глядзім на 50 і 3, 3 менш, чым 50, таму ён ідзе ў першы і затым 50 прыходзіць цалі
Цяпер гэта будзе зроблена, мы вернемся да гэтага спісу і сартаванне гэта правая палова.
42 з'яўляецца яго уласны нумар, так што гэта ўжо адсартаваныя.
Такім чынам, зараз мы параўнаем гэтыя 2 і 3 менш, чым 42, так што атрымлівае пакласці ў першым,
цяпер 42 атрымлівае пакласці ў, і 50 атрымлівае уставіў
Дык вось, гэта спарадкаваныя, мы прайсці ўвесь шлях наверх, 1337 і 15.
Ну, мы зараз паглядзім на левую палову гэтага спісу; 1337 сама па сабе так што ён сартуецца і тое ж самае з 15.
Так што цяпер мы аб'яднаем гэтыя 2 нумары для сартавання, што першапачатковы спіс, 15 <1337,
таму яна ідзе ў першы, то 1337 ідзе цалі
А цяпер сартуюцца абедзве палоўкі зыходнага спісу наверсе.
І ўсё, што нам трэба зрабіць, гэта аб'яднаць гэтыя.
Мы глядзім на першыя 2 нумары з гэтага спісу, 3 <15, таму яна ідзе ў сартавання масіва ў першую чаргу.
15 <42, таму яна ідзе цалі Цяпер, 42 <1337, які ідзе цалі
50 <1337, таму яна ідзе цалі І заўважыў, што мы проста ўзялі 2 нумары з гэтага спісу.
Такім чынам, мы не толькі чаргуючы 2 спісу.
Мы проста гледзячы на ​​пачатак, і мы бярэм элемент
вось і менш, а затым пакласці яго ў наш масіў.
Цяпер мы аб'ядналіся ўсе палавінкі, і мы зрабілі.
>> Любыя пытанні аб зліцці роду? Да?
[Студэнт] Калі гэта расшчапленне ў розных групах, чаму яны не проста падзяліць яго адзін раз
і ў вас ёсць 3 і 2 у групе? [Астатнія пытанні неразборліва]
Прычына - так што пытанне ў тым, чаму мы не можам проста аб'яднаць іх у той першы крок пасля таго, як яны ў нас ёсць?
Таму мы можам зрабіць гэта, пачніце з самага левага элементы з абодвух бакоў,
, А затым ўзяць паменш і паклаў яго ў тым, што мы ведаем, што гэтыя
асобныя спісы ў адсартаваным заказаў.
Так што, калі я гляджу на самы левы элементы абедзвюх палоў,
Я ведаю, што яны збіраюцца быць драбнюткіх элементаў з гэтых спісаў.
Так што я магу пакласці іх у месцах найменшага элемента гэтага вялікага спісу.
З іншага боку, калі я гляджу на гэтыя 2 спісу другога ўзроўня там,
50, 3, 42, 1337 і 15, тым не сартуюцца.
Так што, калі я гляджу на 50 і 1337, я збіраюся паставіць 50 у маім спісе першым.
Але гэта не мае сэнсу, так як 3 найменшы элемент з усіх з іх.
Такім чынам, адзіная прычына, мы можам зрабіць гэта аб'яднанне крок, таму што нашы спісы ўжо адсартаваныя.
Менавіта таму мы павінны спускацца на ўсім шляху да дна
таму што, калі ў нас ёсць толькі адно лік, вы ведаеце, што адзін нумар
само па сабе ўжо з'яўляецца адсартаваны спіс.
>> Ёсць пытанні? Няма?
Складанасць? Ну, вы бачыце, што на кожным кроку ёсць канец ліку,
і мы можам падзяліць спіс часопіса 1/2 п раз,
дзе мы атрымаем гэты часопіс п х п складанасці.
І вы ўбачыце, у лепшым выпадку для сартавання зліццём п § п, і так ужо здарылася,
, Што ў горшым выпадку, ці Ω там, таксама п п ўвайсці.
Трэба мець на ўвазе.
Рухаемся далей, давайце пяройдзем да некаторых супер асноўны файл I / O.
Калі вы паглядзіце на Scramble, вы заўважыце, у нас была нейкая сістэма
дзе вы маглі б напісаць у лог-файл, калі вы чытаеце па коду.
Давайце паглядзім, як вы маглі б зрабіць гэта.
Ну, у нас Fprintf, якія вы можаце думаць, як толькі Printf,
але толькі друк у файл, а і, такім чынам, F у самым пачатку.
Такі код тут, што ён робіць, як вы, магчыма, бачылі ў Scramble,
яна праходзіць праз вашу 2-мерны масіў з друку шэраг за шэрагам, што ліку.
У гэтым выпадку Выводзіць на ваш тэрмінал ці што мы называем стандартны вывад раздзеле.
>> І цяпер, у гэтым выпадку, усё, што мы павінны зрабіць, гэта замяніць Printf з Fprintf,
сказаць яму, што файл, які вы хочаце друкаваць, і ў гэтым выпадку ён проста выводзіць яе на гэты файл
замест таго, каб друкаваць яго на тэрмінал.
Ну, тое, што напрошваецца пытанне: Дзе ж узяць такога роду файлаў з, так?
Мы прайшлі ўвайсці ў гэтую Fprintf Fuction але мы паняцця не меў, адкуль яно ўзялося.
Ну, у самым пачатку кода, тое, што мы мелі, быў гэты кавалак кода сюды,
, Які ў асноўным кажа, што адкрыць файл выклікае log.txt.
Што мы робім пасля гэтага, што мы павінны пераканацца, што файл на самай справе быў паспяхова адкрыты.
Так што, магчыма, не па некалькіх прычынах, вам не хапае месца на вашым кампутары, напрыклад.
Такім чынам, гэта заўсёды важна, перш чым рабіць любыя аперацыі з файламі
што мы правяраем, што файл быў адкрыты паспяхова.
Так што гэта, гэта аргумент Еореп, добра, мы можам адкрыць файл па-рознаму.
Што мы можам зрабіць, мы можам перадаць яго вага, а значыць змяніць файл, калі ён выходзіць ужо,
Мы можам перадаць, што яны дадаем у канец файла, а не перакрываючы яго,
ці мы можам паказаць R, што азначае, давайце адкрыць файл толькі для чытання.
Такім чынам, калі праграма спрабуе ўнесці змены ў файл,
крычаць на іх і не дазваляюць ім гэта зрабіць.
Нарэшце, калі мы скончылі з файлам, зрабіў робяць аперацыі на ёй,
Мы павінны пераканацца, што мы закрываем файл.
І вось у канцы вашай праграмы, вы збіраецеся перадаць іх зноў
гэта файл, які вы адкрылі, і проста зачыніць яго.
Так што гэта нешта важнае, што вы павінны пераканацца, што вы робіце.
Так што памятаеце, што вы можаце адкрыць файл, то вы можаце запісаць у файл,
рабіць аперацыі ў файле, але тады вы павінны зачыніць файл у канцы.
>> Любыя пытанні па асноўных файла I / O? Да?
[Студэнт пытанне, неразборліва]
Прама тут. Пытанне ў тым, дзе ж гэты файл log.txt з'яўляюцца?
Ну, калі вы проста даць яму log.txt, ён стварае яго ў тым жа каталогу, што і выкананы файл.
Так што, калі вы - >> [Студэнцкі пытанне, неразборліва]
Так. У той жа тэчцы, ці ў тым жа каталогу, як вы гэта называеце.
Цяпер памяць, стэк і кучу.
Так, як гэта памяць, выкладзеных у кампутары?
Ну, вы можаце сабе памяць як свайго роду гэтым блоку тут.
І ў памяці ў нас ёсць тое, што называецца кучай затрымаліся там, і стэк, што там унізе.
І куча расце ўніз, а стэк расце ўверх.
Так як Томі згадваў, - о, добра, і ў нас ёсць гэтыя іншыя 4 сегментаў, якія я атрымаю у секунду -
Як сказаў Томі раней, вы ведаеце, як яго называюць сябе функцыі і называюць адзін аднаго?
Яны ствараюць такога роду кадра стэка.
Ну, калі асноўныя выклікі Фу, Фу атрымлівае пакласці ў стэк.
Foo называе, бар атрымаеце паставім у стэк, і што атрымлівае пакласці ў стэк пасля.
І калі яны вернуцца, кожная з іх атрымліваюць зняць стэк.
Што кожны з гэтых месцаў і памяць трымаць?
Ну, верхні, які з'яўляецца сегмент тэксту, утрымлівае саму праграму.
Такім чынам, машынны код, што там, як толькі вы скампіляваць праграму.
Далей, любая ініцыялізуецца глабальныя зменныя.
>> Такім чынам, у Вас ёсць глабальныя зменныя ў вашай праграме, а вы кажаце, як, = 5,
, Які атрымлівае пакласці ў гэтым сегменце, і прама пад гэтым,
ў вас ёсць нейкія неинициализированные глабальныя дадзеныя, якія проста INT,
але вы не кажу, што гэта роўна нічога.
Зразумейце, гэта глабальныя зменныя, так што яны за межамі асноўнага.
Такім чынам, гэта азначае, што любыя глабальныя зменныя, якія абвешчаныя, але не ініцыялізуецца.
Так што ў кучы? Памяць размяркоўваецца з дапамогай таНос, які мы атрымаем у няшмат.
І, нарэшце, са стэкам ў вас ёсць нейкія лакальныя зменныя
і любы функцыі можна выклікаць у любы з іх параметраў.
Апошняя рэч, вы сапраўды не павінны ведаць, што зменныя асяроддзі рабіць,
але кожны раз, калі вы запускаеце праграму, ёсць нешта звязана, як
гэтае імя карыстальніка, які запусціў праграму.
І гэта будзе як бы на дне.
З пункту гледжання адрасы памяці, якія з'яўляюцца шаснаццаткавыя значэння,
Значэння ў верхняй пачынаюцца з 0, і прайсці ўвесь шлях да дна.
У гэтым выпадку, калі вы знаходзіцеся на 32-бітнай сістэме,
адрасе, паказанаму ўнізе будзе 0x, а затым А.Ф., таму што гэта 32 біт,
, Што на 8 байт, і ў гэтым выпадку 8 байт адпавядае 8 шаснаццатковых лічбаў.
Так што тут вы будзеце мець, быццам бы, 0xffffff, і там вы будзеце мець 0.
Так што паказальнікі? Некаторыя з вас, магчыма, не пакрытыя гэтым у раздзеле раней.
але мы не ўдавацца ў лекцыі, таму паказальнік проста тып дадзеных
якія крамах, а не нейкае значэнне, напрыклад 50, яна захоўвае адрас пэўнае месца ў памяці.
Як і што памяць [неразборліва].
Такім чынам, у дадзеным выпадку, тое, што мы ёсць, мы маем паказальнік на цэлае або цэлы лік *,
і змяшчае гэтым шаснаццатковы адрас 0xDEADBEEF.
>> Такім чынам, што мы маем цяпер, гэты паказальнік паказвае на пэўнае месца ў памяці,
і гэта толькі, значэнне 50 у гэта размяшчэнне ў памяці.
На некаторых 32-бітных сістэмах, на ўсіх 32-бітных сістэм, паказальнікі займаюць 32 біта ці 4 байта.
Але, напрыклад, на 64-бітнай сістэме, паказальнікі з'яўляюцца 64-бітнымі.
Так што тое, што вы хочаце, каб трымаць у розуме.
Такім чынам, на канец-бітнай сістэмы, паказальнік канца біт.
Паказальнікі з'яўляюцца свайго роду цяжка пераварыць без дадатковых рэчаў,
так давайце пройдзем прыклад дынамічнага размеркавання памяці.
Што дынамічнага размеркавання памяці робіць для вас, або тое, што мы называем таНос,
яна дазваляе вылучыць нейкі дадзеных за межамі здымачнай пляцоўцы.
Такім чынам, гэтыя дадзеныя з'яўляецца свайго роду больш сталым на працягу ўсяго тэрміну праграмы.
Таму што, як вы ведаеце, калі вы аб'явіце х ўнутры функцыі, а функцыя вяртае значэнне,
Вам больш не маюць доступу да дадзеных, якія захоўваюцца ў х.
Што паказальнікі будзем рабіць, яны дазваляюць нам захоўваць памяць ці захоўваюць значэння
ў іншы сегмент памяці, а менавіта ў кучу.
Цяпер, калі мы вернемся з функцый тых часоў, пакуль у нас ёсць паказальнік
у тое ж месца ў памяці, тое, што мы можам зрабіць, мы можам проста глядзець на значэнні там.
Давайце паглядзім на прыкладзе: Гэта наша памяць макет зноў.
І ў нас ёсць гэтая функцыя, асноўны.
Што яна робіць гэта - добра, так проста, праўда? - Int х = 5, вось толькі на стэку ў галоўным.
>> З іншага боку, зараз мы аб'яўляем паказальнік, які выклікае функцыю giveMeThreeInts.
І вось зараз мы ідзем у гэтую функцыю, і мы ствараем новы кадр стэка для яго.
Аднак, у гэтым кадры стэка, мы заяўляем Int * тэмпература,
які ў mallocs 3 цэлых для нас.
Такім чынам, памер Int дасць нам колькі байт гэтым Int ёсць,
і таНос дае нам, што многія байт прасторы ў кучы.
Такім чынам, у гэтым выпадку, мы стварылі дастаткова месца для 3 ліку,
і куча шлях там, таму я намаляваў яе вышэй.
Як толькі мы скончым, мы вернемся сюды, вам трэба ўсяго толькі 3 цэлымі вярнуліся,
і яна вяртае адрас, у дадзеным выпадку над тым, дзе гэтая памяць.
І мы паставілі паказальнік = выключальнік, і там у нас ёсць яшчэ адзін паказальнік.
Але тое, што гэтая функцыя вяртае ўкладваецца тут і знікае.
Такім чынам, тэмп знікае, але мы па-ранейшаму падтрымліваюць адрасы, дзе
гэтыя 3 ліку знаходзяцца ўнутры сеткі.
Такім чынам, у гэтым наборы, паказальнікі вобласцю на мясцовым узроўні для складзеных кадраў,
але памяць да якіх яны ставяцца ў кучу.
>> Ці мае гэта сэнс?
[Студэнт] Не маглі б вы паўтарыць? >> [Іосіф] Так.
Так што, калі я вярнуся ледзь-ледзь, вы бачыце, што тэмпература выдзелена
некаторы аб'ём памяці ў кучы там.
Таму, калі гэтая функцыя, giveMeThreeInts вяртаецца, гэты стэк тут збіраецца знікаць.
А разам з ёй любы з зменных, у дадзеным выпадку, гэта паказальнік, які быў вылучаны ў стэк кадра.
Гэта значыць знікне, але так як мы вярнуліся тэмпература
і мы паказальніка = тэмпература, паказальнік цяпер будзе ўказваць тую ж самую памяць аб месцы, тэмп быў.
Так што цяпер, нават калі мы страцім тэмп, што мясцовыя паказальнік,
Мы па-ранейшаму захоўваюць адрас памяці, што ён быў накіраваны ўнутр гэтай зменнай паказальнік.
Пытанні? Гэта можа быць нават заблытанай тэмы, калі вы не перайшлі яго ў раздзеле.
Мы можам, ваш TF вызначана пойдзе на гэта і, вядома, мы можам адказаць на пытанні
У канцы сесіі па аглядзе для гэтага.
Але гэта свайго роду складанае пытанне, і ў мяне ёсць іншыя прыклады, якія збіраюцца, каб паказаць
, Якая дапаможа высветліць, што паказальнікі на самай справе.
>> У гэтым выпадку, паказальнікаў эквівалентна масіваў,
так што я магу проста выкарыстоўваць гэты паказальнік, як тое ж самае, Int масіва.
Так што я індэксацыі ў 0, і змяненне першае чысло 1,
змена 2. ліку 2, і 3-й цэлы лік 3.
Так што больш на паказальнікі. Ну, успомніце Бинки.
У гэтым выпадку мы вылучылі паказальнік, ці мы абвясцілі паказальнік,
але спачатку, калі я толькі што абвясцілі паказальнік, гэта не паказвае на любой памяці.
Гэта проста смецце значэння ўнутры яго.
Так што я паняцця не маю, дзе гэты паказальнік вызначае.
Ён мае адрас, які проста напоўнены 0 і 1, дзе ён быў з самага пачатку абвешчаны.
Я нічога не магу зрабіць з гэтым, пакуль я называю таНос на яе
і гэта дае мне мала месца ў кучы, дзе я магу паставіць значэння ўнутры.
Зноў жа, я не ведаю, што ўсярэдзіне гэтай памяці.
Таму першае, што я павінен зрабіць, гэта праверыць, ці з'яўляецца сістэма мела досыць памяці
, Каб даць мне таму 1 цэлае, у першую чаргу, таму я раблю гэта праверыць.
Калі паказальнік пусты, гэта азначае, што ў яго не было досыць месцы, ці іншыя памылкі,
так што я павінен выйсці з маёй праграмы.
Але калі гэта і не ўдалося, цяпер я магу выкарыстоўваць гэты паказальнік
і тое, што * паказальнік робіць гэта наступным дзе адрас
дзе гэта значэнне, і гэта адрознівае яго роўным 1.
Так што тут, мы правяраем, калі што памяць існуе.
>> Калі вы ведаеце, яна існуе, вы можаце змясціць у яе
Якое значэнне вы хочаце ўкласці ў яе, у гэтым выпадку 1.
Як толькі мы скончым з гэтым, неабходна, каб вызваліць гэты паказальнік
таму што мы павінны вярнуцца да сістэмы, памяці, якія вы прасілі ў першую чаргу.
Паколькі кампутар не ведае, калі мы скончым з гэтым.
У гэтым выпадку мы відавочна кажа ён, добра, мы скончылі з гэтай памяццю.
Калі некаторыя іншыя працэсы ў ёй мае патрэбу, некаторыя іншыя праграмы ў ёй мае патрэбу, не саромейцеся ісці наперад і прымаць яго.
Што мы можам зрабіць, гэта мы можам проста атрымаць адрас лакальных зменных на здымачнай пляцоўцы.
Так Int х знаходзіцца ўсярэдзіне складзеныя рамках асноўнай.
І калі мы выкарыстоўваем гэты знак, гэта і аператара, што яна робіць гэта
ён прымае х, і х толькі некаторыя дадзеныя ў памяці, але ў яго ёсць адрас.
Яна знаходзіцца недзе. Так, патэлефанаваўшы па тэлефоне і х, тое, што гэта робіць ён дае нам па адрасе х.
Робячы гэта, мы робім паказальнік кропкі, дзе х знаходзіцца ў памяці.
Цяпер мы проста зрабіць нешта накшталт * х, мы збіраемся, каб атрымаць 5 назад.
Зорка завецца разнаймення яго.
Вы вынікаеце адрас, і вы атрымаеце значэнне яна захоўваецца там.
>> Ёсць пытанні? Да?
[Студэнт] Калі вы гэтага не зробіце 3-завостраныя рэч, гэта ўсё яшчэ скампіляваць?
Так. Калі вы гэтага не зробіце 3-паказальнік рэч, яна па-ранейшаму будзе складаць,
Але я пакажу вам, што адбываецца ў секунду, а без гэтага,
гэта тое, што мы называем уцечкай памяці. Вы не даяце сістэме
Рэзервовае яго памяці, так што праз некаторы час праграма будзе назапашвацца
памяць, што яна не выкарыстоўваецца, і нішто іншае не можа яго выкарыстоўваць.
Калі вы калі-небудзь бачылі Firefox з 1,5 мільёна кілабайт на вашым кампутары,
ў дыспетчару задач, вось што адбываецца.
У вас ёсць уцечкі памяці ў праграме, што яны не апрацоўвае.
Так як жа арыфметыка паказальнікаў працы?
Ну, арыфметыка паказальнікаў накшталт як індэксацыя ў масіве.
У гэтым выпадку, у мяне ёсць паказальнік, і тое, што я раблю, я раблю паказальнік паказвае на першы элемент
гэтага масіў з 3 цэлых лікаў, якія я вылучыў.
Так што цяпер мне рабіць, зорка проста мяняе паказальнік на першы элемент у спісе.
Зорка паказальнік 1 ачкоў тут.
Такім чынам, паказальнік мышы тут, +1 з'яўляецца паказальнікам тут, паказальнік 2 з'яўляецца тут.
>> Так што даданне 1, тое ж самае, рухаючыся па гэтым масіве.
Што мы робім, калі мы робім паказальнік 1 Вы атрымаеце адрас тут,
і для таго, каб атрымаць значэнне тут, вы паклалі зорку ў ад усяго выказвання
Звяртацца да іх.
Такім чынам, у дадзеным выпадку, я ўсталёўваю першае месца ў гэтым масіве ў 1,
Другое месца 2, а трэцяе месца на 3.
Затым, што я раблю тут ёсць я друкую наш паказальнік +1,
які проста дае мне 2.
Цяпер я павялічваючы паказальнік, таму паказальнік роўна паказальнік +1,
, Якая рухаецца наперад.
І вось цяпер, калі я раздрукаваць паказальнік +1, паказальнік 1 цяпер 3,
які ў дадзеным выпадку выводзіць 3.
І для таго, каб нешта бясплатна, паказальнік, які я даю яму
павінны быць накіраваны на пачатак масіва, які я вярнуўся з таНос.
Такім чынам, у дадзеным выпадку, калі б я быў тэлефанаваць 3 прама тут, гэта было б няправільна,
таму што гэта ў сярэдзіне масіва.
Я павінен адняць, каб атрымаць на ранейшым месцы
пачатковая першым месцы перш чым я змагу вызваліць яго.
Такім чынам, вось больш складаны прыклад.
У гэтым выпадку, мы выдзяленні 7 знакаў у масіў знакаў.
>> І ў гэтым выпадку тое, што мы робім, мы цыклаў на працягу першых 6 з іх,
і мы ўсталёўваем іх у Z.
Такім чынам, для Int я = 0, г> 6, я + +,
Такім чынам, паказальнік + Я проста даць нам, у дадзеным выпадку,
паказальнік, паказальнік +1, 2 паказальнік, паказальнік +3, і гэтак далей, і гэтак далей у цыкле.
Што ён збіраецца рабіць гэта атрымлівае, што адрас, разыменовывает яго, каб атрымаць значэнне,
і змены, значэнне Z.
Затым, у канцы памятаеце, што гэта радок, ці не так?
Усе радкі павінны скончыць з нулявой сімвал завяршэння.
Такім чынам, што я раблю, гэта паказальнік ў 6 я паставіў пусты знак канца цалі
А зараз тое, што я ў асноўным раблю тут рэалізуецца Printf для радка, ці не так?
>> Такім чынам, калі ж Printf цяпер, калі яна дасягнула канца радка?
Калі яна знізіцца да нулявой сімвал завяршэння.
Такім чынам, у дадзеным выпадку, мае зыходныя кропкі, паказальнік на пачатак гэтага масіва.
Я надрукаваць першы знак з. Я перамясціць яго на адзін.
Я друкую гэты знак з. Я рухаюся яго.
І я працягваю рабіць гэта, пакуль я дайсці да канца.
А цяпер паказальнік канца * будзе разыменовать і атрымаць нулявы завяршальны сімвал назад.
І таму мая ў той час як цыкл выконваецца толькі тады, калі гэта значэнне не з'яўляецца нулявой сімвал завяршэння.
Такім чынам, цяпер я выйсці з гэтай завесы.
І таму, калі я адняць 6 з гэтага паказальніка,
Я вяртаюся ўвесь шлях з самага пачатку.
Памятаеце, я раблю гэта таму, што я павінен пайсці да пачатку, каб вызваліць яго.
>> Дык вось, я ведаю, што было шмат. Ці ёсць пытанні?
Калі ласка, так?
[Студэнт пытанне неразборліва]
Ці можаце вы сказаць, што гучней? Выбачайце.
[Студэнт] На апошнім слайдзе права, перш чым вызваліць паказальнік,
дзе вы былі на самай справе змяніць значэнне паказальніка?
[Джозэф] Так, прама тут. >> [Студэнт] О, усё ў парадку.
[Джозэф] Такім чынам, у мяне ёсць паказальнік мінус мінус, права,
які перамяшчае рэчы назад на адзін, а потым вызваліць яго,
таму што гэты паказальнік павінен быць паказала на пачатак масіва.
[Студэнт] Але гэта быў бы не патрэбен, калі б вы спыніліся пасля гэтага радка.
[Джозэф] Так што, калі я спыніўся пасля гэтага, гэта будзе разглядацца як ўцечка памяці,
таму што я не запусціць бясплатны.
[Студэнт] Я [неразборліва] пасля першых трох лініях, дзе вы былі паказальніка 1 [неразборліва].
[Джозэф] Угу. Так, што пытанне там?
Выбачайце. Не, няма. Ідзі, ідзі, калі ласка.
[Студэнт] Такім чынам, вы не змяніўшы значэнне паказальнікаў.
Вы не павінны былі б зрабіць паказальнік мінус мінус.
[Джозэф] Так, менавіта так.
Так што, калі я раблю паказальнік і паказальнік +1 +2,
Я не раблю паказальніка роўна паказальнік +1.
Такім чынам, паказальнік застаецца толькі паказвае на пачатак масіва.
І толькі калі я раблю плюс плюс, што ён усталёўвае значэнне назад у паказальнік,
што ён фактычна рухаецца ўздоўж гэтага.
Добра.
Яшчэ пытанні?
>> Зноў жа, калі гэта з'яўляецца свайго роду пераважнай, гэта будуць разгледжаны на сесіі.
Папытаеце вашага навучання калегаў пра гэта, і мы можам адказаць на пытанні ў канцы.
І звычайна мы не хацелі рабіць гэта мінус рэч.
Гэта павінна патрабуюць ад мяне адсочваць, наколькі я Зрушэнне ў масіве.
Так, у агульным, гэта проста растлумачыць, як працуе арыфметыка паказальнікаў.
Але тое, што мы звычайна падабаецца рабіць, мы хацелі б стварыць копію паказальніка,
і тады мы будзем выкарыстоўваць гэтую копію, калі мы рухаемся вакол у радок.
Такім чынам, у гэтых выпадку, калі вы выкарыстоўваеце копіі надрукаваць усю радок,
але мы не павінны рабіць, як паказальнік мінус 6 або адсочваць, колькі мы пераехалі ў гэты,
толькі таму, што мы ведаем, што наша зыходная кропка па-ранейшаму паказвае на пачатак спісу
і ўсё, што мы змянілі гэтая копія.
Так, у агульным, змяняць копіі арыгінальных паказальнік.
Не спрабуйце нешта накшталт - don't змяніць асобніках.
Спроба змяніць толькі копіі арыгінала.
Такім чынам, вы заўважыце, калі мы перадаем радок у Printf
Вы не павінны змясціць зорку перад ім, як мы рабілі з усімі іншымі разыменовывает, дакладна?
Так што, калі вы друкуеце з усёй радкі з% чакае, што гэта адрас,
і ў гэтым выпадку паказальнік або ў дадзеным выпадку, як масіў знакаў.
>> Персанажы, сімвал * з, і масівы адно і тое ж.
Паказальнік складаецца ў сімвалы і знакавыя масівы адно і тое ж.
А так, усё, што мы павінны зрабіць, гэта перадаць у паказальнік.
Мы не павінны праходзіць у як паказальнік * ці што-небудзь падобнае.
Такім чынам, масівы і паказальнікі адно і тое ж.
Калі вы робіце нешта накшталт X [Y] тут для масіва,
што ён робіць пад капотам гэта кажа, добра, што гэта масіў сімвалаў,
так што гэта паказальнік.
І таму х адно і тое ж,
і так, што ён робіць гэта дадае г х,
што тое ж самае, што рухацца наперад у памяці, што шмат.
А зараз х + у дае нам нейкі адрас,
і мы разыменовать адрас або сачыць за стрэлкамі
дзе гэта месца ў памяці, і мы атрымаем значэнне з гэтага месца ў памяці.
Такім чынам, так што гэтыя дзве дакладна такія ж рэчы.
Гэта проста сінтаксічны цукар.
Яны робяць тое ж самае. Яны проста розныя синтактика адзін для аднаго.
>> Такім чынам, што можа пайсці не так з паказальнікамі? Маўляў, шмат. Добра. Так, дрэнныя рэчы.
Некаторыя дрэнныя рэчы, якія вы можаце зрабіць, не правяраючы, калі ваш таНос выклік вяртае нуль, праўда?
У гэтым выпадку, я прашу сістэмы, каб даць мне - што гэта за нумар?
Мне падабаецца 2000000000 раз 4, так як памер цэлае 4 байта.
Я пытаюся ў яго для як 8000000000 байт.
Вядома, мой кампутар не будзе ў стане даць мне, што столькі ж назад памяці.
І мы не праверыць, калі гэта нуль, таму, калі мы спрабуем разнаймення яго там -
сачыць за стрэлкамі, дзе яна збіраецца - у нас няма гэтай памяці.
Гэта тое, што мы называем разнаймення нулявога паказальніка.
А гэта істотна прымушае Вас падаць.
Гэта адзін са спосабаў сегментацыі.
Іншыя дрэнныя рэчы, якія вы можаце зрабіць - гэта ня вельмі істотна.
Гэта было разнаймення нулявога паказальніка. Добра.
Іншыя дрэнных рэчаў - ну, каб выправіць, што вы проста пастаўце галачку там
, Якая правярае, ці з'яўляецца паказальнік з'яўляецца нулявым
і выйсці з праграмы, калі яна здараецца, што таНос вяртае нулявы паказальнік.
Гэта XKCD коміксаў. Людзі разумеюць гэта цяпер. Накшталт таго.
>> Такім чынам, памяць. І я пайшоў з гэтай нагоды.
Мы заклікаем таНос у цыкле, але кожны раз, калі мы называем таНос
мы губляем адсочваць, дзе гэты паказальнік паказвае на,
таму што мы выдаліўшы яго.
Такім чынам, першапачатковы выклік таНос дае мне памяці тут.
Мая паказальнік паказальнікі на гэта.
Зараз, я не вызваліць яго, так што цяпер я называю таНос зноў.
Цяпер ён паказвае тут. Зараз у маёй памяці паказвае тут.
Паказваючы тут. Паказваючы тут.
Але я страціў усё адрасы памяці тут, што я вылучыў.
І вось зараз у мяне няма ніякіх спасылак на іх больш.
Такім чынам, я не магу вызваліць іх за межамі гэтага цыклу.
І таму для таго, каб выправіць нешта накшталт гэтага,
калі вы забыліся, каб вызваліць памяць, і вы атрымаеце гэтую уцечку памяці,
Вы павінны вызваліць памяць, усярэдзіне гэтай завесы, як толькі вы зрабілі з ім.
Ну, гэта тое, што адбываецца. Я ведаю, многія з вас ненавіджу гэта.
Але цяпер - ура! Вы атрымліваеце як 44000 кілабайт.
Такім чынам, вы вызваліце ​​яго ў канцы цыклу,
і што збіраецца проста вызваліць памяць кожны раз.
Па сутнасці, ваша праграма не мае ўцечкі памяці больш.
>> А цяпер нешта яшчэ, што вы можаце зрабіць, гэта вызваліць частку памяці, што вы прасілі ў два разы.
У гэтым выпадку, вы таНос нешта, вы зменіце яго значэнне.
Вы вызваліць яго адразу, таму што вы казалі, што зрабілі з ім.
Але тады мы вызвалілі яго зноў.
Гэта тое, што вельмі дрэнна.
Ён не збіраўся першапачаткова сегментацыі,
але праз некаторы час, што гэта будзе падвойнае вызваленне гэтай псуе вашу кучу структуры,
і вы даведаецеся крыху больш аб гэтым, калі вы вырашылі ўзяць клас, як CS61.
Але па сутнасці, праз некаторы час ваш кампутар будзе заблытацца
пра тое, што вочка памяці, куды і дзе ён захоўваецца -
дзе дадзеныя захоўваюцца ў памяці.
І таму вызваленне паказальніка двойчы гэта дрэнна, што вы не хочаце рабіць.
>> Іншыя рэчы, якія могуць пайсці не так, не выкарыстоўвае SizeOf.
Такім чынам, у гэтым выпадку вы Malloc 8 байт,
і гэта тое ж самае, што і два цэлых ліку, правільна?
Такім чынам, гэта цалкам бяспечна, але гэта такое?
Ну, як Лукас казаў пра на розных архітэктурах,
цэлых лікаў рознай даўжыні.
Так, на прыладу, якое вы выкарыстоўваеце, цэлыя каля 4 байта,
але на некаторых іншых сістэмах яны могуць быць 8 байтаў або яны могуць быць 16 байт.
Так што, калі я проста выкарыстоўваць гэты нумар тут,
гэтая праграма можа працаваць на прыборы,
але ён не збіраецца вылучыць досыць памяці на некаторыя іншыя сістэмы.
У гэтым выпадку, гэта тое, што аператар SizeOf выкарыстоўваецца.
Калі мы называем SizeOf (INT), што гэта робіць
гэта дае нам памер цэлага ў сістэме, што праграма працуе.
Такім чынам, у дадзеным выпадку, SizeOf (INT) верне 4 на нешта накшталт прыбора,
і зараз гэта будзе 4 * 2, што на 8,
, Які з'яўляецца толькі аб'ём прасторы, неабходнага для двух цэлых лікаў.
На іншай сістэме, калі Int, як 16 байт ці 8 байтаў,
гэта проста збіраецца вярнуцца досыць байта для захоўвання гэтай сумы.
>> І, нарэшце, структуры.
Так што, калі вы хочаце захаваць судоку дошка ў памяць, як мы маглі б гэта зрабіць?
Вы можаце ўявіць сабе, як зменнай для першай рэччу,
зменных для другога рэч, зменная 3. рэч,
Зменная за чацвёрты рэч - дрэнна, праўда?
Так, адзін паляпшэнню вы можаце зрабіць на верхняй часткі гэтага зрабіць 9 х 9 масіва.
Гэта выдатна, але што, калі вы хочаце, каб звязаць іншыя рэчы з дошкі судоку
падабаецца тое, што цяжкасці платы,
або, да прыкладу, што ваш рахунак, і колькі часу гэта заняло вам вырашыць гэтую канферэнцыю?
Ну, што вы можаце зрабіць, вы можаце стварыць структуры.
Тое, што я ў асноўным кажу я вызначаю гэтую структуру тут,
і я вызначаю судоку борце якога складаецца з платы, што складае 9 х 9.
>> І тое, што яна ў яго ёсць паказальнікі на імя узроўні.
Яна таксама мае х і у, якія з'яўляюцца каардынатамі, дзе я знаходжуся цяпер.
Ён таксама час, выдаткаванае [неразборліва], і ён мае агульная колькасць хадоў я уведзеныя да гэтага часу.
І таму ў дадзеным выпадку, я магу згрупаваць цэлую кучу дадзеных у адну структуру
замест таго, каб, як ён лётае ў як розныя зменныя
што я не магу адсочваць.
І гэта дазваляе нам мець проста добры сінтаксіс для роду спасылкі розныя рэчы ўнутры гэтай структуры.
Я проста магу зрабіць board.board, і я атрымліваю судоку дошка назад.
Board.level, я зразумеў, як цяжка гэта.
Board.x і board.y даць мне каардынаты, дзе я мог бы быць у радзе.
І таму я доступе, што мы называем поля ў структуры.
Гэта вызначае sudokuBoard, які з'яўляецца тыпам, які ў мяне ёсць.
І вось цяпер мы тут. У мяне ёсць пераменная называецца "дошка" тыпу sudokuBoard.
І вось цяпер я магу атрымаць доступ да ўсіх палях, якія складаюць гэтую структуру сюды.
>> Любыя пытанні аб структурах? Да?
[Студэнт] Для Int х, у, вы абвясцілі абедзве на адной лініі? >> [Іосіф] Угу.
[Студэнт] Такім чынам, вы маглі б проста зрабіць гэта з імі з усімі?
Як і ў х, у коскі раз, што агульная?
[Джозэф] Так, можна вызначана зрабіць гэта, але прычына, я паклаў х і ў на той жа радку -
і пытанне ў тым, чаму мы можам проста зрабіць гэта на той жа лініі?
Чаму мы не проста паставіць усё гэта на адной лініі
х і ў звязаны адзін з адным,
і гэта толькі стылістычна больш правільна, у пэўным сэнсе,
таму што гэта групоўка дзве рэчы, на той жа лініі
што, як і роду адносяцца да адной рэчы.
І я проста падзяліць гэтыя часткі. Гэта проста стыль рэч.
Гэта функцыянальна робіць ніякай розніцы.
Любыя іншыя пытанні, якія тычацца структуры?
Вы можаце вызначыць з Pokédex структуры.
Покемон мае нумар і ён мае лісце, уладальнік, тып.
І потым, калі ў вас ёсць масіў з покемонов, вы можаце скласці Pokédex, дакладна?
Добра, халаднавата. Такім чынам, пытанні аб структур. Гэта звязана з структурам.
>> Нарэшце, GDB. Што GDB дазваляюць вам рабіць? Гэта дазваляе адладжваць вашу праграму.
І калі вы не выкарыстоўвалі GDB, я б рэкамендаваў глядзець на кароткі
і як раз збіраўся за тое, што GDB з'яўляецца, як вы з ім працаваць, як вы можаце выкарыстоўваць яго,
і праверыць яго на праграму.
І тое, што GDB дазваляе вам рабіць гэта дазваляе прыпыніць [неразборліва] да вашай праграмы
і практычнай лініі.
Напрыклад, я хачу, каб прыпыніць выкананне ў радку 3, як з маёй праграмы,
і пакуль я на лініі 3 я магу надрукаваць ўсе значэння, якія ёсць.
І так, што мы называем, як паўза ў лінію
гэта мы называем гэта пакласці супыну на гэтай лініі
і тады мы зможам раздрукаваць зменных на стан праграмы ў той час.
>> Мы можам затым адтуль прайсці па праграме лінія за лініяй.
І тады мы можам паглядзець на стан стэка ў той час.
І так, каб выкарыстоўваць GDB, што мы робім, мы называем ляск на файл C,
але мы павінны яго прайсці, ggdb сцяг.
І як толькі мы скончым з гэтым, мы проста запусціць GDB на выніковы файл высновы.
І таму вы зможаце атрымаць некаторыя, як маса тэксту, як гэта,
але на самой справе ўсё, што вам трэба зрабіць, гэта ўвесці каманды ў самым пачатку.
Перапынак асноўныя ставіць кропку супыну на асноўнай.
Спіс 400 пералічаныя радкоў кода вакол лініі 400.
І таму ў гэтым выпадку вы можаце проста паглядзець вакол і сказаць, ой,
Я хачу, каб усталяваць кропкі супыну ў радку 397, які гэтую лінію,
і тады ваша праграма працуе на такі крок, і ён збіраецца зламаць.
Гэта збіраецца зрабіць паўзу там, і Вы можаце раздрукаваць, напрыклад, значэнне нізкая або высокае.
І так ёсць куча каманд, якія вы павінны ведаць,
і гэта слайд-шоў будзе ісці на сайт,
так што калі вы проста хочаце, каб спасылкі на гэтыя або, як пакласці іх на свой шпаргалак, не саромейцеся.
>> Cool. Гэта была віктарына водгук 0, і мы будзем прытрымлівацца вакол, калі вы маеце любыя пытанні.
Добра.
>> [Апладысменты]
>> [CS50.TV]