[Powered by Google Translate] [Одељак 6: Мање Удобно]
[Нејт Хардисон] [Универзитет Харвард]
[Ово је ЦС50.] [ЦС50.ТВ]
У реду. Добродошли у члану 6.
Ове недеље, ми ћемо да причамо о структурама података у одељку,
пре свега зато што овонедељна проблем подесити на спеллр
не гомила различитих структура података истраживања.
Постоји гомила различитих начина на које можете отићи са проблемом сету,
и више структуре података да о томе знам, више кул ствари које можете да урадите.
>> Дакле, хајде да почнемо. Прво ћемо да разговарамо о димњацима,
стека и перчин структуре података да ћемо да разговарамо о томе.
Димњаци и редови су заиста корисно када почнем да причам о графикона,
што нећемо урадити толико сада.
Али они су стварно добро разуме један од великих основних података структурама ЦС.
Опис у спецификацији проблема сет,
ако га повуци се, говори о димњацима као сродан
хрпу ручавање касета које имате у кафетерији на трпезаријама
где, када је трпезарија особље долази и ставља трпезарије лежишта након што сам их очисти,
су им стек један на врху друге.
И онда када деца дођу у добити храну,
они вуку посуде, прво да је на првом месту, онда онај испод њега, онда онај испод тога.
Тако, у ствари, први носач да трпезарија особље спустио је последњи који добија скинут.
Последња је да је трпезарија особље стави на први онај који буде скинут за вечеру.
У спец је проблем сету а, који можете преузети ако већ нисте,
говоримо о моделовању гомилу података стуцтуре користећи ову врсту струцт.
>> Дакле, оно што смо овде, ово је слично ономе што је представљен у предавању,
осим у предавању представили смо ово са Интс насупрот цхар с *.
Ово ће бити стек који складишти шта?
Данијел? Шта смо складиштење у стеку?
[Данијел] жице? >> Смо складиштење конце у овом стеку, тачно.
Све што треба да имате у циљу стварања стек је низ
одређеног капацитета, што у овом случају,
Капацитет ће бити у свим капе, јер је константа.
А онда поред низа, све што треба да пратите је актуелна величина низа.
Једна ствар коју треба напоменути да је кул
јесте да смо креирање наслагани структуру података на врху другог података структуре, низа.
Постоје различити начини да се спроведе штекова.
Нећемо то урадити још доста, али надамо се после радећи повезане листе проблема,
ћете видети како можете лако имплементирати стек на врху листе, као и повезана.
Али за сада, ми ћемо држати на низове.
Па опет, све што је потребно је низ а ми само треба да пратите величину низа.
[Сам] Извините, зашто је то што је рекао да стек је на врху жице?
За мене је то изгледа као да су жице су у стеку.
[Хардисон] Да. Ми правите, водимо наш података низа структура -
То је велико питање. Дакле, питање је зашто, за људе који гледају овај онлине,
Зато смо рекавши да је стек на врху жице,
јер овде изгледа као да су жице су у стеку?
Који је потпуно случај.
Оно што сам мислио да је то што смо добили низ података структуру.
Имамо низ цхар * с, овај низ стрингова,
а ми ћемо додати да је у циљу стварања наслагани структуру података.
>> Дакле, стек је нешто сложенији него низа.
Можемо користити низ да се изгради гомилу.
Дакле, то је где смо рекли да је стек је изграђен на врху низа.
Исто тако, као што сам раније рекао, можемо изградити стек на врху повезане листе.
Уместо помоћу низа да држимо елементе,
можемо користити повезану листу да држимо елементе и граде штос око тога.
Прошетајмо кроз неколико примера, гледајући неки код,
да видимо шта се заправо догађа овде.
Са леве стране, ја сам бачена шта то стек струцт ће изгледати у меморији
ако су капацитети # дефинисана тако да буде четири.
Имамо нашу четири елемента цхар * низ.
Имамо жице [0], гудачи [1], гудачи [2], стрингс [3]
а онда последњи простор за наше величине цео број.
Да ли ово смисла? Ок.
То је оно што се дешава ако је оно што ја радим са десне стране,
који ће бити мој број, да једноставно прогласи струцт, наслагане струцт зове с.
То је оно што смо добили. Она прописује овај отисак у меморији.
Прво питање је шта су садржај овог стек струцт?
Сада су они ништа, али нису потпуно ништа.
Они су ова врста смећа. Немамо појма шта је у њима.
Када смо прогласити с стек, само смо бацали то доле на врху меморије.
То је нешто као проглашења инт и не иницијализацију.
Ви не знате шта је унутра. Можете прочитати шта је унутра,
али то не може бити супер корисно.
Једна ствар коју желите да се увек сетите да урадите је да покрене све што треба да се иницијализује.
У овом случају, ми ћемо да покрене величину буде нула,
јер ће испасти да буде веома важна за нас.
Могли смо да идемо напред и иницијализовати све показивача, све цхар * с,
да буде нека разумљива вредност, вероватно нулл.
Али то није сасвим неопходно да то учинимо.
>> Сада, две главне операције на полицама су?
Свако сећам из предавања шта радиш са гомиле? Да?
[Стелла] Гурање и кокичара? >> Тачно.
Гурање и кокичара су две главне операције на димњацима.
А шта Пусх ради? >> Она ставља нешто на врху
на стек, а затим га кокичара скида.
[Хардисон] Управо тако. Дакле гура гура нешто на врху стека.
То је као трпезаријом особља стављају трпезаријски послужавник доле на шалтеру.
И кокичара узима трпезаријски послужавник искључивање стека.
Прошетајмо кроз неколико примера шта се дешава
кад гурамо ствари у стеку.
Ако смо били гурнути низ 'здраво' на нашем стек,
То је оно што наш дијаграм би изгледао као сада.
Видите шта се дешава?
Ми смо гурнути у први елемент нашег низа гудаче
и ми смо подигли нашу величину рачунати да је 1.
Дакле, ако погледамо разлику између два слајда, овде је 0, ево пред притиском.
Овде је након притиском.
Пре притиском, након притиском.
И сада имамо један елемент у нашој стек.
То је стринг "здраво", и то је то.
Све друго у низу, у нашем низу гудаче, још увек је смеће.
Нисмо га иницијализована.
Рецимо да гурне друго жицу на нашем стека.
Идемо да гура "свет" на овом времену.
Дакле, можете видети "свет" овде иде на врху "здраво",
и величине бројање иде до 2.
Сада можемо гурнути "ЦС50", и да ће ићи на врху поново.
Ако се вратимо, можете видети колико смо гура ствари на врху стека.
И сада долазимо до поп.
Када смо убацио нешто искључивање стеку, шта се десило?
Свако види разлику? То је прилично суптилне.
[Студентски] величине. >> Да, величина промењена.
>> Шта друго би сте очекује да се промени?
[Студентски] Жице, превише. >> Реду. Жице превише.
Испада да када сте то радили на овај начин,
јер ми не копира елементе у нашој стек,
ми заправо не морате ништа да радите, ми само можемо користити величину
да пратите броја ствари у нашем низу
тако да када се поново појавити, опет смо само умањити нашу величину до 1.
Нема потребе да се заиста тамо и заменити ништа.
Некако функи.
Испоставило се да смо управо обично остави ствари на миру, јер је то мање посла за нас да урадимо.
Ако ми не треба да се вратимо и да препишете нешто, онда зашто то радиш?
Дакле, када смо два пута појавити искључивање стека, све што ради је умањење од величине неколико пута.
И опет, то је само зато што не копира ствари у нашој стека.
Да? Само напред.
[Студент, неразумљив] >> И шта се онда дешава када притиснете нешто опет?
Када притиснете нешто опет, где то иде?
Где то иде, Басиле? >> У стрингс [1]? >> Реду.
Зашто не иде у жицама [3]
[Василије] Јер је заборавио да је било нешто у жицама [1] и [2]?
[Хардисон] Управо тако. Наш скуп, у суштини, "заборавио" да је држи на шта
у стрингс [1] или ниске [2], па кад гурамо "воот",
само ставља да је у елементу на стрингове [1].
Да ли постоје питања о томе како ради, на основном нивоу?
[Сам] Дакле, ово није динамична на било који начин, у смислу износа
или у погледу величине стека?
[Хардисон] Управо тако. То је - поента је да ово није динамички гајилиште стек.
Ово је стек који може држати у већини, четири цхар * с, највише четири ствари.
Ако смо били да покушамо да гура пету ствар, шта мислите да би се десило?
[Студенти, неразумљив]
[Хардисон] Управо тако. Постоји неколико ствари које би могле догодити.
То можда може да сегментира грешку, у зависности од тога шта смо били -
како тачно смо реализацију бацк-енд.
То би могло заменити. То би могло имати ту преливање бафера које смо причали на часу.
Шта би било да је најочигледнији ствар која може бити замењена
ако смо покушали да помере екстра ствар на нашој стека?
Дакле, поменули сте бафера.
Шта може бити ствар која ће бити написано изнад или газио по
ако случајно преплавило покушавајући да гурне екстра ствар?
[Данијел, неразумљив] >> Могуће.
Али прво, шта може да се деси? Шта ако смо покушали да помере и четврту ствар?
То би могло да препишете величину, бар са овим меморијским дијаграму који смо добили.
>> У спецификацији проблема сет, што је оно што ћемо спроводити данас,
оно што ми желимо да урадимо је вратио само лажна.
Наш метод притисак ће вратити боолеан вредност,
и да боолеан вредност ће бити тачно уколико Пусх суццеедс
а фалсе ако не можемо гурати ништа више, јер стек пун.
Прошетајмо кроз мало тог кода сада.
Ево наша функција пусх.
Наша функција притиском на стек ће узети у низу да стави на стек.
То ће вратити труе ако стринг који је успешно гурнут
на стек и лажне другачије.
Свака сугестија о томе шта би било добро прво да урадим овде?
[Сам] Ако величина износи капацитет онда се врати лажно?
[Хардисон] Бинго. Добар посао.
Ако је величина капацитета, ми ћемо вратити фалсе.
Ми не можемо ставити ништа више у нашој стек.
Иначе, ми желимо да ставимо нешто на врху стека.
Шта је "врх стека", првобитно?
[Данијел] Величина 0? >> Величина 0.
Шта је врх стека након Има једна ствар у стеку? Миси, знаш?
[Мисси] Један. >> Величина је један, тачно. Стално додајући величини,
и сваки пут када се стави у нови елемент у индексној величини у низу.
Можемо то да урадимо са том врстом једном броду, ако то има смисла.
Тако смо добили нашу ниске низ, идемо да му приступите на величину индекса,
а ми ћемо само да сачувате своју цхар * тамо.
Обратите пажњу како нема жица копирање дешава овде,
нема динамичан алокација меморије?
А онда Мисси довео до онога што сада имамо да урадимо,
јер смо сачували стринг на одговарајућем месту у низу,
и она је рекла да смо морали да повећате величину по један, тако да смо спремни за следећи притиском.
Дакле, можемо да урадимо то са с.сизе + +.
У овом тренутку, ми смо гурнути у нашем низу. Шта је последња ствар која нам треба да урадимо?
[Студентски] Повратак истина. >> Повратак истина.
Дакле, то је прилично једноставна, прилично једноставна шифра. Не превише.
Када замотан главу око како стек ради,
ово је прилично једноставан за примену.
>> Сада, следећи део ово искакање низ офф стека.
Ја ћу да ти дам момци мало времена за рад на овом мало.
То је скоро суштини супротно оно што смо урадили овде у пусх.
Оно што сам урадио је заправо - Упс.
Сам боотед сам се један апарат овамо, ау апарата,
Сам извукао сам се проблем поставити 5 спецификацију.
Ако смо увећали овде, можемо видети да сам у цдн.цс50.нет/2012/фалл/псетс/псет5.пдф.
Да ли сте ви преузели овај код који се овде налазе, сецтион6.зип?
У реду. Ако нисте урадили, урадите то сада, веома брзо.
Ја ћу то да урадим у мом прозору терминала.
Ја стварно то урадио овде. Да.
Да, Сем? >> Имам питање о томе зашто сте рекли с.стринг с заградама величине = ул?
Шта је стр? Да ли је то дефинисано негде пре, или - ох, у цхар * Ул?
[Хардисон] Да, баш тако. То је био аргумент. >> О, у реду. Извините.
[Хардисон] Ми смо наводећи низ да гура унутра
Друго питање које би могле доћи до које нисмо заиста говорити о томе овде
ми смо узели здраво за готово да смо имали ову променљиву под називом а
који је био у обиму и приступачан за нас.
Ми узео здраво за готово да је с је ово гомила струцт.
Дакле, гледајући уназад на овај пусх кода,
можете видети да радимо ствари са овим стрингом који је добио донесен
али онда сви одједном смо приступ с.сизе, као, одакле ови долазе?
У коду који ћемо да погледамо у рубрици архиви
и онда су ствари које ћете радити у свом проблему поставља,
Направили смо наш стек струцт глобалну променљиву
тако да можемо имати приступ њему у свим нашим различитим функцијама
без потребе да ручно прође око и проћи га референце,
учинити све да се такве ствари на њега.
Ми само вараш се мало, ако хоћете, да се ствари лепше.
И то је нешто што ми овде радимо, јер је то за забаву, то је лакше.
Често ћете видети људе учинити ако имају једну велику структуру података
а која се оперисао у оквиру свог програма.
>> Идемо назад преко на уређај.
Да ли су сви успешно добили сецтион6.зип?
Сви га распакујте користи унзип сецтион6.зип?
Ако идете на дионици 6 директоријум -
аах, свуда -
и навести шта је овде, видите да имате три различита ц фајлове..
Имаш ред, СЛЛ, која је појединачно повезана са листа, и стек.
Ако отворите стацк.ц,
можете видети да смо добили ову струцт дефинисану за нас,
тачно струцт да смо управо причали о томе у слајдовима.
Имамо нашу глобалну променљиву за стек,
Имамо нашу пусх функцију,
и онда имамо нашу поп функцију.
Ја ћу ставити шифру за гура назад на слајду овде,
али оно што бих ви треба да урадите је да најбоље што могу,
иди и спроведе поп функцију.
Када сте га спроводе, можете компајлирати ово са направи штос
а затим покрените извршну резултанта стека,
као и да ће покренути све ово тест кода овде да је у главни.
А главни брине заправо израде пусх и поп позива
и да се уверите да све иде кроз све у реду.
Он је такође покреће стека величину овде
тако да не морате да бринете о томе да је иницијализација.
Можете претпоставити да је било исправно иницијализована
у време које сте приступити га у поп функцију.
Да ли то смисла?
Дакле, идемо. Ту је гурање код.
Даћу вам момци 5 или 10 минута.
А ако имате било каквих питања у међувремену док сте кодирање,
замолите их наглас.
Дакле, ако дођете до тачке лепљење, само питај.
Дозволите ми да знам, да сви остали знају.
Радите са својим комшијом превише.
[Данијел] Ми само спровођење поп сада? >> Само поп.
Иако можете да копирате спровођење притиском ако желите
тако да Тестирање ће радити.
Зато што је тешко да се тестирају ствари улазим -
или, тешко је тестирати кокичара ствари из гомиле ако не постоји нешто у стеку да почне са.
>> Оно што је требало да буде поп враћају? Елемент са врха стека.
Требало би да добијете елемент искључивање на врху стека
и онда Смањење величине стек,
а сада сте изгубили елемент на врху.
А онда вратите елемент на врху.
[Студент, неразумљив]
[Хардисон] Па шта се дешава ако сте то урадили? [Студент, неразумљив]
Шта завршава се дешава је вероватно имате приступ било
елемент који још није покренут, тако да ваш прорачун
где последњи елемент је искључен.
Па ево, ако сте приметили, у притиском, ми смо приступ конце у с.сизе елемент
јер је нови индекс.
То је нови врх стека.
Док је у поп, с.сизе ће бити следећи простор,
простор који је на врху свих елемената у стеку.
Дакле топ највише елемент није на с.сизе,
већ, то је испод ње.
>> Друга ствар коју треба урадити када - у поп,
је ли то треба да умањење величину.
Ако се сетите да врати нашем малом дијаграм овде,
Заиста, једина ствар коју смо видели дешава када смо звали поп
је да је ово величина пао, прво на 2, затим 1.
Онда када смо гурнули један нови елемент, он ће ићи на на одговарајуће место.
[Василије] Ако с.сизе је 2, онда не би било отићи на елемент 2,
и онда би желео да се појави тај елемент искључен?
Дакле, ако смо отишли ​​до - >> Па хајде да погледамо ово поново.
Ако је ово наш стек у овом тренутку
и зовемо поп,
на којој је индекс топ највише елемент?
[Василије] У 2, али то ће поп 3. >> Реду.
Дакле, то је место где је наша величина је 3, али желимо да поп елемент у индексу 2.
То је то типично врста офф један који имате са нултом индексирања низова.
Дакле, не желите да се појави трећи елемент, али је трећи елемент није у индексу 3.
А разлог што не треба да раде тај минус 1 када смо гурање
је зато сада, приметите да је топ највише елемент
ако смо били гурнути нешто на стек у овом тренутку,
ми смо желели да га гура у индексу 3.
И тако се дешава да управо величина и индекси построје кад гура.
>> Ко има радну стека примену?
Имаш радну стек један. Да ли сте поп раде још?
[Данијел] Да. Мислим да је тако.
>> Програм је покренут и не сегментира Фаултинг, то је штампање?
Да ли то штампати "успех" када га покренем?
Да. Направите стек, покрените га, ако се исписује "успех" и не иде бум,
онда све је добро.
У реду. Идемо преко на уређај заиста брзо,
и ми ћемо проћи кроз ово.
Ако погледамо шта се овде дешава са поп,
Данијел, који је био прва ствар коју сте урадили?
[Данијел] Ако с.сизе је већи од 0.
[Хардисон] Ок. А зашто сте то урадили?
[Данијел] Да бисте се уверили да нешто није у стеку.
[Хардисон] Тачно. Ви желите да тестирате да се уверите да с.сизе је већа од 0;
У супротном, шта желиш да се деси?
[Данијел] Повратак нулл? >> Повратак нулл, тачно.
Дакле, ако с.сизе је већа од 0. Онда, шта ћемо да радимо?
Шта ћемо да радимо ако стек није празан?
[Стелла] Можете умањити величину? Ти >> Смањи величину, ок.
Па како си то урадио? >> С.сизе--.
[Хардисон] Одлично. И онда шта си урадио?
[Стелла] И онда сам рекао повратак с.стринг [с.сизе].
[Хардисон] Одлично.
У супротном, вратите нулл. Да, Сем?
[Сам] Зашто то не треба да буде с.сизе + 1?
[Хардисон] плус 1? >> Да. >> Имам га.
[Сам] Мислио сам зато што узимате 1 аут,
онда ћеш бити не враћа онај који их тражио.
[Хардисон] И то је управо оно што смо причали са целом овом питању 0 индекса.
Дакле, ако смо увећали вратити овамо.
Ако гледамо на овог момка овде, можете видети да када се појављују,
ми кокичара елемент у индексу 2.
>> Тако смо смањили прво нашу величину, онда је наша величина одговара наш индекс.
Ако ми прво не умањити величину, онда морамо да урадимо величину -1 и онда умањење.
Сјајно. Све добро?
Сва питања о овоме?
Постоји неколико различитих начина да се напише ово као добро.
У ствари, можемо да урадимо још нешто - можемо направити једну траку.
Можемо да урадимо један линије повратак.
Дакле, ми заправо можемо умањити пре него што се вратимо на тај тим.
Дакле, стављајући - пре с.сизе.
То чини линија заиста густа.
Где је разлика између - с величином и с.сизе--.
је да је ово постфик - они га зову постфик јер - долази после с.сизе--
значи да с.сизе се оцењује ради проналажења индекса
каква је сада, када је ова линија се извршава,
и онда ово - дешава после линија добија погубљен.
Након елеменат у индексној с.сизе приступа.
А то није оно што ми желимо, јер желимо умањење прво деси.
Отхевисе, идемо да се приступа низ, ефикасно, ван граница.
Ми ћемо се приступа елемент изнад оног који смо заиста желите да приступите.
Да, Сем? >> Да ли је брже или да користите мање РАМ да би у једном реду или не?
[Хардисон] Искрено, стварно зависи.
[Сем, неразумљив] >> Да, то зависи. То можете да урадите трикове компајлера
да компајлеру да призна да је, обично, претпостављам.
>> Тако смо поменули мало о овим стварима преводилац оптимизације
које можете да урадите у састављању,
и то је врста ствари које компајлер ће моћи да схватим,
као ох, хеј, можда ја могу да урадим све ово у једном раду,
насупрот учитавања величине варијаблу из РАМ меморије,
децрементинг га, складиштење назад, а затим га поново утовар поново
да обрадимо остатак ове операције.
Али обично, не, ово није врста ствари
који ће направити свој програм знатно брже.
Има ли још питања о димњацима?
>> Дакле, гурања и кокичавости. Ако ви желите да испробате издање хакера,
шта смо урадили у хакерске издању заправо нема
и направио овај стек расте динамички.
Изазов првенствено има овде у пусх функција,
да схватим како да то низ расте
као чувате гура све више и више елемената на на стеку.
То заправо и није превише додатни код.
Само позив - морате да се сетите да добију позиве за маллоц тамо правилно,
и онда схватим кад ћеш звати реаллоц.
То је забавно изазов ако сте заинтересовани.
>> Али, за сада, идемо даље, и хајде да разговарамо о редовима.
Крећите се овде.
Ред је близу брат стека.
Дакле, у стеку, ствари које су ставили у последњој
су прве ствари онда се преузимају.
Имамо ово последњи у, прво се, или ЛИФО, наручивања.
Док је у реду, као што бисте очекивали од када стојите у реду,
прва особа да се у складу, прва ствар коју треба да уђе у ред,
је прва ствар која добија преузета из реда.
Редови су такође често користи када имамо посла са графиконима,
као да смо разговарали о томе кратко са димњака,
а редови су такође корисна за гомилу других ствари.
Једна ствар која се појављује често покушавају да одрже, на пример,
сортирана листа елемената.
И ви можете да урадите са низом. Можете да одржи сортирани списак ствари у низу,
али где да се добије незгодан је тада увек морате да пронађете
одговарајуће место за уметање следећу ствар.
Дакле, ако имате низ бројева, 1 до 10,
и онда желите да проширите то све бројеве од 1 до 100,
а ви добијате те бројеве случајним редоследом и покушава да задржи све
поредани како идете путем, можете завршити потребе да урадите много мења.
Са одређеним врстама редовима и одређених врста основних структура података,
ви у ствари може да је прилично једноставно.
Не морате да додате нешто, а затим реорганизација цела ствар сваки пут.
Нити морате да урадите много померања унутрашњих елемената у околини.
Када погледамо у реду, видећете да - иу куеуе.ц у делу код -
структуре попунити које смо вам дали је заиста сличан струцт да смо вам дао за стеку.
>> Постоји један изузетак, а то је један изузетак
јесте да имамо ову додатну цео зове глава,
а глава је овде за праћење шефа ред,
или први елемент у реду.
Уз гомилу, били смо у могућности да пратите елемента који смо били око за преузимање,
или врх стека, користећи само величину,
док је код ред, имамо да се бави са супротним крајевима.
Ми покушавамо да ствари на лепљивост на крају, али онда се врати ствари из фронта.
Тако ефикасно, са главом, имамо индекс почетка реда,
а величина нам даје индекс краја реда
тако да можемо да преузме ствари из главе и додајте ствари на репу.
Док са стек, ми смо били само икада бави врху стека.
Никада нисмо имали приступ дно стека.
Ми само додаје ствари на врху и узео ствари офф врху
тако да није било потребно да се додатно поље унутар нашег струцт.
Да ли то уопште смисла?
У реду. Да, Шарлот? [Шарлот, неразумљив]
[Хардисон] То је велико питање, а то је онај који је дошао у предавању.
Можда шетњу кроз неколико примера ће илустровати зашто
не желимо да користимо конце [0] као руководиоца реда.
>> Дакле, замислите да имамо ред, ми ћемо га зову куеуе.
На почетку, када смо управо то инстанце,
када смо управо то изјавио, нисмо покренут ништа.
То је све смеће. Па наравно желимо да се уверите да покрене
како величина и главу поља бити 0, нешто разумно.
Такође смо могли ићи напред и нулл напоље елементе у нашој ред.
А да би овај напад дијаграма, приметићете да сада наш ред чекања може само држати три елемента;
док наш стек може одржати четири наша куеуе може само држати три.
А то је само да праве дијаграм.
Прва ствар која се овде догађа је да ми енкуеуе ниску "здраво".
И баш као што смо урадили са стек, ништа страшно другачија овде,
бацамо на ниску на жицама [0] и увећава нашу величину од 1.
Ми енкуеуе "ћао", она добија обући.
Дакле, ово личи на стек за највећи део.
Кренули смо овде, нови елемент, нови елемент, величина стално иде горе.
Шта се дешава у овом тренутку, када желимо да декуеуе нешто?
Када желимо да декуеуе, што је елемент који желимо да декуеуе?
[Василије] жице [0]. >> Нула. Тачно тако, Басиле.
Ми желимо да се ослободимо од прве ниске, овај један, "здраво".
Дакле, шта је друга ствар то променило?
Обратите пажњу када смо појавио нешто искључивање стек, ми смо само променили величину,
али овде, имамо пар ствари које се мењају.
Не само на величину промене, али глава промене.
Ово је да се вратимо на тачку Цхарлотте раније:
зашто имамо ову главу, као и?
Има ли сада смисла, Шарлот? >> Некако.
[Хардисон] Кинд оф? Дакле, шта се десило када смо декуеуед?
Шта је глава да урадите сада је занимљиво?
[Шарлот] Ох, зато што мења - у реду. Разумем.
Пошто је глава - где је глава указује на промене у погледу локације.
То више није увек нула индекс један. >> Да, тачно.
Оно што се десило је било да ли декуеуеинг висок елемент
урађено и ми нисмо имали ову област главе
јер смо увек били називајући ову жицу на 0 индекса шеф нашег реду,
онда цемо морати да смени остатак ред надоле.
Морамо да пребаце "ћао" из из ниски [1] са жицама [0].
И стрингс [2] до стрингс [1].
И ми бисмо да то уради за целу листу елемената,
цео низ елемената.
И када ово радимо са низом да добије стварно скупо.
Па ево, то није велика ствар. Ми само имамо три елемента у нашем низу.
Али, ако смо имали ред од хиљаду елемената или милион елемената,
и онда сви одједном почнемо израду гомилу декуеуе позива све у петљи,
ствари заиста дешава да успори јер помера све доле стално.
Знаш, да се помјере са 1, прелаз 1, смене од 1, смена од 1.
Уместо тога, ми користимо ову главу, зовемо га "показивач" иако то није баш показивач
у строгом смислу, то није поентер тип.
То није инт * или цхар или нешто слично.
Али то показује и указује на главу нашег реда. Да?
>> [Студентски] Како декуеуе зна да само пући све што је у глави?
[Хардисон] Како декуеуе зна како да пући све што је у глави? >> Да, да.
>> Шта се гледа само год глава поље постављено на.
Дакле, у овом првом случају, ако погледамо овде,
наша глава је 0, индекс 0. >> Реду.
[Хардисон] Дакле само каже у реду, добро, елемент у индексу 0, стринг "Здраво",
је елемент на челу нашег реда.
Дакле, ми ћемо декуеуе тог момка.
И то ће бити елемент који добија вратио позиваоцу.
Да, Саад? >> Дакле, глава основи поставља - где ћеш да га индекс?
То је почетак тога? >> Да. >> Реду.
[Хардисон] То постаје нови почетак за нашу низа.
Дакле, када декуеуе нешто, све што треба да урадите је да приступите елемента на индексне к.хеад,
и да ће бити елемент који желите да декуеуе.
Ви такође треба да Смањење величине.
Видећемо се ускоро, где ствари постају мало незгодно са овим.
Ми декуеуе, и сада, ако ми опет енкуеуе,
где смо енкуеуе?
Одакле Следећи елемент иде у нашем реду?
Реци ми желимо да енкуеуе ниску "ЦС".
У којем индекс ће ићи? [Студенти] жице [2]. >> Два.
Зашто 2 и није 0?
[Василије] Јер сада је глава 1, тако да је као на почетку листе?
[Хардисон] Тачно. А шта означава крај листе?
Шта смо користили да означи крај нашег реду?
Глава је глава наше реду, почетак нашег реда.
Шта је крај нашег реду? [Студенти] Величина. >> Сизе, тачно.
Дакле, наши нови елементи иду у на величини, а елементи које смо скинемо отпасти у главу.
Када смо енкуеуе следећи елемент, ми смо га стављате у на величини.
[Студентски] Пре него што ставите да, иако, величина је 1, зар не?
[Хардисон] Тачно. Дакле, не баш у величини. Величина +, не +1, али + глава.
Зато што смо померио све по глави износа.
Дакле, сада имамо ред величине 1 који почиње у индексу 1.
Реп је индекс 2. Да?
>> [Студентски] Шта се дешава када декуеуе жице [0], а конце "слотова у меморији
Само се испразнио, у основи, или само заборавили?
[Хардисон] Да. У том смислу, само смо их заборавили.
Ако смо били складиштење копије за њих -
многе структуре података често ће сачувати своје примерке елемената
тако да лице које управља структуру података не мора да брине
о томе где су све те показивачи иду.
Структура података држи на свему, има на свим копијама,
да бисте се уверили да је све опстаје на одговарајући начин.
Међутим, у овом случају, ове структуре података само за једноставност,
не чинећи копије свега што смо складишне у њима.
[Студентски] Да ли је ово континуирани низ -? >> Да.
Ако се осврнемо на оно што је дефиниција ове структуре, јесте.
То је само стандардни низ као што сте видели,
низ цхар * с.
Да ли то -? >> Да, само сам се питао
ако на крају ћете понестане меморије, у извесној мери,
ако имате све ове празне места у вашем низу?
[Хардисон] Да, то је добра ствар.
>> Ако погледамо шта се десило сад у овом тренутку,
смо испуњен наш ред, то изгледа.
Али нисмо баш напунила наш ред
јер имамо ред који је величина 2, али то почиње у индексу 1,
јер то је место где наш показивач глава.
Као што си рекао, тај елемент на жицама [0], на индекс 0, није стварно тамо.
То није у нашој ред висе.
Ми једноставно није сметало да идем и да препишете је када смо га декуеуед.
Дакле, иако изгледа као да смо понестане меморије, заиста није.
То место је на располагању за нас да користимо.
Примерено понашање, ако смо да покушамо и први декуеуе нешто
као "ћао", да би поп бие искључен.
Сада је наш ред чекања почиње у индексу 2 и величине 1.
А сада, ако ми покушамо нешто енкуеуе опет, кажу 50,
50 треба да иду у том месту у индексу 0
јер је још увек доступан за нас. Да, Саад?
[Саад] Да ли се то догодило аутоматски?
[Хардисон] То се не дешава баш аутоматски. Морате да урадите математику
да то ради, али у суштини оно што смо урадили је да смо управо обмотана око.
[Саад] И то је у реду ако то има рупу у средини тога?
[Хардисон] То је ако можемо да математика ради правилно.
>> И испада да је то у ствари није тако тешко урадити са мод оператера.
Дакле, као што смо урадили са Цезаром и крипто ствари,
користи мод, можемо добити ствари да обмотана и наставите
около и около и около са нашим реду,
држећи да шеф показивач креће.
Приметите да је величина је увек поштујући број елемената у ствари у ред.
И то је само глава показивач који држи бициклом кроз.
Ако погледамо шта се овде догодило, ако се вратимо на почетак,
а ви само гледате шта се дешава на глави
када смо енкуеуе нешто, ништа се није десило у главу.
Када смо енкуеуед нешто друго, ништа се није десило у главу.
Чим смо декуеуед нешто, глава иде до једног.
Ми енкуеуед нешто, ништа се не дешава на глави.
Када смо декуеуе нешто, све изненада глава добија увећава.
Када смо енкуеуе нешто, ништа се не дешава на глави.
>> Шта би се десило у овом тренутку, ако бисмо декуеуе нешто поново?
Било која мисли? Шта би се десило са главом?
Шта треба да се деси у главу
ако бисмо декуеуе нешто друго?
Глава сада је на индекс 2,
што значи да је шеф реду је стрингс [2].
[Студентски] Који враћа 0? >> То би требало да се врати на 0. То би требало преломити врати се, тачно.
До сада, сваки пут кад смо се зове декуеуе смо били додајући један у главу,
додајте један у главу, додајте једно по глави, додајте једну на глави.
Чим да шеф показивач стигне до последњег индекса у нашем низу,
онда морамо да га преломити назад около на почетку, врати на 0.
[Шарлот] Шта одређује капацитет реда у стеку?
[Хардисон] У овом случају, управо смо користили # дефинисана константа. >> Реду.
[Хардисон] У актуелна. Ц фајл, можете отићи и гадост са њим мало
и да га као велики или мало онолико колико желите.
[Шарлот] Дакле, када сте га правите ред, како би се рачунар зна
колики желите стек да буде?
[Хардисон] То је велико питање.
Постоји неколико начина. Једна је да то једноставно дефинисати напред
и кажу да ће то бити перчин који има 4 елемента или 50 елемената или 10.000.
Други начин је да се уради оно што су радили људи хакерске издање
и створити функције да имају своје перчин расте динамички као још ствари се додаје унутра
>> [Шарлот] Дакле да иде са првом опцијом, шта синтакса се користи
да кажем програм шта је величина реда?
[Хардисон] Ах. Зато идемо одавде.
И даље сам у стацк.ц овде, па ћу само да дођете до врха овде.
Да ли видите овде ово право? Ово је # дефине капацитета 10.
А ово је скоро потпуно исти синтакса која имамо за ред.
Осим у реду, ми смо добили тај екстра струцт поље овде.
[Шарлот] Ох, мислио сам да је капацитет значило капацитет за ниске.
[Хардисон] Ах. >> То је максимална дужина речи. >> Имам га.
Да. Капацитет овде - то је велика ствар.
И то је нешто што је шкакљиво
јер оно што смо овде изјавио је низ цхар * с.
Низ показивача.
То је низ карактера.
То је вероватно оно што сте видели када сте били проглашења своје бафере за фајла И / О
када сте стварали конце ручно на стеку.
Међутим, оно што ми имамо овде је низ цхар * с.
Дакле, то је низ показивача.
Заправо, ако се вратимо умањили и гледамо шта се дешава овде
у презентацију, видећете да је стварни елементи, карактер података
не чува се у самом низу.
Шта је ускладиштен у нашој низа овде су показивачи на карактер података.
Ок. Тако смо видели како се величина реда је исто као са стек,
величина увек поштује број елемената тренутно у реду.
Након што 2 енкуеуес, величина 2.
Након што је декуеуе величина је сада 1.
Након што други енкуеуе величина је поново до 2.
Дакле, величина дефинитивно поштује број елемената у реду,
и онда глава само наставља бициклизмом.
Она иде од 0-1-2, 0-1-2, 0-1-2.
И сваки пут ми називамо декуеуе, шеф показивач добија увећава до следећег индекса.
А ако је глава да оде преко, то петљи назад около 0.
Дакле са тим, можемо написати декуеуе функцију.
А ми ћемо да напустимо енкуеуе функцију ви уместо спроведе.
>> Када смо декуеуе елемент из нашег реда,
каква је била прва ствар коју Данијел урадио када смо почели да пишемо поп функцију за гомиле?
Дозволите ми да чујем од некога ко није говорио још.
Хајде да видимо, Саад, да ли се сећате шта Данијел урадио као прву ствар кад пише поп?
[Саад] Било је, било је - >> Он је тестирао за нешто.
[Саад] Ако је величина већа од 0. >> Тачно.
А шта је то тестирање?
[Саад] То је тестирање да видим да ли има нешто у низу.
[Хардисон] Да. Управо тако. Дакле, не можете да убаците ништа од гомиле ако је празна.
Исто тако, не можете ништа од декуеуе ред ако је празна.
Која је прва ствар коју треба да урадите у нашој декуеуе функцији овде, шта мислиш?
[Саад] Ако је величина већа од 0? >> Да.
У том случају, ја заправо нисам баш тестирали да ли је 0.
Ако је 0, можемо вратити нулл.
Али тачно иста логика.
И да наставимо са овим.
Ако величина није 0, где је елемент који желимо да декуеуе?
[Саад] У глави? >> Тачно.
Ми само можемо извући први елемент у нашем реду
приступањем елемент у главу.
Ништа луд.
После тога, шта да радимо? Шта треба да се деси?
Шта је била друга ствар коју смо разговарали о томе у декуеуе?
Две ствари морају да се деси, јер је наш куеуе није променило.
[Данијел] Смањите величину. >> Морамо да смањи величину и повећати главу? Управо тако.
Да бисте повећали главу, не можемо само слепо повећати главу, сећам се.
Ми не можемо урадити куеуе.хеад + +.
Морамо да се овај мод од капацитета.
А зашто ми модифитсиране по капацитету, Стелла?
[Стелла] Зато сто обмотана. >> Тачно.
Ми мод по капацитету, јер мора да заврши назад около да 0.
Дакле, сада, у овом тренутку, можемо да радимо шта Данијел рекао.
Можемо Смањи величину.
А онда можемо да врати елемент који је био на врху реда.
Изгледа некако чворноват на први поглед. Можда имам питање. Извини?
>> [Сам] Зашто је први на врху реда? Где то иде?
[Хардисон] То долази из четвртог линији од дна.
Након што смо тестирали да се уверите да наша Редослед није празна,
ми извуче прво цхар *, ми смо извуците елемент који је седео на челу индекса
нашег низа, наше гудаче низа, >> и позив да се први?
[Хардисон] И зовемо га први. Да.
Само да пратите на томе, зашто мислиш да смо то да урадим?
[Сам] Сваки први је управо враћа к.стрингс [к.хеад]? >> Да.
>> Зато радимо овај промену к.хеад са мод функције,
и не постоји начин да се то уради у року од повратка линије такође.
[Хардисон] Управо тако. Ти си спот он. Сем је потпуно уочити он.
Разлог због којег смо морали да се повуку први елемент у нашем реду и чувајте га у променљиву
зато ову линију где смо управо к.хеад,
ту је мод оператер тамо није нешто што можемо да урадимо
и да је потребно да делује на глави, без - у једној линији.
Дакле, ми заправо треба да извуче први елемент, а затим подесите главу,
подесите величину, а затим се вратите елемент који смо извукли.
И то је нешто што ћемо видети касније доћи до
повезане листе, као што смо се играте са њима.
Често када сте ослобађање или располагања повезаних листи
морате да запамтите следећи елемент, следећи показивач на повезану листу
Пре одлагања тренутне.
Јер иначе баците информације о томе шта је остало на листи.
Сада, ако идете на свом апарату, морате отворити куеуе.ц-Кс од овога.
Дакле, ако сам отворим куеуе.ц, дозволите ми да увећај овде,
видећете да имате сличне изгледа датотеку.
Слично изгледа фајл оно што смо имали раније са стацк.ц.
Имамо нашу струцт за ред дефинисан баш као што смо видели на слајдовима.
>> Ми имамо енкуеуе функцију која је за вас да урадите.
И ми имамо овде декуеуе функцију.
Тхе декуеуе функција у датотеци не спроводе,
али ја ћу га ставити назад на ПоверПоинт, тако да можете да га упишете у, ако желите.
Дакле, за наредних 5 минута или тако, ви момци радите на енкуеуе
што је скоро управо супротно декуеуе.
Не морате да подесите главу када сте енкуеуеинг, али шта имате да подесите?
Сизе. Дакле, када енкуеуе, глава остаје нетакнута, величина добија променила.
Али то не узме мало - ви ћете морати да се играте са тим мод
да схватим шта индекс нови елемент треба да буде убачена у.
Зато ћу ти дати момци мало, ставио декуеуе назад на слајду,
и као ви имате питања, да их изнесу, тако да можемо
Сви говоримо о њима као групи.
Такође, са величином ли не - када сте подесили величину, можете увек само -
Не морате да икада модифитсиране величину? [Данијел] Но >> Не морате да модифитсиране величину, у реду.
Јер величина ће увек, ако ти си - под претпоставком да сте управљању ствари на прави начин,
величина ће увек бити између 0 и 3.
Где мораш да модифитсиране када радите енкуеуе?
[Студентски] Само за главу. >> Само за главу, тачно.
А зашто мораш да модифитсиране уопште у енкуеуе?
Када је ситуација у којој желите да мод?
[Студентски] Ако имате ствари у простору, као код просторима 1 и 2,
а онда је потребно да додате нешто на 0.
[Хардисон] Да, тачно. Дакле, ако ваш показивач глава је на самом крају,
или ако је ваша величина, плус твоја глава је већа, односно ће преломити око реду.
>> Дакле, у овој ситуацији у којој смо добили овде на слајду сада,
ако желим да енкуеуе нешто сада,
желимо да енкуеуе нешто на индекс 0.
Дакле, ако се осврнемо на којој 50 иде, а ја зовем енкуеуе 50,
она иде тамо доле на дну. Она иде у индекс 0.
Он замењује "Здраво" који је већ декуеуед.
[Данијел] Немојте се ви бринете о томе у декуеуе већ?
Зашто ништа са главом у енкуеуе?
[Хардисон] О, па ти не мењате главу, извини.
Али морате да користите оператор мод када сте приступате
елемент који желите да енкуеуе када приступате
следећи елемент у свој ред.
[Василије] Нисам то урадио, и ја сам "успех" на тамо.
[Данијел] Ох, ја разумем шта причаш.
[Хардисон] Дакле дидн'т - ви управо урадили на к.сизе?
[Василије] Да. Управо сам променио страну, нисам ништа с главом.
[Хардисон] Ви заправо немате да вратите главу бити ништа,
али када индекс у низу гудаче,
ви у ствари треба да иде напред и израчунати где Следећи елемент је,
јер прут штос, следећи елемент у свом стеку увек била
у индексу одговара величини.
Ако се осврнемо уназад горе у нашој функцији стек пусх,
увек смо могли бубнути у нашем новом елементу право на индекс величини.
Док са листе чекања, не могу то да урадим
јер ако смо у овој ситуацији,
ако енкуеуед 50 наша нова ниска би било у реду отићи на жицама [1]
који ми не желимо да урадимо.
Желимо да имамо нови стринг иде на индекс 0.
>> Да ли неко - да? [Студентски] Имам једно питање, али стварно се не односи.
Шта значи када неко само тражи нешто пред поинтер?
Шта је то име за кратко? Знам да је то само име.
[Хардисон] Пред поентер? Хајде да видимо. У ком контексту?
[Студентски] То је био за уметком. Могу да вас питам касније ако желиш
јер то није баш у вези, али ја само -
[Хардисон] Од Давида убацити код из предавања?
Можемо повући да се и разговарати о томе.
Причаћемо о томе следеће, када дођемо до повезаним листама.
>> Па хајде да веома брзо погледамо шта енкуеуе функција изгледа.
Шта је прва ствар коју људи покушали да ураде у свом енкуеуе линији? У том чекању?
Слично што си урадио за гурање стека.
Шта сте урадили, Стела?
[Стелла, неразумљив]
[Хардисон] Управо тако. Ако (к.сизе == КАПАЦИТЕТА) -
Морам да ставим протезу на правом месту - ретурн.
Увећање мало. Ок.
Шта је сад следећа ствар коју смо морали да радимо?
Баш као и са стек, и убаци на правом месту.
И шта је било право место да убаците то?
Са стека је индекс величине, са овим није баш тако.
[Данијел] Имам к.хеад--или - >> к.стрингс? >> Да.
к.стрингс [к.хеад + к.сизе мод КАПАЦИТЕТ?]
[Хардисон] Ми смо вероватно желите да ставите заграде око овога
тако да смо све одговарајуће предност и тако да је то цлеарт свима.
И подесите да једнако? >> Да ул? >> Да ул. Сјајно.
И сад шта је последња ствар коју морамо да урадимо?
Баш као што смо урадили у стеку. >> Прираст величину? >> Прирасту величину.
Бум. А онда, пошто је стартер код управо вратио лажно по дефаулту,
желимо да променимо ово истина ако све иде преко и све иде добро.
У реду. То је пуно информација за секције.
Нисмо сасвим завршена. Ми желимо да разговарамо о стварно брзо појединачно-повезаним листама.
Ставићу ово па да се вратимо на то касније.
Али хајде да се вратимо на нашу презентацију за само неколико више слајдова.
Дакле енкуеуе је ТОДО, сада смо то урадили.
>> Сада ћемо да погледамо појединачно-повезаним листама.
Причали смо о овоме мало више у предавању.
Колико од вас видео демо где смо имали људе
неспретно указујући једни друге и држање бројевима? >> Био сам у то.
>> Шта ви мислите? Да ли је то, надам се демистификује ове мало?
Са листе, испада да се бавимо овим типом који ћемо позвати чвор.
Док са реда и стека ми смо имали Структуре које бисмо назвали ред у стеку,
смо имали ове нове ред у стека врстама,
Овде је списак заиста само састоји од гомиле чворова.
На исти начин на који су жице само гомила карактера све постројио поред другог.
Повезана листа је само чвор, а други чвор, а други чвор, а други чвор.
И уместо да разбија све чворове заједно и њихово складиштење цонтигуоусли
У реду један поред другог у меморији,
има овај следећи показивач нам омогућава да ускладиштите чворове где год, насумице.
И онда некако жице их све заједно да укаже са једне на другу.
>> А шта је велика предност да је имао преко низа?
Током складиштења свему цонтигуоусли само заглави једни поред других?
Ви се сећате? Да? >> Динамичка додела меморије?
>> Динамичка додела меморије у ком смислу?
[Студентски] У томе можете да задржите што већи и да не морате да померите цео низ?
[Хардисон] Управо тако. Дакле, са низом, када желите да ставите нови елемент у сред њега,
морате да пребаце све да простор.
И као што смо причали са редоследу
Зато држимо тај показивач главе,
тако да нисмо стално мења ствари.
Зато што добија скупо ако имаш велики низ
а ти стално радиш ове случајне уметке.
Док са листе, све што треба да урадите је да баци га на новом чвору,
подесите показиваче, и готови сте.
Шта безвезе о томе?
Поред чињенице да није тако лако да раде са што низа? Да?
[Данијел] Па, претпостављам да је то много теже да приступе одређени елемент у повезаној листи?
[Хардисон] Не можете само скочити на произвољном елементу у средини вашег повезане листе.
Како то урадити уместо тога? >> Морате да прођете кроз целу ствар.
[Хардисон] Да. Морате да прођете кроз један по један, један по један.
То је огромна - то је бол.
Шта је друго - постоји још један пад на ово.
[Василије] Не можете ићи напред и назад? Мораш да идеш у једном смеру?
[Хардисон] Да. Па како ћемо решити то, понекад?
[Василије] двоструко-линкед листама? >> Тачно. Постоје двоструко-повезане листе.
Ту су - жао?
>> [Сам] Да ли је то исто што и коришћење Пред ствар -
Управо сам се сетио, није то оно пред ствар је?
Није ли то између двоструко и појединачно?
[Хардисон] Погледајмо шта је он радио.
Дакле, идемо. Ево листе код.
Овде имамо предптр, овде. Да ли је то оно што сте причали?
Дакле, ово је - он је ослобађајући листу и он покушава да складишти показивач на њега.
Ово није двоструко, појединачно повезана-листе.
Можемо разговарати више о овоме касније, јер ово је прича о ослобађању листу
и желим да прво покажем неке друге ствари.
али то је само - то је сећање на вредност ПТР
[Студентски] Ох, то је Прецеединг поентер? >> Да.
Тако да онда можемо повећавати ПТР сам пре него што смо тада слободни шта предптр је.
Зато не можемо слободно птр а затим позива птр = птр следећи, зар не?
То би било лоше.
Дакле, хајде да видимо, назад на овог момка.
>> Друга лоша ствар око листе је да, док са низом
Ми само имамо све елементе саме наслагане једна поред друге,
Овде смо увели овај показивач.
Дакле, постоји додатни комад меморије која имамо за коришћење
за сваки елемент који смо складиштења у нашој листи.
Ми смо добили флексибилност, али то долази у цену.
Она долази са ове временске трошкове,
и то долази са овим меморијским цени превише.
Време у смислу да сада морамо да прођемо кроз сваки елемент у низу
да пронађе један по индексу 10, или да би били индекс 10 у низу.
>> Само веома брзо, када смо дијаграм из ове листе,
обично држимо на челу листе или први поентер листе
и имајте на уму да је ово истина показивач.
То је само 4 бајта. То није стварна сама чвор.
Дакле, видите да нема инт вредност у томе, нема поред показивача у њој.
То буквално је само показивач.
То ће да укаже на нешто што је стварни чвор струцт.
[Сам] показивач зове чвор? >> Ово је - не. Ово је показивач на нешто типа чвора.
То је показивач на чвор струцт. >> О, у реду.
Дијаграм на левој, кода на десној страни.
Можемо га поставити на нулл, што је добар начин да се почне.
Када га дијаграм, можете или писати га као нула или сте ставили линију кроз њега тако.
>> Један од најлакших начина да раде са листама,
и ми не питате како препенд и додати да видите разлике између два,
али ако имену је дефинитивно лакше.
Када препенд, ово је место где ти - када препенд (7),
одете и направите струцт ноде
и прво подесите да се укаже на њега, јер сада, пошто смо га припремљени,
то ће бити на почетку листе.
Ако смо препенд (3), што ствара још један чвор, али сада долази пре 3 7.
Дакле, ми смо у суштини гура ствари на нашој листи.
Сада можете видети да препенд, понекад људи зову пусх,
јер сте гура нови елемент на вашој листи.
Такође је лако избрисати на предњој листи.
Тако ће људи често називају тај поп.
И на тај начин, можете симулирати гомилу користећи повезану листу.
Упс. Нажалост, сада смо улазим Додај. Дакле, овде смо припремљени (7), сада имамо препенд (3).
Ако смо припремљени нешто друго на овој листи, ако смо припремљени (4),
онда би имали 4 и онда 3 и онда 7.
Онда смо могли појавити и уклоните 4, уклони 3, уклонити 7.
Често више интуитиван начин да се размишља о томе је са Додај.
Тако сам диаграммед шта би то изгледати са додати овде.
Ево, приложио (7) не изгледа другачије
јер постоји само један елемент у листи.
И додавање (3) ставља га на крају.
Можда можете видети сада трик са Приложена
је да, пошто ми само знамо где је почетак листи је,
да додате на листу, морате да ходају скроз кроз листу
доћи до краја, стани, а затим изградити свој чвор и све што бубнути доле.
Вире све ствари горе.
Дакле, са препенд, као што смо управо риповали кроз ово заиста брзо,
када препенд на листи, то је прилично једноставно.
>> Ви направите свој нови чвор, укључују неку динамичку алокацију меморије.
Дакле, овде се правиш чвора струцт помоћу маллоц.
Тако маллоц користимо јер ће издвојити меморију за нас касније
зато што не желим да ово - ми желимо ово меморије трају дуго.
И ми смо добили показивач на простор у меморији који смо управо додељен.
Ми користимо величину чвора, не сумирам поља.
Ми не ручно генерише број бајтова,
уместо тога користимо сизеоф тако да знамо да смо све одговарајући број бајтова.
Ми смо се уверили да тестирамо да наш позив маллоц успео.
То је нешто што желите да урадите у целини.
На савременим машинама, понестаје меморије није нешто што је лако
осим ако расподеле гомилу ствари и чинећи огромну листу,
али ако правите ствари за, рецимо, као иПхоне или Андроид,
Ви немате ограничене ресурсе меморије, поготово ако радиш нешто интензивније.
Зато је добро да се у пракси.
>> Приметите да сам овде користио пар различите функције
да сте видели да су нова врста.
Тако је исто као иф иф
осим свог првог аргумента поток на који желите да одштампате.
У овом случају, желимо да штампате на стандардни стринг грешке
која се разликује од стандардног оутстреам.
Подразумева се појави на истом месту.
Такође, штампа на терминал, али можете -
користите ове команде сте научили о томе, преусмеравање технике
Ви о томе научили у видео Томија за проблем сет 4, можете га режирати
различитим областима, а затим излазак, овде, излази ваш програм.
То је у суштини је као повратка из главног,
осим користимо излаз јер овде повратак неће учинити ништа.
Ми нисмо у главни, па враћање не изађете из програма као што смо желели.
Дакле, ми користимо излазну функцију и дати му неку грешку.
Затим ту смо поставили вредност поља, новог чвора његова сам на терену да буду једнаки и, и онда смо га пошаљем горе.
Ми смо поставили следећи показивач новог чвора да се укаже на први,
и онда прво ће сада указати на нови чвор.
Ове прве линије кода, ми заправо градимо нови чвор.
Не последња два реда ове функције, али први.
Ви заправо може извлачити у функцији, у функцији помагач.
То је често оно што радим, ја га извуците у функцији,
Ја то зовем нешто буилд чвора,
и да држи препенд функција прилично мала, то је онда само 3 линије.
Ја позивање на моје израде чвор функције, а онда сам жице све горе.
>> Коначна ствар коју желим да вам покажем,
а ја ћу ти додате и све то на своју руку,
је како прелазили преко листу.
Постоји гомила различитих начина да прелазили преко листу.
У овом случају, ми ћемо наћи дужину листе.
Тако ћемо почети са дужином = 0.
Ово је веома сличан писању стрлен за ниске.
То је оно што ја желим да вам покажем, ово петље овде.
Изгледа некако фанки, то није уобичајена инт и = 0, и <штагод, и + +.
Уместо тога је иницијализација нашу променљиву н да буде почетак листе.
А онда, док је наш итератора променљива није нула, ми наставимо.
То је зато, по обичају, крај наше листе ће бити нулл.
А онда увећати, него раде + +,
повезана листа еквивалент + + је н = н-> нект.
>> Пустићу да попуните празнине овде, јер смо ван времена.
Али, имајте то на уму док радите на својим спеллр псетс.
Повезане листе, ако спровођењу хеш табелу,
ће сигурно доћи у врло згодан.
А има овај идиом за петље у ствари ће учинити живот много лакше, надам се.
Сва питања, брзо?
[Сам] Хоћете ли послати попуњен СЛЛ и СЦ?
[Хардисон] Да. Ја ћу послати попуњене слајдове и попуњен СЛЛ штек и куеуе.цс.
[ЦС50.ТВ]