[Powered by Google Translate] [Недеља 6] [Давид Ј. Малан] [Универзитет Харвард] [Ово је ЦС50.] [ЦС50.ТВ] 

Ово је ЦС50, и то је почетак недеље 6, па пар нових алата су сада доступни за вас да искористите, први који се зове ЦС50 Стиле. Шансе су, ако сте попут мене или било наставних момци, Вероватно сте видели програм чији стил изгледа мало несто овако. Можда почнете сечење неке углове касно ноћу, или ћете се бавити касније, и онда ТФ или ЦА долази преко у току радног времена. Онда је тешко за нас да чита. Па, овај код је синтаксно исправна, а то ће компајлирати, и то је заправо ће се покренути. Али то дефинитивно није 5 за стил. 

Али сада, ако идемо у овај директоријум овде- и приметио да имам цондитионс2.ц- и ја покренули ову нову команду, стиле50, на овом датотеке цондитионс2.ц, Ентер, приметити да ме је обавестио да је било стилизована. Гедит приметили да датотека је промењена на диску, и ако сам дугме релоад, сви ваши проблеми су сада аутоматизован. [Аплауз] То је једна од ствари које смо радили овај викенд. Схватите да је несавршена јер постоје неки код да једноставно неће бити у стању да савршено стилизовати, али схватите ово је сада алатка коју можете да искористите ако је само да се очисти неке од еррантли ставља заграда и слично. 

Али више убедљив сада је ЦС50 хотела. Са ЦС50 потврду, можете заправо обављају исте тестове исправност на свом коду да наставе момци су у стању да. Ово је командна линија услужни програм који долази сада у апарату чим ураде упдате50 као по псет 4 спецификације, и ви га користите у суштини овако. Трчиш командне цхецк50. Онда сте проћи у аргумент командне линије, или више опште познат као прекидач или заставу. Генерално, ствари које имају цртице зову прекидач за програм командне линије, тако ц прецизира провере које желите да покренете. 

Тестови које желите да покренете идентификовани су јединствено овом низу, 2012/псет4/ресизе. Другим речима, то је само произвољан али је јединствено ниска које користимо за јединствену идентификацију тестове псет 4 је исправност. А онда одредите простор одвојен листу датотека које желите да поставите да ЦС50 Провери за анализу. На пример, ако ја одем у мом решењу овде ресизе.ц- дозволите ми да отворим прозор већи терминал- и ја напред и покрените рецимо цхецк50 ц 2012/псет4/ресизе, и онда ићи напред и навести имена датотека, ресизе.ц, а затим притисните Ентер, он сабија, она постављено, проверава, а ја сам успео гомилу тестова. Један у црвеном у горњем левом углу каже да ресизе.ц и БМП постоје. То је био тест. То је питање које смо питали. И то је несрећан, јер одговор је био лажан. Бели текст испод ње очекује каже бмп.х да постоји, а то је једноставно моја кривица. Заборавила сам да га постави, па морам да уплоад обе датотеке, ресизе.ц и бмп.х. Али сада приметите све друге тестове су у жуто, јер нису покренути, па насмејано лице је вертикална јер је није ни срећан ни тужан, али морамо да се исправи тај проблем у црвеном пре него што су друге провере ће се покренути. 

Дозволите ми да поправим ово. Дозволите ми да умањите и реприза ово, овај пут са бмп.х такође на командној линији, Ентер, а сада ако све иде добро, то ће да провери и онда се вратити резултат од-задржите дах- све зелено, што значи да радим стварно добро на псет 4 до сада. Можете да видите и закључити из описног текста овде шта је то што ми тестирали. Тестирали смо прво да се фајлови постоје? Затим смо тестирали не ресизе.ц саставити? Онда смо тестирали то не промените величину 1к1 пиксела БМП када н ресизе фактор је 1. Сада, ако немаш појма шта је н, једном ћете зароните у псет 4, али то је једноставно здрав разум проверите да се уверите да нисте промена величине слика уопште ако промене величине фактор 1. Ако се, насупрот томе, она прилагођава 1к1 пиксела ка 1к1 пиксела БМП да правилно 2к2 када је н 2, а затим исто тако, моје сходно формира. 

Укратко, ово је значило да, једном, предузмите Прелазећи прстима из једначине испред вас пошаљите псет. Ви ћете тачно знати шта ваш ТФ ће ускоро знати када идете о подношењу неке од ових проблема скупова, и педагошки мотивација је заиста ставити прилика испред себе тако да када знате а приори да има бугова у свом коду и тестови који се не прошао, можете ставити у ефикаснијем време напред у решавању тих проблема него изгубити поене, добити повратне информације из ТФ, а онда, "Ахх," као да сам схватио да од. Сада барем постоји алат ће вам помоћи да пронађете то. То неће указати где је грешка, али то ће вам рећи оно што је симптоматично то. 

Сада схватају да тестови нису нужно коначан. Само зато што сте добили екран пун зеленог смилеи лица не значи ваш код је савршен, али то не значи који је прошао одређене тестове прописане спец. Понекад нећемо објавити чекове. На пример, детективски роман, један од аспеката псет 4, је врста разочаравајуће ако вам дам одговор о томе шта јесте, а ту је и број начина да се откривају ко лице је у том црвеном буке. Спецификације ће увек наведете у будућности псет 5 па надаље шта проверава постоје за вас. Приметићете да је ова бела УРЛ адреса на дну. За сада, ово је само дијагностички излаз. Ако посетите тај УРЛ, добићете гомилу лудих, криптичне поруке да сте добродошли да погледате, али то је углавном то за запослене тако да можемо дијагностиковати и отклањање грешака грешке у самом цхецк50. 

Без оклевања, идемо на тамо где смо стали. ЦС50 библиотека ми узео здраво за готово за неколико недеља, али онда прошле недеље, почели смо пилинг назад један од слојева њега. Почели смо стављајући на страну стринг у корист чега уместо? [Студенти] Цхар. Знак *, која је цхар све ово време, али сада не морам да се претварам да је стварни тип података стринг. Уместо тога, она је била синоним за врста цхар *, а стринг је низ знакова, па зашто то смисла да представљају низове као цхар * с? Шта цхар представљају у контексту овог концепта низу? Да >> [Студентски] Први карактер.. Добро је, први знак, али не баш први карактер. То су-[Ученици] Адреса. Добро, адреса првог карактера. Све што је потребно да представља ниску у меморију рачунара је само јединствена адреса његовог првог бајта. Не морате чак ни да знам колико дуго је јер како можете схватио динамички? [Студентски] Стринг дужине. Можете позвати дужину жица, одлично, али како стринг дужине ради? Шта то радиш? Да. [Студентски] Наставите док не добијете нулл карактер. Да, тачно, то је само понавља са петљом за, док је петља, год од * до краја, а крај је заступљен по \ 0, такозвани нул карактер, нул, не треба мешати са нула, што је показивач, који ће доћи у разговору поново данас. 

Вратили смо ољуштене слој ГетИнт, а онда је погледао на ГетСтринг, и сећам се да су од тих функција, или стварно, ГетСтринг, користила одређену функцију да стварно анализу, која је, читају или анализу, унос корисника. А шта је то нова функција? Сцанф или ссцанф. То је заправо долази у неколико различитих укуса. Ту је сцанф, ту је ссцанф, има фсцанф. За сада, међутим, да се усредсреди на један најлакше илустрована и пусти ме да иде напред и отворити у апарату фајл овако, сцанф1.ц. Ово је супер једноставан програм, али да уради нешто што никада нисмо урадили без помоћ ЦС50 библиотеке. Ово добија инт од корисника. Како то функционише? Па, у реду 16 тамо, примећујемо да прогласе инт зове к, а у овом тренутку у причи, шта је вредност од к? [Нечујан ученик одговор] [Давид М.] Тако је, ко зна, нека смеће вредност потенцијално, тако да у 17 година, ми смо само реци корисника дај ми број, молим те, и корак 18 је место где се добија занимљиво. Сцанф изгледа да позајми идеју из иф у томе што користи ове кодове формата у наводницима. % Д је наравно децимални број. Али зашто ја пролазу у & к уместо само Кс? Бивши је тачно. Да. [Нечујан ученик одговор] Тачно, ако је циљ тог програма, као и функције ГетИнт самој је да добије инт од корисника могу проћи функције све променљиве желим, али ако их не прође по референци или адресу или показивача, све синоним за потребе данашњих, онда функција нема способност да мења садржај те променљиве. То ће проћи у копији баш као бугги верзију своп да смо разговарали о неколико пута сада. 

Али уместо тога, радећи и к, буквално сам пролазу у шта? [Студентски] Адреса. >> Адреси к. То је као цртање мапа за функцију зове сцанф и говори овде, ово су смернице за комад меморије у рачунару да можете ићи сачувати неке цео унутра Да би ссцанф сада да урадим шта оператер, шта комад синтаксе ће то морати да користе иако га не можемо видети јер је неко други написао ову функцију? Другим речима - шта је то? [Студентски] Кс чита. Ту ће бити неких читање, али само у односу на к овде. Ако сцанф се донела адресу к, синтаксички, шта оператер је дужан да негде постоји Унутрашњост је сцанф имплементације тако да се сцанф заправо може написати број 2 на тој адреси? Да, тако *. Подсетимо се да је наша * дереференце оператера, што у суштини значи ићи тамо. 

Када сте предали адресу, као што је овде случај, сцанф је вероватно-ако смо заиста погледао око изворног кода- ради * к или еквивалент да стварно одем на ту адресу и тамо ставио неку вредност. Сада, као и за колико сцанф учитава са тастатуре, ћемо махати наше руке за данас. Само претпоставимо да оперативни систем омогућава ссцанф да разговарају до тастатуре корисника, али у овом тренутку сада у линији 19, када смо једноставно штампају к, чини се да је случај да сцанф ставила Инт у к. То је тачно како сцанф ради, и сећам се прошле недеље То је тачно како ГетСтринг и ГетИнт и његова друга породица функција коначно ради, иако са благим варијансе као ссцанф, што значи скенирање низ уместо тастатуре. Али хајде да погледамо мало варијансе ово. У сцанф2, ја стварно зезнуо. Шта није у реду и да ћу сакрити коментар који објашњава колико- шта није у реду са овим програмом, верзија 2? Будите што је могуће техничке овом тренутку. Изгледа прилично добро. То је лепо увучен, али- ок, како о будимо орезати до краћих питања? Линија 16. Шта линија 16 ради у прецизном већ техничка енглеском? Добијање мало незгодно. Да, Мајкл. [Студентски] То указује на првом слову ниске. 

Ок, близу. Дозволите ми да дотера мало. Указујући на првом слову ниске, ви декларисање променљиве зове бафер која ће указати на првом обраћању на ниске, односно, да ће указати конкретније знак. Обратите пажњу да не показује је заправо нигде јер нема оператор доделе. Нема знака једнакости, па све што радимо је додељивање променљиву зове бафер. То се дешава да се 32 бита јер је показивач, и садржај бафера вероватно на крају ће садржати адресу карактер, али за сада, шта бафер садржи? Само неки лажни, ко зна, нека смеће вредност, јер ми нисмо изричито иницијализован, тако да не би требало да преузме ништа. Ок, сада ред 17 је-шта линија 17 ради? Можда ће загрејати ово. Он штампа стринг, зар не? Он штампа Стринг молим. 

Линија 18 је врста позната сада у које смо управо видели варијансу овог али са различитим формата кода, па је у складу 18, ми говориш сцанф овде је адреса комад меморије. Желим да звони у низу, као што је имплицирано% с али проблем је у томе нисмо овде урадили неколико ствари. Шта је један од проблема? [Студентски] Покушава да дереференце нулл показивач. Добри, нулл, или само на други начин непознат показивачи. Ти предаје сцанф адресу, али сте рекли малочас да је адреса неке смеће вредност јер нисмо заправо доделити било шта, па ви говорите сцанф ефективно ићи ставио овде низ, али ми не знамо где се овде још увек је, тако да нисмо заправо издвојила меморије за бафер. Осим тога, оно што такође није ни говорио сцанф? Претпостављам да је ово био комад меморије, и то није био смеће вредност, али још увек не говори сцанф нешто важно. [Студентски] Где је то заправо, амперсанд. Амперсанд, тако да у овом случају, то је у реду. Пошто бафер је већ проглашен као показивач са * комад синтаксе, не морате да користите амперсанд јер је већ адреса, али мислим да сам га чуо овде. [Студентски] Како је велика? Добро, нећемо рећи сцанф колики је бафер, што значи да чак и ако су били тампон показивач, говоримо сцанф, ставио овде низ, али овде може бити 2 бајта, могло би да буде 10 бајта, то би могло да буде мегабајт. Сцанф нема појма, и зато је ово комад меморије вероватно, није ниска још. То је само жица када сте написали карактера и \ 0 до тог комад меморије. Сада је то само неки комад меморије. Сцанф неће знати када да престану писања на ту адресу. 

Ако се сећате неке примере у прошлости, где сам случајно уписани на тастатури Покушавам да преливају бафер, и разговарали смо у петак око управо то. Ако противник некако убацује у програм много већи реч или реченица или фраза онда сте очекивали можете преливати комад меморије, што може имати лоше последице, као узимање током целог самог програма. Морамо да поправимо ово некако. Дозволите ми да умањите и отићи у верзији 3 овог програма. То је мало боље. У овој верзији, приметити разлику. У 16. реду, опет сам ја проглашења променљиву зове бафер, али оно што је сада? То је низ од 16 карактера. То је добро, јер то значи да ја сада могу да кажем сцанф овде је стварна комад меморије. Скоро да мислим низова као показивачи сада, иако они нису у ствари еквивалент. Они ће различито понашају у различитим контекстима. Али то свакако случај да бафер референцирање 16 суседне слова, јер то је оно што је низ и био је за неколико недеља сада. 

Ево, ја кажем сцанф ево комад меморије. Овај пут, то је заправо комад меморије, али зашто је то програм и даље експлоатисати? Шта није у реду и даље? Ја сам рекао да ми 16 бајтова, али- [Студентски] Шта ако се упишете на више од 16 година? Тачно, шта ако корисник упише у 17 знакова или 1700 карактера? У ствари, да видимо ако не можемо саплели ове грешке сада. То је боље, али није савршена. Пусти ме само напред и покрените да сцанф3 да састави овај програм. Дозволите ми да покренете сцанф3, Стринг молим вас поздравим, и ми изгледа у реду. Дозволите ми да покушам нешто дужи, здраво. Ок, хајде да здраво како си данас, Ентер. Како се овде врсту среће, рецимо здраво како си. Дођавола. Ок, тако да смо се посрећило. Хајде да видимо, ако не можемо поправити. Не, то неће да ме пусте да копирате. Хајде да покушамо поново. У реду, станд би. Видећемо колико дуго могу да се претварам да се фокусирамо док још увек раде. Дођавола. То је прилично могуће, заправо. Ту смо. Поинт направио. 

Ово непријатно иако је такође, то је такође један од извора велике конфузије када пишете програме који имају бугова јер се манифестују само једном у неко време понекад. Реалност је да чак и ако је ваш број је потпуно сломљена, Можда једино да се потпуно сломљено једном у неко време јер понекад, у суштини оно што се дешава је оперативни систем додељује мало више меморије него што вас заиста потребно из било ког разлога, па нико други не користи меморију одмах након комад 16 карактера, тако да ако идете на 17, 18, 19, шта год, није то таква велика ствар. Сада, рачунар, чак и ако то не сруши у том тренутку, Можда евентуално користити бајта број 17 или 18 или 19 за нешто друго, при чему су ваше податке које сте тамо рекли, мада претерано дуго, ће добити преписани потенцијално неком другом функцијом. То не мора нужно ће остати нетакнута, али то не значи да ће изазвати СЕГ грешку. Али у овом случају, коначно сам обезбедио довољно знакова да сам у суштини премашила свој сегмент меморије, и бам, оперативни систем је рекао: "Жао ми је, то није добро, сегментација грешка." 

И хајде сад видимо да ли оно остаје овде у мом именику, приметити да ја овде имам овај фајл, језгро. Обратите пажњу да је ово опет зове језгро депонију. То је у суштини је фајл који садржи садржај меморије програма у тренутку у коме се срушио, и само овде пробати мало примера да ме пусте унутра и покретање ГДБ на сцанф3 а затим одредите трећи аргумент зове језгро, и приметио да ако сам овде навести шифру моћи ћемо као и обично са ГДБ да почнете да ходате кроз овај програм, и ја могу да трчим и чим сам ударио-као корак са командом у ГДБ- чим сам ударио потенцијално Бугги линију после куцања у огромној ниске, Ја ћу бити у стању да се заиста га идентификују овде. Више од тога, међутим, у делу у погледу основних депонијама и волим, тако да можете заправо џаку око унутар језгра депоније и видети шта лине програм вам није успело. Сва питања онда о показивачима и на адресе? Зато данас, ми ћемо почети узимајући здраво за готово да су ове ствари постоје и ми знамо тачно шта су. Да. 

[Студентски] Како то да ниси морао да стави амперсанд поред дела- Добро питање. Како сам дошао није морао да стави амперсанд поред низа знакова, као што сам раније урадио са већином наших примера? Кратак одговор је низови су мало посебан. Можете готово да мислиш бафер као што заправо адреса, и то је тако једноставно деси да буде случај да заграда нотација је погодност, тако да можемо да идемо у држач 0, 1, носећи носач 2, без потребе да користите ознаку *. То је мало беле лажи, јер низови и показивачи су, у ствари, мало другачије, али су се често, али не увек да се користе наизменично. Укратко, када функција очекује показивач на комад меморије, Можете да га положе адресу која је враћена од маллоц, па ћемо видети маллоц опет пре времена, или можете да га прође име низа. Не морате да урадите амперсанд са низовима, јер су они већ суштини као адресе. То је један изузетак. Угласте заграде да их посебно. 

Да ли сте ставили амперсанд поред бафер? Не у овом случају. То не би функционисало, јер опет, овог угла случаја где низови нису сасвим заправо адресе. Али ми ћемо можда вратити на то пре него што дуго са другим примерима. Хајде да покушамо да овде реши проблем. Имамо структуру података које смо користећи неко време познат као низ. Случај у тачки, то је оно што смо управо имали. Али низови имају неки упсидес и негативне. Низови су лепе зашто? Шта је једна ствар која вам се допада, у мери у којој вам се допада низови-о низовима? Шта је згодно о њима? Шта је убедљив? Зашто смо их увести у првом месту? Да. [Студентски] Они могу сачувати много података, а ви не морате да користите целу ствар. Можете да користите одељак. Добро, са низом можете складиштити много података, а ви не морате да користите све то, тако да можете овераллоцате, што може бити згодно ако не знате унапред колико нешто очекивати. 

ГетСтринг је савршен пример. ГетСтринг, написан од стране нас, нема појма колико слова можете да очекујете, тако чињеница да можемо издвојити комаде целовите меморије је добро. Низови се реши проблем који смо видели пре пар недеља сада где ваш код почиње да се пренесу у нешто веома лоше дизајниран. Подсетимо се да сам направио студент структуру зове Давид, а онда је заправо алтернатива, међутим, да имају променљиве под називом име и другу променљиву зове, мислим, кућа, и други променљиви позвао ИД јер у тој причи сам тада хтела да уведе нешто друго свиђа Роб у програм, па онда сам одлучио сачекати мало, Морам да преименујете ове променљиве. Назовимо рудник НАМЕ1, ид1, хоусе1. Назовимо Робов име2, хоусе2, ИД2. Али онда чекај мало, шта о Томи? Онда смо имали још три променљиве. Увели смо некога, четири комплета променљивих. Свет је почео да се компликују врло брзо, па смо увели Структуре, а оно што је убедљив о струцт? Шта Ц струцт да радите? То је заиста непријатно данас. Шта >> [нечујан ученик одговор?] Да, конкретно, типедеф вам омогућава да креирате нови тип података, и струцт, струцт кључна реч, омогућава вам да обухвати концептуално повезани делови података заједно а након тога их зову нешто као студент. 

То је добро јер сада можемо моделовати много више врста концептуално конзистентна појам студента у променљива него произвољно има један за ниске, један за ИД, и тако даље. Низови су лепе, јер су нам омогућити да почне чишћење наш код. Али, шта је мана сада од низа? Шта можете да не? Да. [Студентски] Морате да знате колики је. Морате да знате колики је, тако да је нека врста бола. Они од вас са претходног програмирања искуством знају да у многим језицима, као Јава, можете питати комад меморије, посебно низа, колики си, дужине, имовине, тако да кажем, и то је заиста згодно. У Ц, не могу ни назвати стрлен на генеричком низу јер стрлен, као реч подразумева, само за гудаче, и можете схватити дужину стринга због овог људског конвенције да се има \ 0, већ низ, више уопштено, само комад меморије. Ако је низ Интс, не постоји ће бити неки специјални карактер на крају чека. Морате да запамтите дужину низа. Друга мана низа дигао главу у себе ГетСтринг. Шта је још мана низа? Господине, само ти и ја данас. [Нечујан ученик одговор] >> То је шта? Је проглашен на стек. Ок, изјавио на стек. Зашто не свиђа? [Студентски] Зато што бива поново користити. Добија поново користити је. Ок, ако користите низ издвојити меморију, Ви не можете, на пример, да се врате јер је на стек. Ок, то је мана. А како би било да неко други са низом? Када га издвоји, ти си некако сјебана ако вам је потребно више простора него низ има. 

Затим смо увели, подсјетимо, маллоц, који нам је дао могућност да динамички алоцира меморију. Али, шта ако смо покушали сасвим другачији свет? Шта ако желимо да решимо неколико тих проблема тако да смо уместо тога, моје перо је заспао овде- шта ако уместо тога желели да суштински створи свет који се више не овако? То је низ, и, наравно, ова врста погоршава када смо погодили крај низа, и сада више нема простора за другу цео или другог карактера. Шта ако некако смо превентивно кажу добро, зашто не бисмо се опустите овај услов да су сви ови комади меморије бити континуални бацк то бацк, и зашто не, кад треба инт или цхар, дај ми простор за једног од њих? И када ми треба још један, дајте ми још један размак, а кад ми треба још, дај још простора. Предност која сада јесте да ако неко други узима меморију овамо, није велика ствар. Ја ћу узети ову додатну комад меморије овде и онда ово. 

Сада, само цака је у томе што је овај готово осећа као да имам гомила различитих променљивих. То се осећа као пет различитих променљивих потенцијално. Али шта ако ми украде идеју од жице чиме смо некако повезати ове ствари заједно концептуално, и шта ако сам урадио ово? Ово је мој веома лоше нацртана стрелица. Али претпоставимо да је сваки од ових комада меморије указао на други, а овај момак, који нема рођак са његове десне стране, нема такву стрелицу. То је у ствари оно што се назива повезана листа. Ово је нова структура података који нам омогућава да издвоје комад меморије, па још један, па још један, па још један, сваки пут ми желимо током програма, и сећам се да су сви некако везани буквално цхаининг их заједно, а ми смо то урадили сликовито овде са стрелом. Али у коду, шта ће бити механизам преко којег сте некако успео да се повеже, скоро као нуле, један комад на други комад? Могли би да користите показивач, зар не? Јер заиста стрелица која иде од горњег левог квадрата, овај момак овде на ово, могу садржавати унутар овог трга не само неки ИНТС, а не само неки знак, али шта ако ја заправо издвојила мало више простора, тако да сада, сваки од мојих комада меморије, иако ће ме коштати, сада изгледа мало више правоугаоног где је један од комада меморије се користи за број, као и број 1, а онда, ако овај момак чува број 2, овај други комад меморије се користи за стрелом, или још конкретније, показивач. И претпостављам да меморишете број 3 овамо, док ја користим ово да укаже на тог момка, и сад овај момак, претпоставимо желим само три такве комаде меморије. Ја ћу повући линију кроз то, указујући нулл. Нема додатних карактера. 

Заиста, ово је како можемо да идемо на имплементацији нешто што се зове повезана листа. Повезана листа је нова структура података, а то је одскочна даска ка много одгајиваца структуре података које почињу да решавају проблеме дуж линије Фацебоок-типа проблема и Гоогле типа проблемима где имате огромне сетова података, и то више не сече за складиштење све цонтигуоусли и користите нешто као линеарне претраге или чак нешто као бинарни претрагу. Хоћеш још боље трчање пута. У ствари, једна од светих Граилс ћемо причати о касније ове недеље или следећег је алгоритам чије време рада је константна. Другим речима, она увек има исту количину времена без обзира колики је улаз, а то би заиста било убедљиво, чак и више него нечим логаритамском. Шта је ово на екрану овде? Сваки од правоугаоника је управо оно што сам нацртао руком. Али ствар скроз са леве стране је посебна променљива. То ће бити један показивач, јер је један готцха са повезану листу, јер те ствари се зову, је да морате да виси на једном крају повезану листу. 

Баш као и са низом, морате да знате адресу првог знак. Иста ствар за повезаним листама. Морате да знате адресу првог комад меморије јер од тамо, можете стићи у сваки други. Мана. Коју цену плаћамо за ову разноврсност има динамички Значајан структура података да ако смо икада потребно више меморије, фино, само издвојити још један комад и извући из показивач старог на нови реп листи? Да. [Студентски] Потребно је око два пута онолико простора. Потребно је дупло толико простора, тако да је то дефинитивно мана, а ми смо видели Поента пре између времена и простора и флексибилности где је до сада, ми не треба 32 бита за сваку од ових бројева. Ми заиста потребна 64, 32 за броју и 32 за показивача. Али, хеј, имам 2 гигабајта РАМ-а. Додавање још 32 бита овде и овде не изгледа тако велика од договора. Али за великим скуповима података, то је дефинитивно додаје до буквално дупло толико. Шта је друго Лоша сада, или шта играни ми одустати, ако представљају спискове ствари са повезаном листом, а не низа? [Студент] Не могу да прођу уназад. Ви не можете прећи уназад, тако да си мало зезнуо ако ходате слева на десно помоћу фор петља или вхиле петље и онда схватиш: "О, ја желим да се вратим на почетак листе." Не могу, јер ови показивачи само иду од лева на десно, као стрелице показују. 

Сада можете да запамтите почетак листе са другом променљиве, али то је комплексност имати на уму. Низ, без обзира колико далеко идете, увек можете да урадите минус, минус, минус, минус и врати се одакле си дошао. Шта је овде још мана? Да. [Нечујан ученик питање] Могао, па си ви заправо сте управо предложио структуру података зове двоструко повезана листа, и заиста, ти би додати још једну показивач на сваку од ових правоугаоника који иде други правац, који наопако сада можете прећи и назад, мана које се сада ви користите три пута више меморије као што смо некада и додао сложеност у смислу кода морате да напишете да га добијете праву. Али ово су све можда врло разумни компромиси, ако преокрет је важније. Да. [Студент] Такође не можете имати 2Д повезану листу. Добро, не можете заиста имају 2Д повезане листе. Ти би могао. То није ни изблиза лако као низа. Као низу, ти отворену заграду, затворени постоље отворено постоље затворен носач, и добити неки 2-димензионалну структуру. Могли спровести 2-димензионалну повезане листе ако ти додаци као што је предложио-трећи показивач на сваку од ових ствари, и ако мислите о другој листи долази на вас 3Д стил на екрану за све нас, што је само још један ланац неке врсте. Могли би то да урадим, али то није тако једноставно као куцање отворену заграду, заграда. Да. [Нечујан ученик питање] Добро, тако да је ово прави бунтовник. 

Ови алгоритми које смо пинед преко, као и ох, бинарне претраге, можете да претражујете низ бројева на табли или именик толико много брже уколико користите завади па владај и бинарни претрагу алгоритам, али бинарни тражи потребно две претпоставке. Један, који је сортиран подаци. Сада смо вероватно да задржите сортиран, па можда то није брига, али бинарни претрагу такође преузела да сте имали насумичну приступ листи бројева, и низ омогућава вам да имате случајан приступ, као и случајним приступом, Мислим, ако си дао низ, колико времена то одвести доћи до конзоле 0? Једна операција, само користите [0], а ти си тамо. Колико корака је потребно да стигнете до локације 10? Један корак, само идите на [10] и да си тамо. Насупрот томе, како се долази до 10. цео у повезаној листи? Морате почети на почетку јер ви само сећајући почетак повезану листу, баш као стринг се памти по адресу свог првог цхар и да нађемо тај 10. Инт или да 10. карактер у низу, морате да претражите целу проклету ствар. 

Опет, ми не решава све наше проблеме. Ми смо увођењем нових, али то заиста зависи од тога шта ви покушавате да дизајнира за. У погледу спровођења овог, можемо позајмити идеју од тог студентског структуре. Синтакса је веома слична, само што је сада, идеја је мало апстрактно од куће и име и ИД. Али ја предлажем да имамо структуру података у Ц која се зове чвор, као последња реч на слајду сугерише, унутар чвора и чвора је само генерички контејнер у рачунарству. Обично се извући као круг или квадрат или правоугаоник као што смо урадили. И у овој структури података, имамо инт, н, тако да је то број који желите да сачувате. Али, шта је ово друга линија, струцт ноде * следећи? Зашто је то тачно, или шта је улога ово игра, иако је мало криптичан на први поглед? Да. [Нечујан ученик одговор] Тачно тако * врста плена да је показивач неке врсте. Име овог показивача је самовољно следећа, али могли смо га звали шта хоћемо, али шта то показивач указују? [Студентски] Други чвор >> Тачно, то. Указује на другу таквом чвору. 

Дакле, ово је нека врста знатижеље Ц. Подсетимо да је Ц чита компајлер врха до дна, с лева на десно, што значи да ако-ово је мало другачији од онога што смо урадили са учеником. Када смо дефинисали студента, ми заправо није ставио ту реч. То је управо рекао типедеф. Онда смо имали инт ид, стринг име, стринг кућу, и онда студент на дну струцт. Ова изјава је мало другачија јер, опет, Ц компајлер је мало глупо. То је само ћу да прочитам од врха ка дну, па ако стигне овде 2. линију где поред проглашен и види, ох, ево променљива зове следећи. То је показивач на структуру струцт чвор. Компајлер ће схватити шта је струцт ноде? Никад нисам чуо за ове ствари пре, јер реч чвор не би другачије појавити до дна, тако да је ово редундантност. Мораш овде да кажем чвор струцт, које затим могу да скрате касније захваљујући типедеф овде, али то је зато смо референцирање саму структуру унутар структуре. То је једна готцха тамо. 

Неки интересантни проблеми ће настати. Имамо списак бројева. Како да убаците у њега? Како да га тражи? Како ћемо избрисати из ње? Посебно сада када морамо да управљају свим овим показивача. Мислили сте да су показивачи врсте ума савијања када сте имали један од њих само покушава да прочитате Инт на њега. Сада морамо да манипулишу вреди читаву листу о. Зашто не узмемо овде 5-минутни одмор, и онда ћемо донети неки људи на бину да уради управо то. 

Ц је много забавније када је поступила. Ко би желео да буквално буде први? Ок, хајде горе. Ти си први. Ко би желео да буде 9? Ок, 9. Шта кажеш 9? 17? Мало клике овде. 22 и 26 у том првом реду. И како онда о некоме тамо се истакао у. Ти си 34. Ок, 34, дођи горе. Прво је тамо. Ок, све четири од вас. А ко смо рекли за 9? Ко је наш 9? Ко заиста жели да буде 9? Добро, хајде, буди 9. Идемо. 34, ми ћемо вас срести тамо. Први део је направити и сами изгледају тако. 26, 22, 17, добро. Ако можете стајати са стране, јер ћемо вас маллоц у тренутку. 

Добро, добро. Ок, одлично, па хајде да поставим овде пар питања. И заправо, како се зовеш >> Анита. Анита, у реду, хајде овамо. Анита ће да нам помогне да некако реши једна прилично једноставно питање, прво, што је како наћи да ли или не вредност на листи? Сада, приметите да је први, представљен овде Луцас, је мало другачија, па је његов комад папира је намерно бочно јер то није толико висок, а не заузима толико бита, иако технички има исту величину папира само ротирају. Али он је мало другачији по томе што је само 32 бита за показивачем, и све од ових момака су 64 бита, од чега је половина броја, од чега је половина показивач. Али показивач није приказан, тако да ако ви могли нешто неспретно користите леву руку да укаже на особу поред себе. А ти си број 34. Које је твоје име? Ари. Ари, па заправо, држи папир у десну руку, а лева рука иде равно доле. Ви представљате нула са леве стране. 

Сада је наш људски слика је веома конзистентан. Ово је заправо колико показивачи раде. И ако можете да повити мало овако па нисам на путу. Анита овде, ми пронашли број 22, али претпостављају ограничења да није човек држи до комада папира, али ово је списак, а ви само треба да почне са Луцас јер је буквално прва показивач. Претпоставимо да сте сами сте показивач, па ви имате могућност да укаже на нешто. Зашто не почнеш указујући на шта Лукас указује на? Добро, и дозволите ми донесе ово овде. Само ради дискусије, дозволите ми да попните овде празну страницу. Како пише своје име >> Анита. Ок, Анита. Рецимо чвор * Анита = Лукаса. Па, не треба звати Луцас. Требало би да вас зову на првом месту. Зашто је то, у ствари, у складу са реалношћу овде? Један, први већ постоји. Прво је вероватно издвојено негде овде. Чвор * први, а то је било некако додељена листу. Ја не знам како се то десило. То се десило пре него што је почео класа. Ова повезана листа људи је направљен. И сада у овом тренутку прича све ово дешава на Фејсбуку очигледно касније- у овом тренутку у причи, Анита је иницијализован да буде једнака први, што не значи да Анита указује на Лукаса. Уместо тога, она указује на оно што је он указује на јер иста адреса која је унутар Луцас је 32 бита - 1, 2, 3 - сада је унутар Анита је 32 бита - 1, 2, 3. 

Сада је 22. Како би идете о радиш ово? Шта је то? >> Поинт то вхатевер. Покажите шта год, па само напред и делују га најбоље што могу. Добро, добро, а сада сте окренути-Како се зовеш са 22? Рамон. >> Рамон, па Рамон држи до 22. Сада сте урадили проверу. Да ли Рамон == 22, и ако је тако, на пример, можемо вратити истина. Пусти ме-док ови момци стоје овде помало неспретно- пусти ме да урадим нешто брже као Боол наћи. Идем да иде напред и рећи (чвор * листа, инт н). Ја ћу се вратити са вама. Морам да напишем нешто кода. А сада ћу да наставим и радити ово, чвор * Анита = листу. И ја ћу да наставим и рећи док (Анита = НУЛЛ!). 

Метафора овде постаје мало развучен, али док (Анита = НУЛЛ!), Шта желим да урадим? Треба неки начин референцирања цео број који Анита је показујући на. У прошлости, када смо имали структуре, који чвор је, користили смо дот нотацију, а ми би рекли нешто као анита.н, али овде је проблем што Анита није струцт по себи. Шта је она? Она је показивач, па стварно, ако желимо да користимо ову дот-нотацију и то ће да изгледа намерно мало гробни- морамо да урадимо нешто као прелазак на левој руци шта год Анита је показујући на и онда се поље зове н. Анита је показивач, али оно што је * анита? Шта вам је када одете на оно што је Анита показујући на? Струцт, чвор, и чвор, опозив, има поље под називом н јер је, подсетимо, ова 2 поља, следећи и Н, које смо видели пре тренутак овде. 

Да заиста имитирају ово коду, можемо урадити и рећи ако је ((* анита). н == н) н да тражим. Приметимо да је функција донет у броју ми је стало. Онда ја могу ићи напред и радити нешто слично повратку прави. Иначе, ако то није случај, шта желим да урадим? Како превести на кодирају шта Анита учинио интуитивно шетњом кроз листи? Шта треба да урадим овде да симулира Анита предузимање тог корака лево, тај корак са леве стране? [Нечујан ученик одговор] >> Шта је то? [Нечујан ученик одговор] Добро, није лоша идеја, али у прошлости, када смо то урадили, урадили смо анита + + јер би додали број 1 на Анити, што би обично указују на следећу особу, као Рамон, или лице поред њега, или поред њега лице низ линију. Али то није сасвим добро овде, јер шта је ова ствар изгледа у меморији? Није то. Морамо да онемогућите то. То изгледа овако у меморији, и иако сам извући 1 и 2 и 3 близу једна другој, ако смо заиста симулира ти ово-цан момци, док је још указујући на истим људима, се неки од вас узети случајни корак назад, неки од вас напред случајни корак? 

Овај неред је још увек повезана листа, али ови момци могу бити било где у меморији, па анита + + неће радити зашто? Шта је на локацији анита + +? Ко зна. То је нека друга вредност која само тако се дешава да се истурили између свих ових чворова случајно, јер ми не користимо низ. Ми додељена сваком од ових чворова појединачно. Ок, ако ви можете сами очистити назад. Дозволите ми предлажемо да уместо анита + +, ми смо уместо радимо Анита добија- Па, зашто не одемо на било Анита указује на и онда следећи. Другим речима, ми идемо да Рамон, који је држи на број 22, а онда следећи је као да ће се Анита копирање леву руку показивач.. Али она не би ишла даље од Рамон, јер смо пронашли 22. Али то би била идеја. Дакле, ово је бог страшно неред. Искрено, нико неће запамтити ову синтаксу, па на срећу, то је заправо мало намерно-ох, ви нисте уствари видели шта сам написао. То би било више убедљив ако можеш. Воила! 

Иза сцене, ја сам решавању проблема на овај начин. Анита, да тај корак са леве стране, Прво, ми идемо на адресу коју је Анита показујући на и где ће наћи не само н, коју смо управо проверава Поређења ради, али ћете такође наћи следећи - у овом случају, Рамон је лева рука указује на следећи чвор у листи. Али ово је бог-страшно неред на које сам поменуо, али испоставило Ц омогућава нам поједностави ово. Уместо писања (* анита), ми смо уместо да само пишите Анита-> н, и то је тачно исто функционално, али је много више интуитивно, и то је много више у складу са сликом коју смо цртеж Све ово време користи стреле. 

На крају, шта је то што треба да урадимо на крају овог програма? Постоји једна линија преосталог кода. Повратак шта? Нетачно, јер ако смо се кроз целу вхиле петље и Анита је, у ствари, нулл, то значи да је она отишла скроз до краја листе где је показујући на-шта зовеш? Ари >> Ари је. Лева рука, која је нулл. Анита је сада нула, и схватам да само стојимо овде неспретно у лимбу јер Идем на монолог овде, али ћемо вас укључити поново само тренутак. Анита је нула у том тренутку у причи, тако да док се петља завршава, и морамо се вратити фалсе, јер ако је она добила, све до нулте поинтер Ари је тада није било број који је тражио на листи. Можемо очисти ово превише, али то је онда прилично добар имплементација од Траверсал функције, наћи функцију повезану листу. То је још увек линеарно претраживање, али то није тако једноставно као + + показивач или + + и променљива, јер сада не можемо погодити где сваки од ових чворова су у меморији. Морамо да буквално прате траг презлом или, тачније, показивачи, да се са једног чвора на други. 

Сада хајде да пробамо још један. Анита, да ли желе да се врате овде? Зашто не можемо ићи напред и издвоје једну особу из публике? Маллоц-Како се зовеш >> Ребека. Ребека. Ребека је маллоцед из публике, и она сада складиштење број 55. А циљ на дохват руке сада је за Анита да убаците Ребецца у повезану листу овде у свом одговарајућем месту. Дођи овамо на тренутак. Урадио сам нешто овако. Урадио сам чвор *. А шта ти је име? Ребека. >> Ребека, ок. Ребека добија маллоц (сизеоф (чвор)). Као што смо издвојили ствари као што су студенти и ситница у прошлости, морамо величину чвора, тако да сада Ребецца указује на шта? Ребека има два поља унутар ње, од којих је 55. Хајде да урадимо оно, Ребека-> = 55. Али онда Ребецца-> нект треба налик сада, њена рука је некако ко зна? То показује у неком смећа вредности, па зашто не и за добру меру ми смо барем урадите тако да лева рука је сада на њеној страни. Сада Анита, преузети одавде. Имате Ребека пошто је додељен. Иди напред и наћи где треба ставити Ребеку. Добро, веома добро. Ок, добро, а сада морамо да се обезбеди мало правцу, тако сте достигли Ари. Његова лева рука је ништаван, али Ребека јасно припада десно, па како то морамо да мењају овај повезана листу како да убаците Ребеку у одговарајућем месту? Ако буквално могао да се померим лево руке људи око себе као потребно, ћемо решити проблем који начин. Ок, добро, а у међувремену, Ребека је лева рука је сада поред ње. 

То је било превише лако. Хајде да покушамо додељивања-Ми скоро завршен, 20. Ок, хајде горе. 20 је додељено, па ћу ићи напред и рећи поново овде Управо смо урадили чвор * Саад. Имамо маллоц (сизеоф (чвор)). Ми онда исту синтаксу као тачан смо урадили раније за 20, и ја ћу учинити следећи = нулл, а сада је на Анити да убаците у повезаној листи, ако би могао да играм ту потпуно исту улогу. Екецуте. Добро, добро. Сада размислите пре него што почнете креће лево руке. Ти далеко добио већину непријатна улогу данас. Коме треба прво преселио? Ок, чекај, ја чујем неке не-а. Ако неки људи би желели учтиво да помогне у решавању овде незгодну ситуацију. Чији лева рука треба да буде ажуриран прво можда? Да. [Студентски] Саад је. Ок, саад је, зашто, иако? [Нечујан ученик одговор] Добро, јер ако идемо-Како се зовеш >> Маршал. Маршал, ако померите руку прво до нулл, Сада смо буквално сироче четворо људи у овој листи јер је он био једина ствар показујући на Рамон и свима са леве стране, па ажурирање прво да показивач био лош. Идемо ундо то. Добро, а сад иди и помери леву руку одговарајући показивач на Рамон. То се осећа мало сувишан. Сада постоје две особе уперене Рамон, али то је у реду јер сада како другачије да смо ажурирали листу? Која је друга рука има да се крећу? Одлично, сада имамо изгубио памћење? Не, па добро, хајде да видимо, ако не можемо прекинути ово још једном. 

Маллоцинг последњи пут, број 5. Све начин у леђа, хајде доле. То је веома узбудљиво. [Аплауз] Које је твоје име >> Рон. Рон, у реду, ви маллоцед као број 5. Управо смо погубили код који је готово идентичан ово са само другим именом. Одлично. Сада, Анита, срећно убацивање број 5 на листи сада. Добро, и? Одлично, тако да је ово заиста трећа од три укупног броја случајева. Прво смо имали некога на крају, Ребека. Ми смо тада имали некога у средини. Сада имамо некога на почетку, у овом примеру, сада морали да ажурирате Лукаса први пут јер први елемент у листи сада има да укаже на новом чвору, која, опет, указује на број чвора 9. 

Ово је изузетно непријатно демонстрација, сигуран сам, тако велики аплауз за ове момке ако можеш. Лепо урађено. То је све. Можете задржати своје папире као мало меморије. Испоставило се да радиш у шифрама није баш тако једноставно као само кретање руке око и указивање на показиваче различите ствари. Али схватају да када је у питању време да спроведе нешто слично повезана листа или варијанта тога ако се усредсредите на стварно ове основне фундаменталне залогаја величине проблеми морам да схватим, да ли је ово рука или ово рука, схватите да оно што је иначе прилично сложен програм може, у ствари, бити сведен на релативно једноставне градивних блокова као што је ова. 

Узмимо ствари у софистициранијим правцу даље. Ми сада имамо појам повезану листу. Такође смо-захваљујући предлогу тамо-двоструко повезане листе, која изгледа скоро исто, али сада имамо две тројке унутар струцт уместо једног, а ми смо вероватно могли назвати оне показивачи претходни и следећи или лево или десно, али ми, у ствари, потребно двоје од њих. Код ће бити мало више укључени. Анита би морали да раде више овде на сцени. Али ми свакако може имплементирати такву структуру. У погледу вођења време, ипак, шта би било време рада за Аниту за проналажење броја н у повезаној листи сада? Ипак велики О н, тако да је бољи од линеарног претрагу. Ми не можемо бинарну претрагу, међутим, поново. Зашто је то тако? Ви не можете около скочи. Иако смо очигледно виде све људе на сцени, и Анита могао да еиебаллед и рекао: "Ево је средњи листе" она не би знао да ако је она компјутерски програм јер једино она је морала да се ухвате на на почетку сценарија био је Лукас, који је био први поентер. Она нужно морати да прати те везе, рачунајући свој пут док није нашао отприлике на средини, па чак и тада, она неће да зна када је она достигла средину осим ако она оде скроз до краја да схватим колико има, тада повлачи, и да превише би било тешко уколико сте имали двоструко повезана листа неке врсте. 

Решавање неких проблема данас, али увођење друге. Шта други структуру података укупно? Ово је фотографија од носача у Матхер Хоусе, и у овом случају, имамо структуру података и ми смо некако већ говори о томе. Разговарали смо о стека у контексту меморије, и то је нека врста намерно названа јер стек у погледу меморије је ефикасно структура података који има све више и више ствари слојевитим на врху. Али занимљива ствар у вези гомиле, као што је то случај у стварности, је да је посебна врста структуре података. То је структура података којом први елемент у је последњи елемент напоље. Ако сте први носач да се стави на стек, ћеш нажалост бити последњи послужавник да се скине штос а то није нужно добра ствар. Насупрот томе, можете да размислите о томе около други начин, последњи у је први напоље. 

Дакле, да ли сценарији долазе на памет, где има гомилу Структура података где имате ту имовину за последњи у, првом излаз, заправо убедљив? Да ли је то добра ствар? Да ли је то лоше? То је дефинитивно лоше ако нису тацне идентична и сви они су посебни различите боје или ситница, а боја коју желите скроз на дну. Наравно, не можете да добијете да без великог напора. Морате почети од врха и раде свој пут доле. Слично томе, шта ако сте били један од тих навијачких дечака ко чека целу ноћ покушавајући да добије иПхоне и линије уп на оваквом месту? Зар не би било лепо када би Аппле Сторе били стек података структура? Иаи? Наи? То је само добро за људе који се појаве у последњем могућем тренутку и онда се извукао ван редоследа. А у ствари, чињеница да сам био толико склон да кажем ред је заправо у складу са оним што бисмо ми назвали ова врста структуре података, један у стварности, где поредак битно, и желите да први у да буде први од ако је само због људске правичности. Ми генерално ћемо назвати куеуе структура података. 

Испоставило се, поред повезаним листама, можемо да почнете да користите исте основне идеје и почети стварање нове и различите врсте решења за проблеме. На пример, у случају гомиле, можемо представљати гомилу користећи структуру података овако, ја бих предлажемо. У том случају, ја сам проглашен за струцт, а ја сам рекао унутар ове структуре је низ бројева и онда променљива зове величина, и ја ћу да позовем ова ствар гомилу. Е сад, зашто се то заправо ради? У случају стека, могао сам да цртам ефикасно на екрану као низа. Овде је мој стек. То су моји бројеви. И ми ћемо их извући као ово, ово, ово, ово, ово. А онда сам овде имам неке друге податке члана, који се зове величина, тако да је ово величина, и то је број, и колективно, цела иПад овде представља једну стека структуру. Сада, по дефаулту, величина вероватно мора да се иницијализује на 0, и шта је унутра низа бројева иницијално када сам први пут доделити низ? Смеће. Ко зна? И то заправо не битно. Није битно да ли је то 1, 2, 3, 4, 5, потпуно насумично од лоше среће се налазе у мојој структури, јер докле год знам да је величина стека је 0, онда програмски знам, не гледај на неки од елемената у низу. Није битно шта је тамо. Не гледај у њих, као што би био импликација величине од 0. 

Али претпоставимо сада ићи напред и убаците нешто у стеку. Желим да убаците број 5, па сам ставио овде број 5, и онда шта сам ставио овде? Сада сам стварно бих спустио 1 по величини, и сада стек величине 1. Шта ако сам напред и ставите број, рецимо, 7 следећи? То онда добија ажуриран 2, а онда ћемо до 9, а онда добија ажурирани 3. Али занимљива карактеристика сад овог стека је да Ја треба да уклони елемент који, ако желим да поп нешто искључивање стеку, да се тако изразим? 9 ће бити прва ствар коју треба да идем. Како би се слика промени ако желим да се појави елемент ван стек, волео послужавник у Матхер? Да >> [Студентски] Подешавање величине до 2.. Тачно, све што урадите је да поставите величину до 2, и шта да радим са низом? Не морам ништа да радим. Сам могао, само да би анални, ставите 0 постоји или -1 или тако нешто, да означи да ово није легит вредност, али то није битно, јер Ја могу снимати изван самог низа колико је она тако да ја знам само осврнемо на прва два елемента у овом низу. Сада, ако одем и додајте број 8 на овај низ, како се слика промени следеце? Ово постаје 8, и то постаје 3. Ја сам овде сечење неколико углова. Сада имамо 5, 7, 8, и ми смо се вратили на величину од 3. То је прилично једноставан за примену, али када ћемо зажалити ову одлуку дизајн? Када се ствари почну да иду врло, врло погрешно? Да. [Нечујан ученик одговор] Када желите да се вратите и да први елемент сте ставили унутра 

Испоставило се овде, иако стек низ испод хаубе, ови подаци структуре смо почели да разговарамо о су опште познати као апстрактне структуре података чиме како они спроводе потпуно је поред тачке. Структура података као стек треба да дода подршку операције као што притиском, што гура послужавник на стек, и поп, који уклања елемент са стека, и то је то. Ако сте били да преузмете туђи код који већ имплементиран ово се зове стек, та особа би написали само два функције за вас гура и поп, чија је једина сврха у животу би да урадите управо то. Ти или он, или она која спроводи тај програм би био у потпуности један да одлучи како да се примени семантике гурања и кокичара испод хаубе или функционалност гура и кокичавости. И ја сам овде направио нешто кратковид одлуку спроводећи своју штос са овом једноставном структуру података зашто? Када се ове податке структуру паузу? У ком тренутку морам вратити грешку када корисник позива Пусх, на пример? [Студентски] Ако нема више простора. Тачно, ако нема више простора, ако сам премашио капацитет, што је све капе, јер сугерише да је то нека врста глобалне константе. Па, онда ћу само морати да кажу: "Жао ми је, не могу да гурне друго вредност на стеку, "много као у Матхер. 

У неком тренутку, они ће да удари горњи део тог малог кабинета. Нема више простора или капацитета у стеку, након чега постоји нека врста грешке. Они морају да стави елемент негде другде, касета негде другде, или нигде уопште. Сада, са ред, можемо га имплементирати мало другачије. Редослед је мало другачији по томе што испод хаубе, она може да се имплементира као низ, али зашто, у овом случају, ја предлагање да имају елемент подизања представља главу на листи, предњи део листе, прва особа у реду на Аппле продавници, поред величине? Зашто ми треба додатни податак? Сетите се шта је бројева ако сам извући на следећи начин. Претпоставимо да је ово сада перчин уместо стека, разлика бити-баш као Аппле сторе-ред је фер. Прва особа у реду на почетку листе, број 5, у овом случају, он или она ће бити пусти у продавници прво. Хајде да то урадимо. Претпоставимо да је ово стање мог ред у овом тренутку у времену, а сада Аппле продавница отвара и прва особа, број 5, је водио у продавницу. Како да промените слику сада сам одјављене чекању прву особу на предњој линији? Шта је то >> [Студентски] Промените редослед. Промените главу, па 5 нестаје. У стварности, то је као да-како најбоље да се то уради? У стварности, то је као да је овај момак нестаје. Шта би број 7 учинити у стварном продавници? Они би унапред предузети велики корак. 

Али оно што смо дошли да ценимо, када је у питању низови и премештање ствари около? То је нека врста отпада ваше време, зар не? Зашто мораш да будеш тако аналног да имамо прву особу на почетку линије на физички почетку комад меморије? То је потпуно непотребно. Зашто? Шта сам могао да се сетим само уместо >> [нечујан ученик одговор?] Тачно, само сам могао да се сетим са овим додатним подацима чланица главе да је сада на челу листе је више 0, која је пре тренутак. Сада је заправо број 1. На овај начин, ја се мало оптимизацију. Само зато што сам одјављене чекању некога из линије на почетку линије на Аппле продавници не значи да сви треба да се мењају, што је присећање линеарна операција. Ја уместо да само троше време константан и постићи онда много бржи одговор. Али цена коју плацам је оно да се добије тај додатни рад и не морају да пребаце све? Да >> [нечујан ученик одговор]. Могу да додају још људи, па то је проблем ортогонална на чињеницу да нисмо Правац људе около. То је и даље низ, тако да без обзира да ли смо или нисмо пребаце свима или не- Ох, видим шта мислите, у реду. Заправо, ја се слажем са оним што ви кажете да је у готово као да ми смо сада никада неће више користити почетак овог низа јер ако сам уклони 5, онда уклоните 7. Али ја само ставити људе са десне стране. 

То се осећа као да губим простор, и на крају ми је перчин распадне у ништа, тако да смо само могли да имамо људе обвојно, и могли бисмо да размишљамо о овом низу заиста као нека врста кружног објекта, али ми користимо шта оператор у Ц да такве обвојно? [Нечујан ученик одговор] >> модулу оператер. Било би мало досадно да се размисли како да урадите обвојно, али смо могли да радимо, и ми могли почети стављање људи на оно што је некада била испред линије, али ми се сетим са овом главом променљиве који стварни шеф линије заправо јесте. Шта ако, уместо тога, на крају наш циљ, међутим, био је да потражите бројеве, као што смо овде урадили на позорници са Анита, али ми заиста желимо најбоље од свих тих светова? Желимо више софистицираности него низ омогућава јер желимо могућност да динамички расте података структуру. Али ми не желимо да морају да прибегну нешто што смо истакли У првом предавању није била оптимална алгоритам, да од линеарне претраге. Испада да сте, у ствари, постигне или барем близу сталном времену, при чему неко као Анита, ако она подешава своју структуру података не буде повезана листа, да не буде скуп, да не буде ред чекања, може се, у ствари, дошао до података структуру која омогућава јој да изгледа горе ствари, чак и речи, а не само бројеве, у шта ћемо звати константно време. 

И у ствари, гледајући напред, један од псетс у овој класи је готово увек имплементација Правопис, при чему ми смо вам дати опет неке 150.000 речи енглеског језика и циљ је да се учитати у меморију и они брзо бити у стању да одговори на питања о форми се ова реч правилно написан? И стварно би сиса, ако сте морали да вршите итерацију кроз све 150.000 речи да одговорим. Али, у ствари, видећемо да то радимо у веома, веома брзо време. И то ће укључити спроводи нешто што се зове хеш табели, и иако на први поглед ово се зове хеш табела ће се нека нам постигли ови супер брзи одзив, Испоставило се да је у ствари проблем. Када дође време да се спроведе ову ствар зове-опет, ја то радим поново. Ја сам једини овде. Када је у питању време да примени ову ствар зове хеш табела, ћемо морати да донесе одлуку. Колико велике би ова ствар заправо бити? А када смо започели убацивањем бројеве у овој хеш табели, како ћемо их чувати на такав начин да можемо да их вратимо се тако брзо као што их је добио у? Али видећемо убрзо да се ово питање када је свачији рођендан је у класи ће бити сасвим германе. Испада да у овој просторији, имамо неколико стотина људи, па су шансе да нас двоје имамо исти рођендан је вероватно прилично висока. Шта ако је било само 40 од нас у овој соби? Какве су шансе да двоје људи имају исти рођендан? [Студенти] Преко 50%. Да, преко 50%. У ствари, чак сам донео графикон. Испоставило се и да је ово заиста само снеак превиев- ако има само 58 од нас у овој соби, вероватноћа од 2 нас имају исти рођендан је изузетно висока, скоро 100%, и да ће изазвати гомилу повредио за нас у среду. 

Уз то је рекао, хајде да завршимо овде. Видимо се у среду. [Аплауз] [ЦС50.ТВ]