[Powered by Google Translate] [Раздзел 6: менш камфортна] [Nate Хардисон] [Harvard University] [Гэта CS50.] [CS50.TV] Добра. Сардэчна запрашаем у профіль 6. На гэтым тыдні мы збіраемся казаць пра структуры дадзеных у раздзеле у першую чаргу таму, што праблема на гэтым тыдні устаноўлены на spellr робіць цэлы букет розных даследаванняў структуры дадзеных. Ёсць мноства розных спосабаў, вы можаце пайсці з праблемай набору, і больш структур дадзеных вы ведаеце пра, тым больш цікавых рэчаў можна зрабіць. 

Такім чынам, давайце пачнем. Спачатку мы пагаворым аб стэкі, стэка і чэргі структур дадзеных, якія мы збіраемся пагаварыць. Стэкі і чэргі сапраўды карысныя, калі мы пачынаем казаць аб графіках, якія мы не збіраемся рабіць так шмат цяпер. Але яны вельмі добра разумеюць адной з буйных фундаментальных структур дадзеных CS. Апісанне ў спецыфікацыі пастаўленай задачы, калі вы пацягніце яго ўверх, кажа пра стэкі падобна Куча сталовай латкі, якія ў вас ёсць у сталовай за абедным залах дзе, калі абедзенны персанал прыходзіць і ставіць сталовай латкоў пасля яны чысцяць іх, яны складаюць іх адна на іншую. А потым, калі дзеці прыходзяць, каб атрымаць ежу, яны цягнуць з латкоў, спачатку верхнюю, а затым адзін ніжэй за яго, то той, што ніжэй. Так што, па сутнасці, першы латок, абедзенны персанал паклаў з'яўляецца апошняй, якая атрымлівае знятыя. Апошнім, што супрацоўнікі сталовай паставіць на першае адзін, які атрымлівае знятыя на вячэру. У спецыфікацыі пастаўленай задачы, якія вы можаце спампаваць, калі вы гэтага яшчэ не зрабілі, мы кажам пра мадэліраванне stucture стэка дадзеных з дапамогай такой структуры. 

Такім чынам, што мы маем тут, гэта падобна на тое, што была прадстаўлена ў лекцыі, акрамя лекцыі мы прадставілі гэта з цэлымі, а не сімвал * с. Гэта будзе стэк, які захоўвае і што? Дэніэл? Што мы захоўванню ў гэтым стэку? [Данііл] радкоў? >> Мы захоўвання радкоў у гэтым стэку, гэта дакладна. Усё, што вам трэба мець для таго, каб стварыць стэк ўяўляе сабой масіў канкрэтнай магутнасці, якая ў дадзеным выпадку, магутнасці будзе ва ўсіх вялікіх літарах, таму што гэта ўвесь час. І тады ў дадатак да масіву, усе мы павінны адсочваць гэта бягучы памер масіва. Адна рэч, каб адзначыць тут, што гэта крута з'яўляецца тое, што мы ствараем складзеныя структуры дадзеных на іншую структуру дадзеных, масіў. Існуюць розныя спосабы рэалізацыі стэкаў. Мы не будзем рабіць гэтага зусім яшчэ, але, спадзяюся, пасля выканання звязанага спісу праблем, Вы ўбачыце, як вы можаце лёгка рэалізаваць стэк па-над звязанага спісу, а таксама. Але цяпер, мы будзем прытрымлівацца масіваў. Такім чынам, яшчэ раз, усё што нам трэба гэта масіў, і мы проста неабходна адсочваць памер масіва. [Сэм] Выбачайце, чаму гэта, што вы сказалі, што стэк знаходзіцца на вяршыні радкі? Мне здаецца, што радкі ў стэку. [Хардисон] Так. Мы ствараем, мы бярэм наш масіў структуры дадзеных - гэта вялікае пытанне. Такім чынам, пытанне, чаму, для людзей, якія назіраюць за гэтым у Інтэрнэце, Таму мы кажам, што стэк у верхняй частцы радка, таму што тут яна выглядае як радкі ўнутры стэка? Які цалкам справе. Тое, што я меў на ўвазе, што ў нас ёсць структуры масіва дадзеных. У нас ёсць масіў сімвалаў * з, гэта масіў радкоў, і мы збіраемся дадаць да гэтага, каб стварыць стэк структуры дадзеных. 

Такім чынам, стэк трохі больш складаным, чым масіў. Мы можам выкарыстоўваць масіў для стварэння стэка. Дык вось, калі мы кажам, што стэк пабудаваны на вяршыні масіва. Сапраўды гэтак жа, як я сказаў раней, мы можам пабудаваць стэк на пачатак звязанага спісу. Замест таго каб выкарыстоўваць масіў для захоўвання нашых элементы, мы маглі б выкарыстоўваць звязаны спіс для захоўвання нашых элементы і пабудаваць стэк вакол гэтага. Давайце разгледзім некалькі прыкладаў, гледзячы на ​​код, каб убачыць, што на самой справе тут адбываецца. На левым, я кінуў, што гэта стэк структура будзе выглядаць у памяці калі ёмістасць была # вызначаецца як чатыры. У нас ёсць нашы чатыры элемента масіў сімвалаў *. У нас ёсць радкі [0], радкоў [1], радкоў [2], струны [3], а затым, што ў мінулым прастору для нашага памеру цэлага ліку. Ці мае гэта сэнс? Добра. Гэта тое, што адбудзецца, калі тое, што я раблю на правую, які будзе свой код, гэта проста абвясціць структуру, складзеныя структура называецца с. Гэта тое, што мы атрымліваем. Яна ўсталёўвае гэты след у памяці. Першае пытанне, вось тое, што з'яўляецца зместам гэтага стэка структуры? Цяпер яны нічога, але яны не зусім нічога. Яны такога смецця. Мы паняцця не маем, што ў іх. Калі мы аб'яўляем стэк S, мы проста кідалі ўніз, што ў верхняй частцы памяці. Гэта накшталт як аб'яву Int я, а не яго ініцыялізацыі. Вы не ведаеце, што там. Вы можаце прачытаць, што там, але яна не можа быць супер карысным. Адна рэч, якую вы хочаце заўсёды памятаць, каб зрабіць гэта ініцыялізаваць усё, што неабходна ініцыялізаваць. У гэтым выпадку, мы збіраемся, каб ініцыялізаваць памер роўным нулю, таму што гэта адгукнецца вельмі важна для нас. Мы маглі б пайсці далей і ініцыялізаваць ўсе паказальнікі, усё сімвал S * каб быць зразумелымі некаторыя значэння, верагодна, нулявы. Але гэта не зусім неабходна, каб мы гэта робім. 

Цяпер дзве асноўныя аперацыі па стэкі? Хто-небудзь памятае з лекцыі, што вы робіце са стэкамі? Да? [Stella] Націск і пляскаць? >> Менавіта так. Націск і з'яўляюцца дзве асноўныя аперацыі па стэкі. І што ж штуршок рабіць? >> Гэта ставіць нешта на верхнім з стэка, а затым бавоўна здымае яго. [Хардисон] Менавіта так. Такім чынам, націснуўшы штурхае нешта на вяршыні стэка. Гэта падобна на сталовую персаналу пакласці сталовую паднос на стале. І з'яўляюцца прымае сталовай латок з стэка. Давайце разгледзім некалькі прыкладаў таго, што адбываецца Калі мы штурхаць рэчы ў стэк. Калі б мы былі націснуць на радок "прывітанне" на наш стэк, гэта тое, што наша схема будзе выглядаць цяпер. Паглядзіце, што адбываецца? Мы вылучылі на першы элемент нашага масіва радкоў і мы павялічылі колькасць нашых памерам роўным 1. Такім чынам, калі мы паглядзім на розніцу паміж двума горкамі, тут быў 0, то вось перад штуршком. Вось пасля штуршка. Перад націскам, пасля штуршка. І зараз у нас ёсць адзін элемент у нашым стэку. Гэта радок "прывітанне", і гэта ўсё. Усё астатняе ў масіве, на наш масіў радкоў, яшчэ смецце. Мы не ініцыялізацыі. Скажам, мы націскаем іншую радок на наш стэк. Мы збіраемся націснуць "свет" на гэты раз. Такім чынам, вы можаце бачыць "свет" тут ідзе зверху "прывітанне", і памер адлік ідзе да 2. Цяпер мы можам націснуць "CS50», і што пайду на вяршыні зноў. Калі мы вернемся, вы можаце ўбачыць, як мы націску рэчы на ​​вяршыні стэка. А зараз мы пяройдзем да поп-музыкі. Калі мы зайшлі нешта з стэка, што здарылася? Ніхто бачыце розніцу? Гэта даволі тонкі. [Студэнт] памеру. >> Так, памер змяніўся. 

Што б вы яшчэ чакалі змяніць? [Студэнт] радкоў, таксама. >> Праве. Радкоў таксама. Аказваецца, што, калі вы робіце гэта такім чынам, таму што мы не капіюючы элементы ў нашым стэку, Мы на самой справе не трэба нічога рабіць, мы можам проста выкарыстоўваць памер адсочваць колькасць рэчаў у нашым масіве так што, калі мы ўсплываў зноў, зноў, мы проста памяншаем нашу памерам да 1. Там няма неабходнасці на самай справе пайсці і перапісаць усё. Выгляд ачмуральны. Атрымліваецца, што мы звычайна проста пакінуць рэчы ў спакоі, таму што гэта менш працы для нас. Калі мы не павінны вярнуцца і перапісаць нешта, то навошта гэта рабіць? Таму, калі мы двойчы ўсплываў з стэка, усё, што робіць памяншэння памеру пару разоў. І зноў жа, гэта толькі таму, што мы не капіяваць рэчы ў нашым стэку. Да? Ідзем далей. [Студэнт, неразборліва] >> І што адбываецца тады, калі вы націскаеце зноў нешта? Калі вы націскаеце зноў нешта, дзе яно дзяецца? Куды яно дзяецца, Васіль? >> У радка [1]? >> Праве. Чаму яны не ідуць у радкі [3]? [Васіль], таму што забыўся, што было нешта ў радку [1] і [2]? [Хардисон] Менавіта так. Наш стэк, па сутнасці, "забыўся", што ён трымаўся за нешта у радку [1] або радкоў [2], таму, калі мы націскаем "Woot», ён проста ставіць, што ў элемент радкі [1]. Ці ёсць пытанні аб тым, як гэта працуе, на базавым узроўні? [Сэм] Так што гэта не дынамічны ў любым выпадку, з пункту гледжання колькасці або ў тэрмінах памеру стэка? [Хардисон] Менавіта так. Гэта - Справа ў тым, што гэта не было дынамічна growning стэка. Гэта стэка, які можа быць ня больш за чатыры знакаў * з, не больш за чатыры рэчаў. Калі б мы былі, каб паспрабаваць падштурхнуць 1/5 рэч, што вы думаеце павінна адбыцца? [Студэнты, неразборліва] [Хардисон] Менавіта так. Ёсць цэлы шэраг рэчаў, якія могуць здарыцца. Гэта магло сегментах віна, у залежнасці ад таго, што мы былі - як менавіта мы ажыццяўлялі заднім канцы. Гэта можа перазапісаць. Ён мог бы мець, што перапаўненне буфера, што мы казалі ў класе. Што было б найбольш відавочныя рэчы, якія могуць быць перазапісаны калі б мы спрабавалі праштурхнуць лішняя рэч на нашым стэку? Такім чынам, вы згадалі перапаўнення буфера. Што можа быць тое, што б атрымаць пісьмовае больш або растаптаў калі мы перапоўненыя выпадкова, спрабуючы падштурхнуць лішняя рэч? [Данііл, неразборліва] >> Магчыма. Але на пачатковым этапе, што можа здарыцца? Што, калі мы спрабавалі праштурхнуць 1/4 рэч? Гэта можа перапісаць памер, па меншай меры, з гэтай памяццю схеме, што ў нас ёсць. 

У апісанні мноства праблем, што мы і збіраемся рэалізацыі сёння, тое, што мы хочам зрабіць, гэта проста вяртанне ілжывым. Нашы метаду прымусовай збіраецца вярнуць лагічнае значэнне, і што лагічнае значэнне будзе сапраўдным, калі штуршок паспяхова і ілжыва, калі мы не можам вылучыць нічога больш, таму што стэк перапоўнены. Давайце разгледзім крыху, што код прама цяпер. Вось наш штуршок функцыі. Нашы штуршок функцыі для стэка збіраецца ўзяць у радку пакласці на стэк. Ён збіраецца вярнуцца дакладна, калі радок была паспяхова выцеснілі ў стэку, а ў адваротным выпадку. Любыя прапановы аб тым, што можа быць добрым першае, што трэба рабіць тут? [Сэм] Калі памер роўны магутнасцю затым вярнуцца ілжывым? [Хардисон] Bingo. Добрая праца. Калі памер мае патэнцыял, мы збіраемся вярнуцца ілжывым. Мы не можам змясціць больш нічога ў нашым стэку. У адваротным выпадку, мы хочам пакласці нешта на вяршыні стэка. Што такое "вяршыню стэка," з самага пачатку? [Данііл] Памер 0? Памер >> 0. Што такое вяршыні стэка пасля ёсць адна рэч, у стэку? Місіі, вы ведаеце? [Missy] One. >> Памер адзін, сапраўды. Вы працягвайце дадаваць да памеру, і кожны раз, калі вы змяшчаеце ў новы элемент на памер індэкса ў масіве. Мы можам зрабіць гэта з такой адзін-лайнер, калі гэта мае сэнс. Такім чынам, мы атрымалі наш масіў радкоў, мы збіраемся атрымаць да яго доступ на памер індэкса, і мы толькі збіраемся, каб захаваць наш сімвал * у там. Звярніце ўвагу, што там няма радкі капіяванне адбываецца тут, няма дынамічнага размеркавання памяці? А потым Missy выхоўвалі, што мы цяпер павінны зрабіць, таму што мы захоўваць радок у адпаведнае месца ў масіве, і яна сказала, што мы павінны былі павялічваць памер аднаго, так што мы гатовыя для наступнага штуршка. Такім чынам, мы можам зрабіць гэта з s.size + +. На дадзены момант, мы ўпіхнулі ў нашым масіве. Што гэта апошняе, што мы павінны рабіць? [Студэнт] Вярнуцца праўда. >> Вярнуцца праўда. Так што гэта даволі просты, вельмі просты код. Ці не занадта шмат. Пасля таго як вы абгорнутыя вакол галавы, як стэк працуе, гэта даволі проста рэалізаваць. 

Цяпер, наступная частка гэтага з'яўляюцца радкі з стэка. Я збіраюся даць вам, хлопцы некаторы час, каб працаваць над гэтым няшмат. Гэта амаль па сутнасці, супрацьлеглае таму, што мы зрабілі тут, у штуршку. Што я зрабіў на самой справе - ой. Я загрузіўся прыбора тут, і ў прыбор, Я падняў праблемы ўсталяваць 5 спецыфікацыі. Калі мы павялічым тут, мы можам бачыць, што я знаходжуся на cdn.cs50.net/2012/fall/psets/pset5.pdf. Хіба вы, хлопцы, запампаваў гэты код, што знаходзіцца тут, section6.zip? Добра. Калі вы яшчэ не зрабілі гэтага, зрабіце гэта прама зараз, вельмі хутка. Я зраблю гэта ў маім акне тэрмінала. Я сапраўды зрабіў гэта тут. Так. Так, Сэм? >> У мяне ёсць пытанне аб тым, чаму ты сказаў s.string 'ы дужках памер = вул? Што такое СТА? Хіба што пэўная дзесьці раней, ці - о, у знак вул *? [Хардисон] Так, менавіта так. Гэта быў аргумент. >> Ну, добра. Выбачайце. [Хардисон] Мы указаннем радкі націснуць цалі Іншае пытанне, што можа прыдумаць, што мы сапраўды не гаворым пра тут быў Мы лічылі само сабой якія разумеюцца, што ў нас была гэтая зменная з , Які быў па сваіх маштабах і даступным для нас. Мы лічылі само сабой якія разумеюцца, што было з гэтым стэкам структуры. Такім чынам, азіраючыся на гэты штуршок код, Вы можаце бачыць, што мы робім рэчы з гэтага радка, якія атрымалі прайшло ў але потым усё раптоўна, мы доступе s.size, быццам бы, адкуль ёй прыйшоў? У кодзе, які мы збіраемся паглядзець у раздзеле Архіў , А затым рэчы, якія вы будзеце рабіць у вашай праблеме ўсталёўвае, мы зрабілі наш стэк будуем глабальную зменную так што мы можам мець доступ да яго ва ўсіх нашых розных функцый без неабходнасці ўручную перадаваць яго і перадаць яго па спасылцы, рабіць усё ў такім жа родзе да яго. Мы проста падманвае трохі, калі хочаце, каб зрабіць рэчы лепш. І гэта тое, што мы тут робім, таму што гэта для задавальнення, гэта прасцей. Часта, вы ўбачыце, людзі робяць гэта, калі яны маюць адзін вялікі структуры дадзеных які эксплуатуецца ў рамках сваіх праграм. 

Давайце вернемся да прыборы. У кожнага паспяховага атрымаць section6.zip? Усе распакаваць яго з дапамогай распакаваць section6.zip? Калі вы зойдзеце ў раздзел 6 каталогаў - ааа, паўсюль - і вы пералічыце тое, што тут, вы бачыце, што ў вас ёсць тры розных. з файламі. У вас ёсць чарзе, SLL, які з'яўляецца односвязный спіс, і стэк. Калі вы адкрыеце stack.c, Вы бачыце, што ў нас ёсць гэтая структура вызначана для нас, дакладныя структуры, які мы толькі што казалі ў слайдах. У нас ёсць нашы глабальныя зменныя для стэка, Мы атрымалі наш штуршок функцыі, а то ў нас ёсць наша поп-функцыі. Я пастаўлю код адсунуць на слайдзе тут, але тое, што я хацеў бы вам, хлопцы, каб зрабіць гэта, у меру вашых магчымасцяў, пайсці і рэалізацыі поп-функцыі. Пасля таго як вы рэалізавалі яго, вы можаце скампіляваць гэта з рабіць стэк, , А затым запусціць выніковы выкананы стэк, і што будзе працаваць усё гэта тэставы код сюды, гэта ў асноўным. А галоўнае клапоціцца пра справу робіць штуршок і поп-званкі і пераканаўшыся, што ўсё ідзе праз усё ў парадку. Ён таксама ініцыялізуе памер стэка прама тут так што вам не прыйдзецца турбавацца аб тым, што ініцыялізацыя. Можна выказаць здагадку, што гэта было правільна ініцыялізаваны Да таго часу, доступ да яго ў поп-функцыі. Ці мае гэта сэнс? Такім чынам, тут мы ідзем. Там у штуршок код. Я дам вам, хлопцы 5 або 10 хвілін. І калі ў вас ёсць якія-небудзь пытанні ў прамежкавым той час як вы кадавання, Калі ласка, папытаеце іх у вушы. Так што калі вы атрымаеце камень перапоны, проста спытайце. Дазвольце мне ведаць, хай ўсе астатнія ведаюць. Праца з вашым суседам таксама. [Данііл] Мы проста ажыццяўленні поп прама цяпер? >> Проста поп-музыкі. Хоць Вы можаце скапіяваць рэалізацыі штуршок, калі вы хочаце так што тэставанне будзе працаваць. Таму што гэта цяжка праверыць рэчы патрапіць у - або, цяжка праверыць з'яўляцца рэчы з стэка, калі няма нічога ў стэк з самага пачатку. 

Што такое поп павінна быць вяртанне? Элемент з вяршыні стэка. Ён павінен атрымаць элемент з вяршыні стэка , А затым памяншаць памер стэка, і зараз вы страцілі элемент на вяршыні. І тады вы вернецеся элемент на вяршыні. [Студэнт, неразборліва] [Хардисон] Што здарыцца, калі вы гэта зробіце? [Студэнт, неразборліва] Што ў выніку адбываецца гэта вы, верагодна, доступ альбо Элемент, які не быў ініцыялізаваны, так што ваш разлік , Дзе апошні элемент выключаны. Дык вось, калі вы заўважылі, у штуршку, мы доступе радкоў у элеменце s.size таму што гэта новы індэкс. Гэта новая вяршыня стэка. Калі ў поп, s.size будзе наступны прасторы, прастору, якое знаходзіцца на вяршыні ўсіх элементаў у стэку. Такім чынам, самы верхні элемент не ў s.size, але, хутчэй, гэта пад ім. 

Іншая рэч, каб зрабіць, калі вы - у поп, гэта ў вас ёсць для памяншэння памеру. Калі вы памятаеце, вернемся да нашай маленькай дыяграме прама тут, на самай справе, адзінае, што мы бачылі, адбываецца, калі мы называлі поп- было тое, што гэты памер ўпала, спачатку ў 2, то да 1. Потым, калі мы вылучылі новы элемент, ён пойдзе на на належным месцы. [Васіль] Калі s.size роўна 2, то не было б перайсці да элемента 2, і вы хочаце, каб ўсплываў гэты элемент прэч? Такім чынам, калі мы пайшлі ў - >> Такім чынам, давайце паглядзім на гэта яшчэ раз. Калі гэта наш стэк на дадзены момант і мы называем поп, , Пры якім індэкс самага верхняга элемента? [Васіль] У 2, але гэта будзе поп-3. >> Праве. Дык вось, дзе наш памер 3, але мы хочам, каб соваць элемент з індэксам 2. Гэта вельмі тыповы выгляд на адзінку, што ў вас з нулявой індэксацыі масіваў. Такім чынам, вы хочаце, каб соваць трэці элемент, а трэці элемент не з індэксам 3. І таму мы не павінны рабіць гэта мінус 1, калі мы націску адбываецца таму, што прама зараз, вы заўважыце, што самы верхні элемент, калі б мы былі вылучыць нешта яшчэ ў стэк на дадзены момант, Мы хацелі б, каб падштурхнуць яе з індэксам 3. І так ужо здарылася, што памер і індэксы выстройваюцца, калі вы націскаеце. 

У каго ёсць рабочая рэалізацыі стэка? У вас ёсць працоўны стэк адзін. Ці ёсць у вас поп працоўныя яшчэ? [Данііл] Так. Я так думаю. >> Праграма працуе, а не сегментах разломаў, гэта раздрукоўка? Ці ёсць раздрукаваць "поспех" пры запуску? Так. Зрабіць стэк, запусціць яго, калі ён друкуе «поспех» і не ідзе бум, то ўсё добра. Добра. Давайце пяройдзем да прылады вельмі хутка, і мы пройдзем праз гэта. Калі мы паглядзім на тое, што адбываецца тут з поп- Daniel, што было першае, што вы зрабілі? [Данііл] Калі s.size больш 0. [Хардисон] Добра. А навошта вы гэта зрабілі? [Данііл] Каб пераканацца ў тым, што нешта ўнутры стэка. [Хардисон] Дакладна. Вы хочаце, каб праверыць, каб пераканацца, што s.size больш 0; у адваротным выпадку, што вы хочаце, каб адбылося? [Данііл] Return нуль? >> Вярнуцца нулявы, гэта дакладна. Так што, калі s.size больш 0. Тады што ж мы будзем рабіць? Што мы будзем рабіць, калі стэк не пусты? [Stella] Вы паменшыце памер? >> Вы памяншэння памеру, усё ў парадку. Так як жа вы гэта зробіце? >> S.size--. [Хардисон] Вялікі. А тое, што ты зрабіў? [Stella] І тады я сказаў вяртання s.string [s.size]. [Хардисон] Вялікі. У адваротным выпадку вы вернецеся нулявы. Так, Сэм? [Сэм] Чаму яна не павінна быць s.size + 1? [Хардисон] плюс 1? >> Так. >> Ёсць. [Сэм] Я думаў, таму што вы прымаеце 1 з, то вы будзеце вяртацца не той, што яны прасілі. [Хардисон] І гэта было менавіта тое, што мы гаворым пра цэлым з гэтым пытаннем ад 0 індэксаў. Таму, калі мы маштаб тут. Калі мы паглядзім на гэтага хлопца прама тут, вы можаце ўбачыць, што калі мы поп, Мы з'яўляцца элемент з індэксам 2. 

Такім чынам, мы зніжаем наш памер, а затым наш памер адпавядае нашаму індэксе. Калі мы не памяншаем памер, а затым мы павінны зрабіць памер -1, а затым декремента. Вялікі. Усё добра? Ёсць пытанні па гэтай нагоды? Ёсць шмат розных спосабаў, каб напісаць гэта, а таксама. На самай справе, мы можам зрабіць нешта яшчэ - мы можам зрабіць адзін-лайнер. Мы можам зрабіць адну лінію звароту. Такім чынам, мы сапраўды можам памяншаць перш чым мы вернемся на гэтым. Такім чынам, паклаўшы - да s.size. Гэта робіць лінію вельмі шчыльны. Дзе розніца паміж -. З памерам і s.size-- што гэта постфикс - яны называюць гэта постфикс, таму што - прыходзіць пасля s.size-- азначае, што s.size ацэньваецца для мэт знаходжання індэкса як у цяперашні час, калі гэтая лінія будзе выканана, і тады гэта - адбываецца пасля радка запускаецца на выкананне. Пасля таго, як элемент s.size індэкс даступны. І гэта не тое, што мы хочам, таму што мы хочам декремент адбудзецца ў першую чаргу. Othewise, мы будзем атрымліваць доступ да масіву, па сутнасці, па-за законам. Мы збіраемся атрымліваць доступ да элемента вышэй за тую, што мы на самай справе хочам атрымаць доступ. Так, Сэм? >> Гэта хутчэй і выкарыстоўвае менш памяці, каб у адным радку ці не? [Хардисон] Шчыра кажучы, гэта сапраўды залежыць. [Сэм, неразборліва] >> Так, гэта залежыць ад абставінаў. Вы можаце зрабіць кампілятар трукі каб атрымаць кампілятар прызнаць, што, як правіла, я мяркую. 

Такім чынам, мы ўжо казалі трохі аб гэтай рэчы аптымізацыі кампілятараў што вы можаце зрабіць у зборы, і гэта такая рэч, што кампілятар можа быць у стане высветліць, як Гэй, можа быць, я магу зрабіць гэта ўсё ў адной аперацыі, у адрозненне ад загрузкі памер зменнай з аператыўнай памяці, яго памяншэння, захоўванне яго назад, а затым загрузку яго зноў Для апрацоўкі астатняй частцы гэтай працы. Але, як правіла, не, гэта не тая рэч, што збіраецца зрабіць праграму значна хутчэй. Ёсць яшчэ пытанні па стэкаў? 

Такім чынам, штурхаючыся і з'яўляюцца. Калі вы, хлопцы, жадаеце паспрабаваць хакерам выданне, тое, што мы зрабілі ў хакерам выданне фактычна пайшоў і зрабіў гэта стэк дынамічна расці. Праблема ёсць у першую чаргу тут, у штуршок функцыі, каб высветліць, як зрабіць гэты масіў расці як вы працягваць настойваць больш і больш элементаў у стэк. Гэта на самай справе не так ужо шмат дадатковага кода. Проста выклік - вы павінны памятаць, каб атрымаць званкі на таНос там належным чынам, , А затым высветліць, калі вы збіраецеся тэлефанаваць пераразмеркаваць. Гэта весела праблемай, калі вы зацікаўленыя. 

Але на дадзены момант, давайце рухацца далей, і давайце пагаворым аб чэргах. Пракруціць тут. Чарга блізка роднасны стэка. Такім чынам, у стэку, рэчы, якія былі ўведзены ў апошнім былі першымі рэчамі, каб потым быць адноўленая. У нас ёсць апошні ўвайшоў, першы выйшаў, або ЛИФО, замовы. У той час як у чарзе, як вы чакалі б ад таго, калі вы стаіце ў чарзе, Першым чалавекам, стаць у чаргу, перш за ўсё, каб патрапіць у чаргу, гэта першае, што атрымлівае здабываецца з чаргі. Чэргі таксама часта выкарыстоўваецца, калі мы маем справу з графікамі, пра якую мы гаварылі коратка стэкі, і чэргаў таксама зручныя для кучу іншых рэчаў. Адна рэч, якая прыходзіць часта спрабуе падтрымліваць, напрыклад, адсартаваны спіс элементаў. І вы можаце зрабіць гэта з дапамогай масіва. Вы можаце падтрымліваць адсартаваны спіс рэчаў у масіве, аднак там, дзе становіцца складана тады ў вас заўсёды ёсць, каб знайсці адпаведнае месца, каб ўставіць наступную рэч. Так што калі ў вас ёсць масіў лікаў, ад 1 да 10, і вы хочаце пашырыць, што для ўсіх лікаў ад 1 да 100, і вы атрымліваеце гэтых лічбаў у адвольным парадку і спрабавалі трымаць усё Сартаваць як вы ідзяце праз, вы ў канчатковым выніку даводзіцца рабіць шмат перадач. Пры некаторых тыпах чэргаў і некаторых відаў базавых структур дадзеных Вы можаце фактычна трымаць яго даволі проста. Вы не маеце нешта дадаць, а затым пераразмеркавацца ўсё гэта кожны раз. Таксама вы павінны зрабіць шмат зрушэнне ўнутраных элементаў вакол. Калі мы глядзім на чарзе, вы бачыце, што - і ў queue.c ў раздзеле кода - Структура, якую мы далі вам сапраўды падобная на структуру, якую мы далі вам за стэка. 

Там у адно выключэнне з гэтага, і што за адным выключэннем з'яўляецца тое, што ў нас ёсць гэта дадатковыя цэлы лік, званае галавой, і галава тут для адсочвання галаве чарзе, або першы элемент у чарзе. З стэк, мы змаглі адсочваць элемент, які мы збіраліся атрымаць, або на вяршыні стэка, выкарыстоўваючы толькі памер, у той час як з чаргой, мы мець справу з процілеглых канцоў. Мы спрабуем трэка рэчы на ​​канцы, а затым вярнуць рэчы з фронту. Такім чынам, эфектыўна, з галавой, у нас ёсць індэкс пачатку чарзе, і памер дае нам індэкс канца чаргі так што мы можам атрымаць рэчы з галавы і дадаць рэчы на ​​хвасце. У той час як з стэкам, мы былі толькі калі-небудзь справу з вяршыні стэка. Мы ніколі не мелі доступу да ніжняй часткі стэка. Мы толькі дадалі рэчы на ​​верхнія і ўзяў рэчы з верхняй так што нам не трэба, што дадатковыя поля ўнутры нашай структуры. Ці значыць гэта наогул сэнс? Добра. Так, Шарлота? [Charlotte, неразборліва] [Хардисон] Гэта вялікае пытанне, а што было адно, што прыйшлі ў лекцыі. Можа быць, ідучы праз некалькі прыкладаў праілюстраваць, чаму Мы не хочам, каб выкарыстоўваць радкі [0] у якасці кіраўніка чарзе. 

Такім чынам, уявіце, што ў нас ёсць чарга, мы будзем называць яго чарга. У пачатку, калі мы толькі што створаны ён, калі мы толькі абвясцілі яго, мы не ініцыялізаваны нічога. Гэта ўсё фігня. Таму, вядома, мы хочам пераканацца, што мы ініцыялізуем і памер, і кіраўнік поля роўна 0, то разумна. Мы таксама маглі б пайсці далей і обнулять элементы ў нашай чарзе. А каб гэтая схема падыходзіць, заўважыў, што цяпер наша чаргу можа мець толькі трох элементаў; у той час як наш стэк можа правесьці чатыры, наша чаргу можа мець толькі тры. І гэта толькі каб зрабіць схему патрэбным. Першае, што тут адбываецца, што мы пастаноўкі ў чаргу радка "прывітанне". І гэтак жа, як мы гэта рабілі са стэкам, нічога не страшна тут па-іншаму, мы кідаем радкі, па меншай радкі [0] і павялічваем наш памер на 1. Мы пастаноўкі ў чаргу "да пабачэння", яна будзе надзець. Так гэта выглядае як чарка па большай частцы. Мы пачалі тут, новы элемент, новы элемент, памерам працягвае ісці ўверх. Што адбываецца ў гэты момант, калі мы хочам нешта з чаргі? Калі мы хочам з чаргі, якая з'яўляецца элементам, які мы хочам з чаргі? [Васіль] струнных [0]. >> Zero. Цалкам дакладна, Васіль. Мы хочам, каб пазбавіцца ад першага радка, на гэты раз, "прывітанне". Так што ж іншая рэч, якая змянілася? Звярніце ўвагу, калі мы нешта выскачыў з стэка, мы проста змянілі памер, але тут, у нас ёсць пара рэчаў, якія змяняюцца. Не толькі змяніць памер, але кіраўнік зменаў. Гэта вяртаючыся да кропкі Шарлоты раней: чаму мы павінны гэта галава, а? Ці мае сэнс зараз, Шарлота? >> Накшталт таго. [Хардисон] Выгляд? Так што ж адбылося, калі мы з чаргі? Што ж кіраўнік зрабіць гэта цяпер цікава? [Charlotte] О, таму што яна змянілася - усё ў парадку. Разумею. Таму што галава - дзе галава паказвае на змены ў плане размяшчэння. Гэта ўжо не заўсёды нулявога азначніка. >> Так, менавіта так. Тое, што адбылося, калі dequeueing высокага элемента было зроблена, і ў нас не было гэтай кіраўніка поля таму што мы заўсёды называў гэты радок у 0 індэкс кіраўнік нашай чарзе, тады мы павінны перайсці астатнія чарзе ўніз. Мы павінны перайсці "да пабачэння" з з радкоў [1] радкі [0]. І радкоў [2] аж да радка [1]. І мы павінны зрабіць гэта, каб увесь спіс элементаў, Увесь масіў элементаў. І калі мы робім гэта з дапамогай масіва, які атрымлівае вельмі дорага. Дык вось, гэта не мае вялікага значэння. Мы проста павінны трох элементаў у масіве. Але калі ў нас была чарга з тысяч элементаў або мільён элементаў, а затым усё раптоўна, мы пачынаем рабіць кучу з чаргі называе ўсё ў цыкле, рэчы сапраўды збіраецца запавольвацца, як ён перакладае ўсе ўніз пастаянна. Вы ведаеце, перакласці на 1, зрух на 1, зрух на 1, зрух на 1. Замест гэтага, мы выкарыстоўваем гэтую галаву, мы называем гэта "паказальнік", хоць гэта не зусім паказальнік У строгай сэнсе, гэта не тып паказальніка. Гэта не Int * ці сімвал * ці што-небудзь падобнае. Але гэта ўказанні або з указаннем кіраўніка нашай чаргі. Да? 

[Студэнт] Як йедиеие ведаць, каб проста паліць усё, што ў галаву? [Хардисон] Як йедиеие ведаю, як паліць усё гэта ў галаве? >> Так, так. >> Што яна глядзіць на толькі што галава поле ўстаноўлена. Такім чынам, у першым выпадку, калі мы паглядзім прама тут, нашы галовы роўная 0, індэкс 0. >> Праве. [Хардисон] Так што гэта проста кажа, добра, добра, элемент з індэксам 0, радок "прывітанне", з'яўляецца элементам на чале нашай чаргі. Такім чынам, мы збіраемся з чаргі гэтага хлопца. І гэта будзе элемент, які атрымлівае вярнуліся да абаненту. Так, Саад? >> Так кіраўнік у асноўным задае - дзе вы збіраецеся індэксаваць? Вось пачатак гэтага? >> Так. >> Добра. [Хардисон] Гэта становіцца новым пачаткам для нашага масіва. Такім чынам, калі вы нешта з чаргі, усё што вам трэба зрабіць, гэта атрымаць доступ да элемента па індэксе q.head, і гэта будзе элемент, які вы хочаце з чаргі. Вы таксама павінны памяншаць памер. Мы ўбачым у біт, дзе ўсё становіцца крыху больш складана з гэтым. Мы з чаргі, і цяпер, калі мы зноў паставіць у чаргу, дзе ж мы паставіць у чаргу? Дзе наступнага элемента пайсці ў нашай чарзе? Скажам, мы хочам паставіць у чаргу радка "CS". У якой індэкс ён пойдзе? [Студэнты] струнных [2]. Два >>. Чаму на 2, а не 0? [Васіль] Таму што цяпер галава 1, так што падобна на пачатак спісу? [Хардисон] Дакладна. А што пазначае канец спісу? Што мы выкарыстоўваем для абазначэння канца нашай чарзе? Галава кіраўнік нашай чэргі, у пачатку нашай чаргі. Што ў канцы нашай чарзе? [Студэнты] Size. >> Памер, дакладна. Такім чынам, нашы новыя элементы пайсці, па меншай памер, і элементы, якія мы узлятаем адарвацца на галаву. Калі мы пастаноўкі ў чаргу на наступны элемент, мы змяшчаем яго ў ў памерах. [Студэнт] Перад тым, як пакласці, што ў, хоць, памер складаў 1, дакладна? [Хардисон] Дакладна. Так што не зусім па памеры. Памер +, а не +1, але + галава. Таму што мы перайшлі ўсе па галаве сумы. Дык вось, зараз у нас ёсць чарзе памерам 1, які пачынаецца з індэксам 1. Хвост індэкс 2. Да? 

[Студэнт] Што адбываецца, калі вы з чаргі радкі [0], і радкі 'слотаў памяці проста атрымаць апусцелі, у асноўным, або проста забыліся? [Хардисон] Так. У гэтым сэнсе, мы проста забыліся іх. Калі б мы былі захоўвання копій іх - многія структуры дадзеных часта захоўваюць свае ўласныя копіі элементаў так што чалавек кіруе структурай дадзеных не трэба турбавацца пра тое, дзе ўсе гэтыя паказальнікі збіраюцца. Структура дадзеных выконваецца на ўсім, праводзіць на ўсіх копіях, каб пераканацца, што ўсё захоўваецца належным чынам. Тым не менш, у дадзеным выпадку, гэтыя структуры дадзеных толькі для прастаты, не робім копіі за ўсё, што мы захоўванні ў іх. [Студэнт] Дык гэта бесперапынны масіў -? >> Так. Калі мы азірнемся на тое, што вызначэнне было гэтай структуры, гэта так. Гэта ўсяго толькі стандартны набор, як вы бачылі, масіў сімвалаў S *. Ці значыць гэта -? >> Так, мне было проста цікава калі вы ў канчатковым выніку запусціць з памяці, у пэўнай ступені, калі ў вас ёсць усе гэтыя пустыя месцы ў вашым масіве? [Хардисон] Так, гэта добрая кропка. 

Калі мы паглядзім на тое, што адбылося цяпер у гэтай кропцы, мы запоўнілі нашы чарзе, як ён выглядае. Але мы сапраўды не запоўнены нашымі чарзе таму што ў нас чарга гэта памер 2, але ён пачынаецца з індэкса 1, таму што там нашы галовы паказальнік. Як вы казалі, што элемент радкі [0], індэкс 0, на самай справе не існуе. Гэта не ў нашай чарзе больш. Мы проста не папрацавалі пайсці і перапісаць яго, калі мы яго з чаргі. Таму, нават калі гэта выглядае як мы запускаем з памяці, мы на самай справе не маюць. Гэтае месца даступна для нас, каб выкарыстаць. Адпаведнае паводзіны, калі б мы спрабавалі і першы з чаргі нешта падабаецца "да пабачэння", што б поп спаткання з. Зараз наша чарга пачынаецца з індэксам 2 і мае памер 1. І зараз, калі мы будзем спрабаваць паставіць у чаргу зноў нешта, скажам, 50, 50 павінны ісці ў гэтае месца з індэксам 0 таму што ён па-ранейшаму даступныя для нас. Так, Саад? [Саад] Ці значыць гэта адбывацца аўтаматычна? [Хардисон] Гэта не адбываецца цалкам аўтаматычна. Вы павінны зрабіць матэматыку каб прымусіць яго працаваць, але па сутнасці тое, што мы зрабілі, мы толькі абгорнуты вакол. [Саад] І гэта добра, калі гэта мае адтуліну ў сярэдзіне гэтага? [Хардисон] Гэта калі мы можам зрабіць матэматыку працаваць належным чынам. 

І аказваецца, што гэта на самай справе не так ужо цяжка зрабіць з модом аператара. Гэтак жа, як мы гэта рабілі з Цэзарам і матэрыял крыпта, выкарыстанне мода, мы можам дамагчыся, каб абгарнуць вакол і працягваць ісці вакол ды каля і вакол нашай чарзе, падтрыманню, што галава паказальнік перасоўвацца. Звярніце ўвагу, што памер заўсёды павазе колькасць элементаў на самай справе ў чарзе. І гэта толькі галава паказальнік, які трымае ровары праз. Калі мы паглядзім на тое, што адбылося тут, калі мы вернемся да пачатку, і вы толькі паглядзіце, што адбываецца ў галаве Калі мы нешта паставіць у чаргу, нічога не здарылася з галавой. Калі мы ў чарзе нешта яшчэ, нічога не здарылася з галавой. Як толькі мы нешта з чаргі, галава ідзе ўверх на адну. Мы ў чарзе нешта, нічога не адбываецца ў галаве. Калі мы нешта з чаргі, раптам галава атрымлівае прырашчэнне. Калі мы нешта паставіць у чаргу, нічога не адбываецца ў галаве. 

Што адбудзецца ў гэты момант, калі б мы з чаргі зноў нешта? Любыя думкі? Што будзе з галавой? Што павінна адбыцца ў галаву калі б мы з чаргі нешта яшчэ? Галава прама цяпер з індэксам 2, Гэта азначае, што кіраўнік чаргу радкоў [2]. [Студэнт] Які вяртае 0? >> Яна павінна вяртаць 0. Варта абгарнуць вакол спіны, дакладна. Да гэтага часу, кожны раз, калі мы тэлефанавалі з чаргі, мы былі дадаўшы да яго адзін у галаву, дадаць да галавы, дадайце адзін у галаву, дадайце адзін у галаву. Як толькі што галава паказальнік трапляе на апошні індэкс ў масіве, Затым мы павінны абгарнуць яго назад да пачатку, вярніцеся да 0. [Charlotte] Што вызначае здольнасць чэргі ў стэку? [Хардисон] У гэтым выпадку, мы проста выкарыстоўвалі # вызначана пастаянная. >> Добра. [Хардисон] У рэальным. Файл C, вы можаце пайсці і скінуць з яе трохі і зрабіць гэта як вялікі або як мала, як вы хочаце. [Charlotte] Такім чынам, калі вы робіце гэта чарзе, як вы робіце кампутара ведаю наколькі вялікі Вы хочаце, каб стэк быць? [Хардисон] Гэта вялікае пытанне. Ёсць некалькі спосабаў. Адным з іх з'яўляецца проста вызначыць яго пярэдняя і сказаць, што гэта будзе чарзе, якая мае 4 элемента або 50 элементаў або 10.000. Іншы спосаб зрабіць тое, што людзі, хакер выданне робіць і стварыць функцыі, каб ваша чаргу дынамічна расці, як іншыя рэчы дадаюцца цалі 

[Charlotte] Так, каб пайсці з першым варыянтам, які сінтаксіс вы выкарыстоўваеце паказаць праграме, што памер чарзе? [Хардисон] Ah. Такім чынам, давайце з гэтага. Я ўсё яшчэ ў stack.c тут, так што я проста хачу, каб пракруціць да самага верху тут. Вы можаце ўбачыць гэта прама тут? Гэта # вызначыць ёмістасць 10. І гэта амаль дакладна такі ж сінтаксіс, які мы маем для чэргі. За выключэннем чаргу, мы атрымалі, што дадатковае поле структуры тут. [Charlotte] О, я думаў, што магутнасць азначае здольнасць да радка. [Хардисон] Ah. >> Што гэта максімальная даўжыня слова. >> Ёсць. Так. Ёмістасць тут - гэта выдатная кропка. І гэта нешта, што складана таму што мы абвясцілі тут масіў сімвалаў S *. Масіў паказальнікаў. Гэта масіў знакаў. Гэта, напэўна, тое, што вы бачылі, калі вы былі вашы аб'явы буфераў для файлавага ўводу / вываду, калі вы стваралі радкі ўручную ў стэку. Аднак тое, што мы маем тут уяўляе сабой масіў сімвалаў S *. Так што гэта масіў паказальнікаў. На самай справе, калі мы маштаб, і мы паглядзім, што тут адбываецца У прэзентацыі, вы бачыце, што фактычныя элементы, характар ​​дадзеных не захоўваецца ў масіве сябе. Што захоўваецца ў нашым масіве тут з'яўляюцца паказальнікамі на знакавыя дадзеныя. Добра. Такім чынам, мы бачылі, як памер чарзе такі ж, як са стэкам, Памер заўсёды з павагай ставіцца да ліку элементаў у цяперашні час у чарзе. Пасля таго, як 2 ставіць у чаргу, памер 2. Пасля таго, як з чаргі памеры Зараз 1. Пасля таго, як іншы пастаноўкі ў чаргу Памер назад да 2. Так што памер, безумоўна паважае лік элементаў у чарзе, , А затым галаву проста трымае на ровары. Гэта ідзе ад 0-1-2, 0-1-2, 0-1-2. І кожны раз, калі мы называем з чаргі, кіраўнік атрымлівае паказальнік павялічыцца да наступнага індэксе. І калі галава збіраецца пераходзіць, ён вяртаецца назад каля 0. Так з гэтым, мы можам напісаць функцыю з чаргі. І мы збіраемся пакінуць функцыю пастаноўкі ў чаргу для вас, хлопцы, а не для рэалізацыі. 

Калі мы з чаргі элемента з нашай чарзе, тое, што было першае, што зрабіў Данііл, калі мы пачалі пісаць поп-функцыі для стэкаў? Дай мне пачуць ад каго-небудзь, хто не казаў яшчэ. Давайце паглядзім, Саад, ты памятаеш, што Даніэль зрабіў так, як першае, што калі ён пісаў поп? [Саад] Там было, гэта было - >> Ён выпрабаваў нешта. [Саад] Калі памер больш, чым 0. >> Менавіта так. І тое, што было, што тэставанне на? [Саад] Гэта было выпрабаванне, каб паглядзець, ці ёсць што-небудзь ўнутры масіва. [Хардисон] Так. Менавіта так. Такім чынам, вы не можаце поп што-небудзь з стэка, калі яна пустая. Акрамя таго, вы не можаце нічога з чаргі з чаргі, калі яна пустая. Што такое першае, што мы павінны зрабіць у нашай йедиеие функцыі тут, як вы думаеце? [Саад] Калі памер больш 0? >> Так. У гэтым выпадку, я на самой справе проста правяраў, каб убачыць, калі яна роўная 0. Калі ён роўны 0, мы можам вярнуцца нулявы. Але дакладна такая самая логіка. І давайце працягнем з гэтым. Калі памер не роўны 0, дзе знаходзіцца элемент, які мы хочам з чаргі? [Саад] У галаве? >> Менавіта так. Мы можам проста ўзяць і выняць першы элемент у нашай чэргі пры звароце да элемента ў галаву. Нічога не вар'ят. Пасля гэтага, што мы павінны рабіць? Што павінна адбыцца? Якая была іншая рэч, пра якія мы казалі ў йедиеие? Дзве рэчы павінны адбыцца, таму што наша чаргу змяніўся. [Данііл] Памяншэнне памеру. >> Мы павінны паменшыць памер і павялічыць галаву? Менавіта так. Для павелічэння галавы, мы не можам слепа павялічыць галаву, памятаю. Мы не можам проста зрабіць queue.head + +. Мы павінны таксама ўключаць гэты мод па магутнасці. І чаму мы мода на магутнасць, Stella? [Stella] Таму што ён мае, каб абгарнуць вакол. >> Менавіта так. Мы мод па магутнасці, паколькі яна мае абгарнуць назад да 0. Дык вось, на дадзены момант, мы можам рабіць тое, што сказаў Дэніэл. Мы можам памяншаць памер. І тады мы можам проста вярнуць элемент, які быў у пачатку чарзе. Гэта выглядае роду вуглаваты на першы погляд. Вы можаце ёсць пытанне. Прабачце? 

[Сэм] Чаму гэта спачатку ў пачатак чаргі? Дзе гэта пайсці? [Хардисон] Яно адбываецца ад чацвёртай радку знізу. Пасля таго як мы праверыць, каб пераканацца, што наша чаргу не пустая, Мы выцягнуць з * Па-першае, мы выцягнуць элемент, які сядзіць на чале індэкса нашага масіва, нашы радкоў масіва, >> і выклік, які ў першую чаргу? [Хардисон] І мы называем гэта ў першую чаргу. Так. Проста сачыць за што, чаму вы думаеце, мы павінны былі гэта зрабіць? [Сэм] кожнай першай проста вяртанне q.strings [q.head]? >> Так. >> Таму што мы робім гэта змена q.head з модом функцыі, і няма ніякага спосабу зрабіць гэта ў зваротнай лініі таксама. [Хардисон] Менавіта так. Ты пляма на. Сэм цалкам месцам на. Прычына мы павінны былі выцягнуць першы элемент у нашай чэргі і захаваць яго ў зменную таму, што гэта лінія, дзе мы толькі што q.head, ёсць мод аператара там не тое, што мы можам зрабіць і яна ўступіць у сілу на галаве без - у адну лінію. Такім чынам, мы на самай справе трэба выцягнуць першы элемент, а затым наладзіць галаву, змяніць памер, а затым вярнуць элемент, які мы выцягнулі. І гэта тое, што мы ўбачым прыдумалі пазней звязаныя спісы, як мы пагуляць з імі. Часта, калі вы вызваленні або ўтылізацыі звязаныя спісы Вы павінны памятаць, наступны элемент, наступны паказальнік звязаны спіс Перад утылізацыяй бягучага. Таму што ў адваротным выпадку вы выкінеце інфармацыю аб тым, што засталося ў спісе. Зараз, калі вы ідзяце ў прыбор, вы адкрыеце queue.c--х з гэтага. Так што, калі я адкрываю queue.c, дазвольце мне павялічыць тут, Вы ўбачыце, што ў вас ёсць падобны выгляд файла. Падобныя выгляд файла, што мы мелі раней з stack.c. У нас ёсць наша структура для чэргі вызначаецца гэтак жа, як мы бачылі на слайдах. 

У нас ёсць паставіць у чаргу функцыю, якая для вас зрабіць. А ў нас з чаргі функцый тут. Йедиеие функцыі ў файле нявыкананымі, Але я пакладу яго назад на PowerPoint, так што вы можаце ўвесці яго, калі вы хочаце. Такім чынам, на працягу наступных 5 хвілін або каля таго, вы, хлопцы працуюць на пастаноўкі ў чаргу якая амаль прама процілеглая з чаргі. Вы не павінны рэгуляваць галаву, калі вы enqueueing, але тое, што вы павінны наладзіць? Памер. Такім чынам, калі вы пастаноўкі ў чаргу, галава застаецца некранутай, памер не мяняецца. Але для гэтага трэба крыху - вам давядзецца пагуляць з гэтым мод , Каб высветліць дакладна, што індэкс новага элемента павінна быць устаўлены ст. Таму я дам вам, хлопцы трохі, паклаў назад з чаргі на слайдзе, і як вы, хлопцы, ёсць пытанні, крычаць іх, так што мы можам ўсе размовы аб іх як аб групе. Акрамя таго, з памерам вы не - пры наладзе памеру, вы заўсёды можаце проста - Вы павінны мода памер калі-небудзь? [Данііл] Няма >> Вы не павінны мода памеру, маеце рацыю. Паколькі памер будзе заўсёды, калі вы - мяркуецца, што вы ўсё правільна кіраваць, Памер заўсёды будзе паміж 0 і 3. Дзе вы павінны мода, калі вы робіце пастаноўкі ў чаргу? [Студэнт] Толькі для галавы. >> Толькі за галаву, дакладна. І чаму вы павінны мода на ўсе пастаноўкі ў чаргу? Калі сітуацыя, у якой вам давядзецца мода? [Студэнт] Калі ў вас ёсць рэчы ў прасторы, як на прасторах 1 і 2, , А затым вам трэба дадаць нешта ў 0. [Хардисон] Так, менавіта так. Такім чынам, калі ваша галава паказальнік знаходзіцца ў самым канцы, або калі ваш памер плюс ваша галава больш, або, хутчэй, будзе абгарнуць вакол чэргі. 

Такім чынам, у гэтай сітуацыі, што мы атрымалі тут, на слайдзе прама зараз, калі я хачу нешта паставіць у чаргу прама зараз, Мы хочам паставіць у чаргу нешта па індэксе 0. Так што калі вы паглядзіце, дзе ў 50 ідзе, і я заклікаю епдиеие 50, яна ідзе там на дне. Ён ідзе ў індэкс 0. Ён замяняе «прывітанне», якая ўжо была выдаленая з чаргі. [Данііл] Не вы клапоціцеся аб тым, што ў йедиеие ўжо? Чаму ён нічога зрабіць з галавой пастаноўкі ў чаргу? [Хардисон] Ах, так вы не змяніўшы галавой, прабачце. Але вы павінны выкарыстоўваць мод аператара, калі вы звяртаецеся элемент, які вы хочаце паставіць у чаргу, калі вы звяртаецеся Наступны элемент у чарзе. [Васіль] я гэтага не зрабіў, і я атрымаў "Поспех" там. [Данііл] О, я разумею, што вы кажаце. [Хардисон] Такім чынам, вы didn't - вы толькі што зрабілі ў q.size? [Васіль] Так. Я проста перайшла на іншы бок, я нічога не рабіў з галавой. [Хардисон] Вы на самой справе не маюць для скіду галавой быць што заўгодна, але калі вы індэкс ў масіве радкоў, Вы на самой справе трэба ісці наперад і вылічыць, дзе наступны элемент, таму што лаза стэка, наступны элемент у стэку заўсёды была на індэкс, які адпавядае памер. Калі мы азірнемся назад у нашым функцыяй націску стэка, Мы заўсёды мог шпурнуць у нашым новым элеменце права на памер індэкса. У той час як з чаргой, мы не можам зрабіць гэта таму што, калі мы ў гэтай сітуацыі, калі мы ў чарзе 50 нашых новая радок будзе ісці прама на радкі [1] якія мы не хочам рабіць. Мы хочам, каб новая радок пайсці на індэкс 0. 

Хто-небудзь - так? [Студэнт] У мяне ёсць пытанне, але гэта на самай справе не звязаныя паміж сабой. Што гэта значыць, калі хтосьці проста выклікае нешта накшталт PRED паказальнік? Што гэта назва скарочана? Я ведаю, гэта проста назва. [Хардисон] Pred паказальнік? Давайце паглядзім. У якім кантэксце? [Студэнт] Гэта было для ўстаўкі. Я магу задаць вам пазней, калі вы хочаце таму што гэта на самай справе не звязаныя, але я проста - [Хардисон] З ўстаўкі кода Давід з лекцыі? Мы можам цягнуць, што і казаць пра гэта. Мы пагаворым пра гэта ў наступны, як толькі мы дабяромся да звязаных спісаў. 

Так што давайце сапраўды хутка зірнуць на тое, што функцыя пастаноўкі ў чаргу выглядае. Якой была першая рэч, якую людзі спрабавалі зрабіць у вашай пастаноўкі ў чаргу радкі? У гэтай чарзе? Як і тое, што вы зрабілі для стэка націскам. Што вы рабілі, Стэла? [Stella, неразборліва] [Хардисон] Менавіта так. Калі (q.size == ёмістасці) - Мне трэба паставіць маю дужкі ў патрэбным месцы - вярнуцца ілжывым. Павялічыць няшмат. Добра. Цяпер тое, што наступная рэч, якую мы павінны былі зрабіць? Гэтак жа, як з стэкам, і ўстаўляецца ў патрэбнае месца. І тое, што было ў патрэбным месцы, каб ўставіць гэта? З стэк гэта быў памер індэкса, з гэтым не зусім так. [Данііл] У мяне ёсць q.head--ці - q.strings? >> >> Так. q.strings [q.head + q.size мод якасці]? [Хардисон] Мы, верагодна, хочуць паставіць дужкі вакол гэтага так што мы атрымліваем адпаведны прыярытэт і так вось cleart для ўсіх. І ўстаноўлена, што роўныя? Каб >> вул? Каб >> вул. Вялікі. А зараз тое, што апошняя рэч, якую мы павінны зрабіць? Гэтак жа, як мы гэта рабілі ў стэку. >> Прырашчэнне памеру? >> Прырашчэнне памеру. Boom. А затым, паколькі стартавы код толькі што вярнуўся ілжывай па змаўчанні, Мы хочам змяніць гэта дакладна, калі ўсё праходзіць і ўсё ідзе добра. Добра. Гэта вельмі шмат інфармацыі для часткі. Мы не зусім скончана. Мы хочам казаць пра сапраўды хутка односвязный спісы. Я пакладу гэта так, мы можам вярнуцца да яго пазней. Але давайце вернемся да нашай прэзентацыі ўсяго за некалькі слайдаў. Так епдиеие з'яўляецца TODO, зараз мы зрабілі гэта. 

Зараз давайце зірнем на односвязный спісы. Мы гаварылі пра гэта трохі больш у лекцыі. Як многія з вас, хлопцы ўбачылі дэма, дзе ў нас былі людзі няёмка паказваючы адзін да аднаго і правядзенне лічбы? >> Я была ў гэтым. >> Што вы думаеце, хлопцы? Хіба што, як мы спадзяемся растлумачыць гэта трохі? У спісе, то атрымліваецца, што мы маем справу з гэтым тыпам, які мы будзем называць вузлом. У той час як з чаргой і стэкам ў нас былі структуры, якія мы назвалі б чэргі ў стэку, у нас былі гэтыя новыя чэргі ў стэку тыпу, Тут спіс на самай справе проста складаецца з кучу вузлоў. Такім жа чынам, што радкі проста набор знакаў ўсе сталі побач адзін з адным. Звязаны спіс усяго вузла і іншай вузел, а другі вузел, а другі вузел. І замест таго, разбіўшы усе вузлы разам, і захоўваць іх бесперапынна ўсё побач адзін з адным у памяці, з гэтай наступны паказальнік дазваляе захоўваць вузлах, дзе, у выпадковым парадку. А потым накшталт правадоў іх усё разам, каб паказаць ад аднаго да іншага. 

І тое, што было вялікім перавагай, што гэта было больш чым масіў? За захоўванне ўсе бесперапынна проста затрымаўся побач адзін з адным? Вы памятаеце? Да? >> Дынамічнае размеркаванне памяці? >> Дынамічнае размеркаванне памяці ў якім сэнсе? [Студэнт], што вы можаце зрабіць яго яшчэ больш, і вы не павінны перамясціць ўвесь масіў? [Хардисон] Менавіта так. Такім чынам, з масівам, калі вы хочаце паставіць новы элемент у сярэдзіне, Вы павінны перайсці усё, каб вызваліць месца. І, як мы гаварылі з чаргой, Вось чаму мы трымаем галаву, што паказальнік, так што мы не пастаянна змяняюцца рэчы. Таму што становіцца дарагім, калі ў вас ёсць вялікі масіў і вы ўвесь час робіце гэтыя выпадковыя ўстаўкі. У той час як са спісам, усё што вам трэба зрабіць, гэта выкінуць яго на новы вузел, наладзіць паказальнікі, і вы зрабілі. Што смокча з гэтай нагоды? Акрамя таго, што гэта не так проста, як працаваць з масівам? Да? [Данііл] Ну, я думаю, гэта значна цяжэй атрымаць доступ да пэўнага элементу ў звязаным спісе? [Хардисон] Вы не можаце проста перайсці да адвольнага элементу ў сярэдзіне вашага звязанага спісу. Як вы павінны гэта зрабіць замест гэтага? >> Вы павінны пакрокава ўсю рэч. [Хардисон] Так. Вы павінны прайсці па адным, па адным за раз. Гэта велізарная - гэта боль. Што з іншага - ёсць яшчэ адзін крушэнне да гэтага. [Васіль] Вы не можаце пайсці наперад і назад? Вы павінны ісці ў адным кірунку? [Хардисон] Так. Так як жа нам вырашыць, што часам? [Васіль] двунакіраванага спісаў? >> Менавіта так. Ёсць двойчы звязаныя спісы. Ёсць таксама - шкада? 

[Сэм] Гэта тое ж самае, што і выкарыстанне PRED тое, што - Я толькі што ўспомніў, гэта не тое, што PRED рэч, гэта? Хіба гэта не паміж двух-і паасобку? [Хардисон] Давайце паглядзім, што менавіта ён робіць. Такім чынам, тут мы ідзем. Вось спіс кода. Тут мы маем predptr, тут. Гэта тое, што вы кажаце? Так што гэта было - ён вызваляючы спіс, і ён спрабуе захаваць паказальнік на яго. Гэта не двойчы, асобна звязаныя спісы. Мы можам пагаварыць пра гэта пазней, так як гэта кажа аб вызваленні спіс і я хачу паказаць некаторыя іншыя рэчы першай. але гэта проста - гэта памятаць значэнне PTR [Студэнт] О, гэта папярэдняй паказальнік? >> Так. Так што мы можам павялічыць PTR сябе, перш чым мы тады бясплатна, што з'яўляецца predptr. Паколькі мы не можам бясплатна PTR, а затым выклікаць PTR = PTR далей, ці не так? Гэта было б дрэнна. Такім чынам, давайце паглядзім, вернемся да гэтага хлопца. 

Іншыя дрэнныя рэчы пра спісах з'яўляецца тое, што ў той час як з масівам мы проста павінны ўсе самі элементы выкладзеныя побач адзін з адным, Тут мы таксама ўвялі гэты паказальнік. Так што ёсць дадатковы блок памяці, што мы звяртаючыся да выкарыстання для кожнага элемента, што мы захоўванні ў нашым спісе. Мы атрымліваем гнуткасць, але гэта звязана з пэўнымі выдаткамі. Ён пастаўляецца з гэтым выдаткі часу, і ён прыходзіць з гэтай памяццю кошт таксама. Час у тым сэнсе, што мы зараз павінны прайсці праз кожны элемент масіва каб знайсці той, з індэксам 10, або, што было б індэкс 10 у масіве. 

Проста вельмі хутка, калі мы дыяграму з гэтых спісаў, Звычайна мы праводзім на галаву спісу або першы паказальнік спісу і адзначыць, што гэта з'яўляецца сапраўдным паказальнікам. Гэта проста 4 байт. Гэта не самога вузла. Такім чынам, вы бачыце, што ён не мае цэлалікавых значэнне ў ёй, не наступнага паказальніка ў ім. Гэта літаральна паказальнік. Гэта будзе паказваць на тое, што фактычная структура вузла. [Сэм] паказальнік называецца вузел? >> Гэта - не. Гэта паказальнік на нешта тыпу вузла. Гэта паказальнік на вузел структуры. >> Ну, добра. Дыяграма злева, код справа. Мы можам ўсталяваць яго ў нуль, які з'яўляецца добрым спосабам для пачатку. Пры схеме, вы альбо напісаць яго ў якасці нулявога ці вы пакладзеце лініі, якая праходзіць праз гэта так. 

Адзін з самых простых спосабаў працы са спісамі, і мы просім Вас як дадаем і дадаем ўбачыць адрозненні паміж імі, але дадаючы, безумоўна, лягчэй. Калі вы папярэднічаць, гэта, дзе вы - калі вы дадаем (7), Вы ідзяце і стварыць вузел структуры і вы ўсталяваць першы звярнуў увагу на гэта, таму што цяпер, так як мы дадаецца яго, гэта будзе ў пачатку спісу. Калі мы дадаем (3), што стварае яшчэ адзін вузел, але цяпер 3 ідзе да 7. Такім чынам, мы істотна націскам рэчы на ​​нашым спісе. Цяпер вы можаце бачыць, што пачатак, канец, часам людзі называюць яго штурхаць, таму што вы націскаеце новы элемент на вашым спісе. Гэта таксама лёгка выдаліць ў пярэдняй частцы спісу. Такім чынам, людзі часта называюць гэта поп-музыкі. І ў гэтым выпадку, вы можаце эмуляваць стэк з дапамогай звязанага спісу. Воклічы. На жаль, зараз мы ўваходзім у дадатак. І вось мы дадаецца (7), зараз мы дадаем (3). Калі дадаецца нешта яшчэ на гэты спіс, калі мы дадаецца (4), Затым мы павінны былі б 4, а затым 3, а затым 7. І тады мы маглі б поп-і выдаліць 4, выдаліць 3, выдаліць 7. Часта больш інтуітыўны спосаб думаць пра гэта з даданне. Так што я дыяграме, што яна будзе выглядаць з дадаць тут. Тут прыкладаецца (7) не выглядае па-іншаму таму што ёсць толькі адзін элемент у спісе. І дадання (3) ставіць яго ў канцы. Можа быць, вы можаце ўбачыць прама зараз трук з даданне з'яўляецца тое, што, так як мы толькі ведаем, дзе ў пачатку спісу, дадаць у спіс, трэба прайсці ўвесь шлях да канца спісу каб дабрацца да канца, спыніць, а затым пабудаваць свой вузел і бухнуть ўсё ўніз. Злучыце ўсе рэчы ўверх. Так што з пачатак, канец, як мы толькі што разарваў гэта сапраўды хутка, Пры папярэднічаць ў спіс, гэта даволі проста. 

Вы робіце свой новы вузел, ўключаюць некаторыя дынамічнага размеркавання памяці. Такім чынам, вось што мы робім вузел структуры выкарыстаннем таНос. Так таНос мы выкарыстоўваем, таму што будзе выдзелена памяці для нас, для наступнага таму што мы не хочам гэтага - мы хочам, каб гэтая памяць захаваецца на працягу доўгага часу. І мы атрымліваем паказальнік на месца ў памяці, што мы проста вылучаныя. Мы выкарыстоўваем памер вузла, мы не падвесці поля. Мы не ўручную генераваць колькасць байтаў, замест гэтага мы выкарыстоўваем SizeOf, так што мы ведаем, мы атрымліваем адпаведную колькасць байтаў. Мы клапоцімся аб тым, каб праверыць, што наш таНос выкліку ўдалося. Гэта тое, што вы хочаце зрабіць у цэлым. На сучасных машынах, сыходзіць з памяці гэта не тое, што лёгка калі вы выдзяленні тоны матэрыялу і ўносяць вялізны спіс, Але калі вы будуеце рэчы, скажам, як iPhone або Android, ў вас ёсць абмежаванасць рэсурсаў памяці, асабліва калі вы робіце нешта інтэнсіўна. Так што гэта добра, каб атрымаць на практыцы. 

Звярніце ўвагу, што я выкарыстаў некалькі розных функцый тут што вы бачылі, што гэта свайго роду новае. Так Fprintf такі ж, як Printf акрамя яе першы аргумент з'яўляецца паток, у які вы хочаце надрукаваць. У гэтым выпадку, мы хочам, каб друкаваць на стандартную радок памылкі , Які адрозніваецца ад стандартнага outstream. Па змаўчанні яна з'яўляецца ў тым жа месцы. Яна таксама выводзіць на тэрмінал, а можна - з дапамогай гэтых каманд вы даведаліся пра, метады перанакіраваньні Вы даведаліся пра ў відэа Томі праблемай для мноства 4, Вы можаце накіроўваць яе у розных галінах, а затым выйсці, прама тут, выходзіць вашу праграму. Гэта, па сутнасці, як вяртаўся з галоўных, за выключэннем мы выкарыстоўваем выхад, таму што тут вяртанне не будзе нічога рабіць. Мы не ў асноўнай, так што вяртацца не выйсці з праграмы, як мы хочам. Таму мы выкарыстоўваем функцыю выхаду і даць яму код памылкі. Тады тут мы ўсталёўваем значэнне новага вузла поля, яго я поля роўным я, а потым падлучыць яго. Мы ўсталявалі наступны паказальнік новага вузла, каб паказаць на першы, , А затым першым будзе ўказваць на новы вузел. Гэтыя першыя радкі кода, мы фактычна будаўніцтва новага вузла. Не дзве апошнія радкі гэтай функцыі, але першы з іх. Вы сапраўды можаце выйсці ў функцыю, у дапаможную функцыю. Гэта часта, што я раблю, я выцягнуць яго ў функцыю, Я называю гэта нешта накшталт вузла зборкі, і што трымае дадаем функцыю даволі невялікі, гэта проста 3 лініі тады. Я раблю выклік маёй функцыі вузла зборкі, а потым я правады ўсё дагары. 

Апошняе, што я хачу паказаць вам, і я дам вам зрабіць даданне і ўсё, што на свой уласны, як для перабору спісу. Ёсць мноства розных спосабаў для перабору спісу. У гэтым выпадку, мы збіраемся, каб знайсці даўжыню спісу. Такім чынам, мы пачынаем з даўжынёй = 0. Гэта вельмі падобна на напісанне StrLen для радка. Гэта тое, што я хачу паказаць вам, гэта цыкл прама тут. Гэта выглядае свайго роду фанк, гэта не звычайная Int я = 0, <што заўгодна, я + +. Замест гэтага ён ініцыялізацыю нашай зменнай п будзе ў пачатку спісу. І потым, калі наш итератор зменнай не з'яўляецца нулявым, мы працягваем. Гэта таму, што, па дамове, у канцы нашага спісу будзе нулявы. І тады, каб павялічыць, а не рабіць + +, Звязаны спіс эквіваленце + + п = п-> далей. 

Я дам вам запоўніць прабелы тут, таму што мы знаходзімся па-за часам. Але майце гэта на ўвазе, як вы працуеце на psets spellr. Змяненні, спісы, калі вы рэалізуеце хэш-табліцы, , Безумоўна, вельмі зручны. І з гэтай ідыёмы цыкл над рэчамі зробіць жыццё нашмат прасцей, спадзяюся. Любыя пытанні, хутка? [Сэм] Ці будзеце вы адправіць запоўненую SLL і ПК? [Хардисон] Так. Я буду пасылаць завершана слайды і завяршыў стэк SLL і queue.cs. [CS50.TV]