[Музыка, якая іграе] СПІКЕР 1: Добра. Ўсё дабро запрашаем у профіль. Я спадзяюся, што вы ўсё паспяхова адышоў ад вашай віктарыны з мінулага тыдня. Я ведаю, што гэта крыху вар'яты ў разы. Як я ўжо казаў раней, калі вы ў межах стандартнага адхіленні, на самай справе не турбавацца пра гэта, асабліва для менш камфортным раздзеле. Вось пра тое, дзе вы павінны быць. Калі вы зрабілі вялікі, то дзіўным. Слава вам. І калі вы адчуваеце, як вам трэба трохі больш дапамогі, калі ласка, не саромейцеся, каб дасягнуць да любой з TFS. Мы ўсе тут, каб дапамагчы. Вось чаму мы вучым. Вось чаму я тут кожны панядзелак для вас Хлопцы і ў офісе гадзін па чацвяргах. Таму, калі ласка, не саромейцеся, дайце мне ведаць, калі вы турбуецеся аб чым-небудзь або калі што-небудзь на віктарыне што вы сапраўды хацелі б звярнуцца. Так парадак дня на сёння ўсё пра структурах дадзеных. Некаторыя з іх проста будзе проста каб вы азнаёміліся з імі. Вы ніколі не можаце рэалізаваць ім у гэтым класе. Некаторыя з іх вы, як для вашага SPELLER PSET. Вы будзеце мець выбар паміж хэш-табліц і спробаў. Такім чынам, мы будзем вызначана над тымі. Гэта будзе вызначана больш віду з падзелу высокі ўзровень сёння, хоць, таму што ёсць многія з іх, і калі мы пайшлі ў дэталі рэалізацыі на ўсе з іх, мы не былі б нават прайсці праз звязаныя спісы і, можа быць, трохі хэш-табліцы. Так, мядзведзь са мной. Мы не збіраемся рабіць столькі кадавання на гэты раз. Калі ў вас ёсць якія-небудзь пытанні па гэтай нагоды ці вы хочаце ўбачыць гэта рэалізуецца або паспрабаваць яго на сабе, Я вызначана рэкамендую збіраецца study.cs50.net, якія ёсць прыклады ўсіх з іх. Гэта будзе мець свае PowerPoints з заўвагамі, якія мы як правіла, выкарыстоўваюць, а таксама некаторыя праграмавання практыкаванні, асабліва для рэчаў як звязаныя спісы і бінарныя дрэвы стэкі і падказкі. Так трохі больш высокі ўзровень, які магло б быць добра для вас, хлопцы. Так з гэтым, мы пачнем. А таксама, yes-- віктарыны. Я думаю, што большасць з вас, хто ў мой раздзел ёсць свае віктарыны, але хто прыходзіць у ці нейкай прычыне вы няма, яны прама тут, у пярэдняй. Так сувязныя спісы. Я ведаю гэты від ідзе для рэзервовага перад вашай віктарыны. Гэта было за тыдзень да што мы даведаліся пра гэта. Але ў гэтым выпадку, мы проста пайсці крыху больш падрабязна. Дык чаму мы маглі б выбраць звязаны спіс па масіве? Што адрознівае іх? Так? АЎДЫТОРЫЯ: Вы можаце пашырыць звязаны спіс у параўнанні з фіксаваным памерам масіва ў. СПІКЕР 1: Права. Масіў мае фіксаваны памер у той час як Звязаны спіс мае пераменны памер. Так што, калі мы не ведаем, як шмат мы хочам захаваць, Звязаны спіс дае нам выдатны спосаб зрабіць гэта, таму што мы можам проста дадаць на іншым вузле, і дадаць на іншы вузел і дадаць на іншым вузле. Але што можа быць кампраміс? Хто-небудзь памятае кампраміс паміж масівамі і звязаныя спісы? Mmhmm? АЎДЫТОРЫЯ: Вы павінны прайсці праз усе шляху праз звязаны спіс знайсці элемент у спісе. У масіве, вы можаце проста знайсці элемент. СПІКЕР 1: Права. Так з arrays-- АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: З масівамі, у нас ёсць тое, што называецца адвольным доступам. Азначае, што калі мы хочам што альбо пятая кропка з спісу або пятая кропка нашага Масіў, мы можам проста ўзяць яго. Калі гэта звязаны спіс, у нас ёсць для перабору, ці не так? Так доступ да элемента ў Масіў з'яўляецца пастаянная часу, у той час як са звязаным спісам было б хутчэй за ўсё, будзе лінейнае час, таму што, можа быць, наш элемент цалкам у канцы. Мы павінны шукаць праз усе. Так з усімі гэтымі дадзенымі структуры, якія мы збіраемся каб марнаваць крыху больш часу на, якія плюсы і мінусы. Калі можа мы хочам выкарыстоўваць адзін над іншым? І гэта збольшага больш, што трэба забраць. Такім чынам, мы маем тут Вызначэнне вузла. Гэта як адзін з элементаў наш звязаны спіс, ці не так? Такім чынам, мы ўсе знаёмыя з нашымі ЬурейеЕ структур, якія мы разгледзелі ў аглядзе апошні раз. Гэта была ў асноўным проста стварэнне іншы тып дадзеных, якія мы маглі б выкарыстоўваць. І ў гэтым выпадку, гэта нейкая вузел што правядзе некаторы цэлае лік ст. І тады тое, што другая частка тут? Любы? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Так. Гэта паказальнік на наступны вузел. Такім чынам, гэта павінна быць на самой справе тут. Гэта паказальнік тыпу вузел да наступнай рэчы. І вось што яны ахоплівае нашу вузел. Прахладны. Добра, так з пошукам, як мы былі проста кажу, перш чым рукі, калі вы будзе шукаць праз, ў вас ёсць на самой справе ітэрацыі праз звязаны спіс. Так што, калі мы шукаем колькасці 9, мы б пачаць у нашай галаве і што паказвае нам на пачатку нашай звязанага спісу, ці не так? І мы кажам: добра, робіць гэта вузел ўтрымлівае лік 9? Няма? Добра, ідзі да наступнага. Выконвайце яго. Ўтрымлівае Ці яна лік 9? Няма. Выконвайце наступны. Так што мы павінны на самай справе ітэрацыі праз нашу звязанага спісу. Мы не можам проста пайсці проста туды, дзе 9. І калі вы, хлопцы, на самай справе хочаце, каб ўбачыць некаторыя псеўда-код там. У нас ёсць функцыя пошуку тут што бярэ in-- што ж трэба ў? Што ты думаеш? Так лёгкім. Што гэта? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: мы шукаем лік. Ці не так? І што б гэта адпавядаць? Гэта паказальнік на? АЎДЫТОРЫЯ: вузел. СПІКЕР 1: вузел у спіс што мы глядзім на, ці не так? Таму ў нас ёсць некаторыя вузлы паказальнік тут. Гэта кропка, што збіраецца на самай справе перабору нашым спісе. Мы ўсталёўваем яго роўным спіс таму што гэта проста мяркуючы яго роўным пачаць нашага звязанага спісу. І ў той час як гэта не NULL, у той час як у нас яшчэ ёсць рэчы ў нашым спісе, праверце, калі гэты вузел мае лік мы шукаем. Вярнуцца праўда. У адваротным выпадку, абновіце яго, ці не так? Калі гэта NULL, мы выходзім з нашага у той час як цыкл і вярнуцца ілжывым таму што гэта азначае, што мы не знайшлі яго. Ці ўсё атрымаць, як гэта працуе? Добра. Так з ўстаўкі, вы ёсць тры розных спосабу. Вы можаце папярэднічаць, вы можаце дадаць і вы можаце ўставіць у асарці. У гэтым выпадку, мы збіраюся рабіць препендом. Хто-небудзь ведае, як тыя, тры выпадкі могуць адрознівацца? Так перад імем азначае, што вы паклалі гэта ў пярэдняй часткі вашага спісу. Так што гэта будзе азначаць, што незалежна ад таго, што ваш вузел, незалежна ад таго, што значэнне, што вы збіраецеся паставіць яго прама тут, перад, ОК? Гэта будзе першы элемент у спісе. Калі вы дадаеце яго, гэта будзе ісці да задняй частцы спісу. І ўставіць у асарці азначае, што вы збіраецца паставіць на самай справе ў тое месца, дзе ён трымае ваш звязаны спіс адсартаваны. Зноў жа, як вы карыстаецеся тыя, і калі вы карыстаецеся ім будзе вар'іравацца ў залежнасці ад вашага выпадку. Калі гэта не трэба сартаваць, перад імем, як правіла, быць тым, што большасць людзей выкарыстоўваць, таму што вы не павінны прайсці праз увесь спіс каб знайсці канец, каб дадаць яго на, ці не так? Вы можаце проста прытрымлівацца яго прама ў. Так што мы будзем праходзіць праз ўстаўка 1 прама цяпер. Так што тое, што я збіраюся вельмі рэкамендую на гэтым PSET з'яўляецца прыцягненне рэчы, як заўсёды. Гэта вельмі важна, што вы абнаўляеце Вашы ўказальнікі ў правільным парадку таму што, калі вы абнаўляеце іх крыху не ў парадку, Вы будзеце ў канчатковым выніку страты часткі вашага спісу. Так, напрыклад, у дадзеным выпадку, мы кажа кіраўнік проста навесці на 1. Калі мы проста робім, што без захавання гэтага 1, мы паняцця не маем, што 1 варта паказаць на зараз таму што мы страцілі тое, што Кіраўнік паказаў на. Так адна справа памятаць калі вы робіце препендом гэта, каб выратаваць тое, што галава паказвае на першы, затым перапрызначыць яго, а затым абнавіць што ваш новы вузел павінен паказваць на. У гэтым выпадку, гэта адзін са спосабаў зрабіць гэта. Так што, калі б мы зрабілі гэта такім чынам дзе мы проста пераназначаны галаву, мы губляем у асноўным наша Увесь спіс, ці не так? Адзін са спосабаў зрабіць гэта, каб мець 1 пункт да Далей, а затым галоўкі кропку 1. Ці вы можаце зрабіць выгляд, як часовага захоўвання, якія я казаў пра. Але перапрызначэння праграмы Your ўказальнікі ў правільным парадку будзе вельмі, вельмі важна для гэтай PSET. У адваротным выпадку, вы будзеце мець хэш табліцы або паспрабаваць што проста будзе толькі частка словы, якія вы хачу і тое you're-- mmhmm? АЎДЫТОРЫЯ: Што было часовае захоўвання, што вы казалі? СПІКЕР 1: часовае захоўванне. Таму ў асноўным іншы як вы маглі б зрабіць гэта будзе захоўваць кіраўніка тое, як захоўваць яму часовую зменную. Прызначаюць яго па 1 і затым абнавіць 1 да кропкі да таго, што кіраўнік выкарыстоўваецца, каб паказаць на. Такім чынам, відавочна, больш элегантным, таму што вас ня трэба часовае значэнне, але проста прапаноўваючы яшчэ адзін спосаб зрабіць гэта. І мы, сапраўды ёсць некаторы код для гэтага. Так што для звязанага спісу, мы на самай справе ёсць некаторы код. Так, перанясіце сюды, гэта папярэднічаючы. Так што гэта ўваходзіць у яго ў галаве. Так першая рэч, вы павінны стварыць новы вузел, вядома, і праверыць на NULL. Заўсёды добра. І тады вам трэба прысвоіць значэння. Кожны раз, калі вы ствараеце новы вузел, вам не ведаю, што гэта, паказваючы на ​​наступны, так што вы хочаце, каб ініцыялізаваць яго, каб NULL. Калі гэта ў канчатковым выніку паказваючы на ​​нешта яшчэ, ён атрымлівае пераназначаны, і гэта выдатна. Калі гэта першае, што у спісе, ён павінен паказваць на NULL, таму што што гэта канец спісу. Такім чынам, каб ўставіць яго, мы бачым тут мы прысвойваем наступны каштоўнасць нашага вузла быць усё, што галава, якая з'яўляецца тое, што мы мелі тут. Гэта тое, што мы толькі што зрабілі. І тады мы прысвойваем галаву да кропкі на наш новы вузел, таму што памятаю, Новы некаторы паказальнік на вузел, і гэта менавіта тое, што галава. Менавіта таму мы ёсць гэтая стрэлка аксессор. Прахладны? Mmhmm? АЎДЫТОРЫЯ: Ці ёсць у нас у ініцыялізаваць новы Далей, каб NULL-першае, ці мы можам проста ініцыялізаваць яго ўзначаліць? СПІКЕР 1: Новая наступны павінен быць NULL, каб пачаць таму што вы не ведаеце, дзе ён будзе. Акрамя таго, гэта свайго роду сапраўды гэтак жа як парадыгму. Вы можаце ўсталяваць яго роўным NULL проста зрабіць Пераканайцеся, што ўсе вашыя базы пакрытыя перш чым рабіць якія-небудзь перапрызначэння так, што Вы заўсёды гарантуецца, што гэта будзе паказваць на пэўнае значэнне супраць, як каштоўнасці смецця. Таму што, так, мы прысвойваем Новая наступны аўтаматычна, але гэта больш, як добрая практыка, каб ініцыялізаваць яго такім чынам, і затым перадаць. Такім чынам, двусвязного спісы цяпер. Што мы думаем? Што змянілася з двусвязного спісы? Такім чынам, у нашых звязаных спісаў, мы можам рухацца толькі ў адным накірунку, ці не так? У нас ёсць толькі побач. Мы можам ісці толькі наперад. З двунаправленный спіс, мы можам таксама рухацца ў зваротным кірунку. Такім чынам, мы маем не толькі лік, якое мы хочам захаваць, у нас ёсць, дзе ён паказвае на наступны і дзе мы толькі прыйшлі. Такім чынам, гэта дазваляе некаторыя лепш абыходу. Так ўдвая звязаныя вузлы, вельмі падобныя, ці не так? Толькі розніца ў тым, зараз мы ёсць побач і папярэдняя. Гэта адзінае адрозненне. Так што, калі б мы павінны былі папярэднічаць або append-- мы не маюць ніякага кода для гэтага да here-- але калі б вы былі, каб паспрабаваць устаўце яго, важную рэч гэта вы павінны зрабіць што вы прысваення як ваш папярэдні і вашы наступны паказальнік правільна. Такім чынам, у гэтым выпадку, вы б не толькі ініцыялізаваць побач, ініцыялізацыі папярэдняя. Калі мы знаходзімся ў пачатку спісу, мы будзе не толькі зрабіць кіраўнік роўна новы, але наш новы папярэдняя павінны паказваюць на галаве, ці не так? Вось і ўся розніца. І калі вы хочаце больш практыкі з яны са звязанымі спісамі, з ўстаўкі, з выдаленнем, з устаўкай у зборных спісу, калі ласка, азнаёмцеся з study.cs50.net. Там куча вялікіх вучэнняў. Я вельмі рэкамендую іх. Я жадаю, каб мы паспелі прайсці праз іх але ёсць шмат структур дадзеных каб прайсці. Такім чынам, хэш-табліцы. Гэта, бадай, найбольш карысна трохі для PSET тут, таму што вы збіраецеся быць рэалізацыі аднаго з іх, або спробу. Мне вельмі падабаецца, хэш-табліцы. Яны даволі халаднавата. Таму ў асноўным тое, што адбываецца гэта хэш-табліца калі нам сапраўды трэба хуткае ўстаўка, выдаленне, і пошук. Тыя рэчы, якія мы прыярытэтнасці ў хэш-табліцы. Яны могуць атрымаць даволі вялікі, але, як мы ўбачым з спроб, Ёсць рэчы, якія нашмат больш. Але ў прынцыпе, усе хэш табліца хэш-функцыя што кажа вам, якія вядро пакласці сябар Вашых дадзеных, кожны з вашых элементаў у. Просты спосаб думаць аб хэш-табліцы з'яўляецца тое, што гэта ўсяго толькі вядра рэчаў, ці не так? Такім чынам, калі вы сартавання рэчы як першую літару свайго імя, што накшталт як хэш-табліцу. Так што, калі б я быў у групе, вы, хлопцы, гэта ў групах, хто пачынае імя з тут, або той, хто дзень нараджэння у студзені, лютым, сакавіку, незалежна, гэта значыць эфектыўна стварэнне хэш-табліцу. Гэта проста стварэнне вядра, што Вы сартавання элементаў у так што вы можаце знайсці іх лягчэй. Так Такім чынам, калі мне трэба каб знайсці адзін з вас, У мяне няма да пошуку праз кожны з вашых імёнаў. Я магу быць, як, ну, я ведаю, што Дзень нараджэння Даніэль з'яўляецца in-- АЎДЫТОРЫЯ: --April. СПІКЕР 1: Красавік. Так я гляджу на мой красавіка вядро, і калі пашанцуе, яна будзе адзіным у там і мой час быў сталым у гэтым сэнсе, у той час як, калі я павінен глядзець праз цэлую кучу людзей, гэта зойме значна больш часу. Так хэш-табліцы сапраўды ўсё вядра. Лёгкі спосаб думаць пра іх. Так вельмі важная рэч аб Хэш-табліца ўяўляе сабой хэш-функцыя. Так пра што я толькі што казаў пра, як Ваша першы ліст ад вашага імя ці твой дзень нараджэння месяц, гэта ідэі, якія сапраўды карэлюе з хэш-функцыі. Гэта проста спосаб вырашыць, якія вядро Ты элемент трапляе ў, ОК? Такім чынам, для гэтай PSET, вы можаце паглядзець амаль любы хэш-функцыя вы хочаце. Не трэба быць вашым уласным. Ёсць некаторыя сапраўды класныя тыя з ёсць што рабіць усякія вар'яты матэматыцы. І калі вы хочаце, каб ваш праверка арфаграфіі супер хуткі, Я б вызначана шукаць у адным з тых. Але існуюць і простыя, як вылічальных сума словамі, як кожная літара мае свой нумар. Вылічыць суму. Гэта вызначае вядро. Яны таксама маюць лягчэй, што такія ж, як усе тут, усе B тут. Любы з іх. У асноўным, гэта проста кажа вам, якія Індэкс масіва ваш элемент павінен перайсці ў. Проста вырашаючы bucket-- гэта ўсё хэш-функцыя. Так вось у нас ёсць прыклад, які проста першая літара радкі што я толькі што казаў пра. Так у вас ёсць хэш, гэта толькі Першая літара вашага струннага мінус, які дасць вам некаторыя лік ад 0 да 25. І тое, што вы хочаце зрабіць, гэта пераканайцеся, што гэта ўяўляе памер вашай хэш table-- колькі ёсць вядра. З многімі з іх Хэш-функцыі, яны збіраецца вяртацца значэння, якія маглі б быць нашмат вышэй колькасці каўшоў што вы на самой справе ёсць ў хэш-табліцы, так што вам трэба зрабіць упэўнены і мода на іх. У адваротным выпадку, ён збіраецца сказаць, ой, яна павінна быць у вядры 5000 але ў вас ёсць толькі 30 вядра ў ваш хэш-табліцы. І, вядома, мы ўсе ведаем, што гэта збіраецца прывесці ў некаторых вар'ятаў памылак. Таму пераканайцеся, што мода на Памер вашага хэш-табліцы. Прахладны. Так сутыкненняў. Ці ўсё добра да гэтага часу? Mmhmm? АЎДЫТОРЫЯ: З чаго б гэта вярнуць такую ​​масіўную значэнне? СПІКЕР 1: У залежнасці ад алгарытму што ваш хэш-функцыя выкарыстоўвае. Некаторыя з іх будуць рабіць вар'ят множання. І гэта ўсё аб атрыманні раўнамернае размеркаванне, так яны робяць некаторыя сапраўды вар'яты рэчы часам. Гэта ўсё. Што-небудзь яшчэ? Добра. Так сутыкненняў. У асноўным, як я ўжо казаў, у лепшым выпадку, любы вядро я гляджу ў гэта будзе мець адно, так што я не павінен глядзець на ўсё, ці не так? Я альбо ведаю, што там ці гэта ня, і гэта тое, што мы сапраўды хочам. Але калі ў нас ёсць дзесяткі тысяч пункту дадзеных і менш гэтага ліку каўшоў, мы збіраемся мець Сутыкнення дзе ў рэшце рэшт што-то будзе мець у канчатковым выніку ў Вядро, што ўжо ёсць элемент. Такім чынам, пытанне, што мы робім у гэтым выпадку? Што мы робім? У нас ужо ёсць што-то там? Ці ёсць у нас проста выкінуць яго? Няма. Мы павінны трымаць іх абодвух. Таму шлях, які мы як правіла, зрабіць гэта будзе што? Якая структура дадзеных мы толькі што гаварылі аб? АЎДЫТОРЫЯ: звязаны спіс. СПІКЕР 1: звязаны спіс. Так што цяпер, замест таго, каб кожны з іх Вядра толькі маючы адзін элемент, ён збіраецца ўтрымліваць звязаны спіс элементы, якія былі HASHED ў яго. ОК, ці ўсё выгляд гэта ўзялі? Таму што мы не маглі мець масіў таму што мы не ведаем, як шмат рэчаў збіраюцца быць там. Звязаны спіс дазваляе ёсць толькі дакладнае лік, што хэшируются у гэтым вядры, ці не так? Так лінейнага зандзіравання з'яўляецца у асноўным гэта idea-- гэта адзін са спосабаў барацьбы з сутыкненні. Што вы можаце зрабіць, гэта калі ў гэты Справа, ягада была хэшируется ў 1 і ў нас ужо ёсць што-то там, вы проста працягваць ісці ўніз да таго часу, Вы знайсці свабодны слот. Гэта адзін са спосабаў справіцца з гэтым. Іншы спосаб справіцца гэта з тым, што мы проста called-- звязаны спіс называецца ланцужкі. Так гэтая ідэя працуе, калі Ваш хэш-табліцы вы думаеце значна больш, чым ўсталяваць вашы дадзеныя, або калі вам хачу паспрабаваць і мінімізаваць ланцужкі пакуль гэта не абсалютна неабходна. Так адно лінейнае зандзіравання, відавочна, азначае, што ваш хэш-функцыі гэта не зусім так карысна таму што вы будзеце ў канчатковым выніку з дапамогай Ваш хэш-функцыя, трапляючы ў кропку, Вы лінейны датчык да нейкае месца, што даступна. Але цяпер, вядома, што-небудзь яшчэ, што заканчваецца там, Вы будзеце мець, каб пошук яшчэ далей ўніз. І ёсць нашмат больш Пошук выдаткі, якія пераходзіць у ўводзе элемент ў хэш-табліцы зараз, ці не так? І зараз, калі вы ідзяце, і паспрабаваць знайсці ягадка ізноў, вы збіраецеся, каб высьветліць ягоную, і ён збіраецца сказаць, ой, глядзіце ў вядро 1, і гэта не будзе у вядро 1, так што вы давядзецца прайсці праз астатнія з іх. Так што часам карысна, але ў большасці выпадкаў, мы збіраемся сказаць, што ланцужкі з'яўляецца тое, што вы хочаце зрабіць. Такім чынам, мы казалі пра гэта раней. Я крыху забягаю наперад. Але ланцужкі ў асноўным, што кожны вядро ў хэш-табліцы гэта проста звязаны спіс. Так яшчэ адзін спосаб, або больш тэхнічны спосаб, каб думаць пра хэш-табліцы з'яўляецца тое, што гэта проста масіў звязаных спісаў, якія калі вы пішаце свой слоўнік і вы спрабуеце загрузіць яго, думаць пра яго, як масіў звязаных спісаў будзе зрабіць гэта нашмат прасцей для вас, каб ініцыялізаваць. АЎДЫТОРЫЯ: Так хэш-табліцы мае загадзя пэўны памер, як [неразборліва] вёдраў? СПІКЕР 1: Права. Так што мае пэўную колькасць Каўшы, што вы determine-- якія вы, хлопцы, павінны не саромейцеся гуляць з. Гэта можа быць даволі халаднавата каб паглядзець, што адбываецца як вы зменіце сваё колькасць сегментаў. Але так, гэта мае ўсталяваць колькасць каўшоў. Што дазваляе адпавядаць як многія элементы, як вам трэба гэта асобны ланцужкі, дзе вас звязалі спісы ў кожным вядры. Гэта азначае, што ваш хэш-табліцу будзе дакладна памер што вам гэта трэба, каб быць, ці не так? Вось і ўся кропка звязаных спісаў. Прахладны. Так што ўсё там у парадку? Добра. Ах. Што толькі што адбылося? Сапраўды цяпер. Адгадайце, хто-то забівае мяне. ОК, мы збіраемся пайсці ў нах, якія трохі вар'ятам. Мне падабаецца хэш-табліцы. Я думаю, што яны сапраўды выдатна. Спрабуе гэта крута, занадта. Дык хто-небудзь памятае, што спроба гэта? Вы павінны перайшлі гэта коратка ў лекцыі? Памятаеш роду, як гэта працуе? АЎДЫТОРЫЯ: Я проста ківаючы што мы сапраўды ішлі па ёй. СПІКЕР 1: Мы сапраўды ідуць па ім. Добра, мы сапраўды збіраемся ісці за гэта зараз з'яўляецца тое, што мы гаворым. АЎДЫТОРЫЯ: Вось для пошуку дрэва. СПІКЕР 1: Так. Гэта пошукавая дрэва. Дзіўны. Так што, адно заўважыць тут, што мы глядзім на асобных персанажаў тут, ці не так? Таму, перш чым з нашым хэш-функцыі, мы глядзелі на словах, як у цэлым, і зараз мы глядзім больш на персанажаў, ці не так? Таму ў нас ёсць Максвелла сюды і Мендэль. Таму ў асноўным try-- спосаб думаць аб тым, што кожны ўзровень тут ўяўляе сабой масіў з літар. Так што гэта ваш каранёвай вузел тут, ці не так? Гэта ўсё сімвалы алфавіт для пачатку кожнага слова. І тое, што вы хочаце зрабіць, гэта скажам, у парадку, у нас ёсць некаторыя M слова. Мы збіраемся шукаць Максвелла, так мы ідзем да М. і М кропак у цэлым іншы масіў, у якім кожны Слова, пакуль існуе гэтае слова, якое мае ў якасці другога лісты, пры ўмове, што ёсць слова, якое ёсць B ў якасці другога лісты, ён будзе мець паказальнік адбываецца ў нейкай наступны масіў. Там, напэўна, не Слова, якое MP-то, так у P пазіцыі ў гэтым Масіў, што гэта проста будзе NULL. Гэта б сказаў, добра, там няма ні слова што M наступным P, ОК? Так што, калі мы думаем пра яе, кожны адзін з гэтых больш дробных рэчаў на самой справе адзін з іх буйныя масівы з A да Z. Так што можа быць адной з рэчаў, што гэта свайго роду недахопам паспрабаваць? АЎДЫТОРЫЯ: Шмат памяці. СПІКЕР 1: Гэта тона памяці, ці не так? Кожны з гэтых блокаў тут ўяўляе 26 месцы, 26 масіў элементаў. Так спрабуе атрымаць неверагодна прастору цяжкім. Але яны вельмі хутка. Так неверагодна хутка, але сапраўды прастору неэфектыўна. Выгляд павінен высветліць з якой вы хочаце. Гэта сапраўды выдатна для вашага PSET, але яны займаюць шмат памяці, так што вы кампраміс. Так? АЎДЫТОРЫЯ: Ці можна будзе наладзіць спробу, а затым калі ў вас ёсць усе Дадзеныя ў ім, што вы need-- Я не ведаю, калі гэта будзе мець сэнс. Я быў пазбавіцца ад усіх NULL сімвалы, але затым Вы не змаглі б індэкс them-- СПІКЕР 1: Вы па-ранейшаму ў іх мае патрэбу. АЎДЫТОРЫЯ: - сапраўды гэтак жа кожны раз. СПІКЕР 1: Так. Вы патрэбны нулявыя сімвалы, каб Вы ведаеце, калі ёсць не слова ёсць. Бэн ў вас было што-то вы хочаце? Добра. Добра, так што мы збіраемся ісці трохі больш ў тэхнічных дэталях ззаду паспрабаваць працаваць праз прыклад. ОК, так што гэта адно і тое ж. У той час як у звязаным спісе, наш галоўны выгляд of-- што слова, якое я хачу? - як будаваць блок быў вузел. У спробе, у нас таксама ёсць вузел, але гэта вызначаецца па-рознаму. Такім чынам, мы маем некаторую Ьоо што ці ўяўляе слова ў рэчаіснасці існуе ў гэтым месцы, а затым у нас ёсць некаторыя масіў here-- дакладней, гэта паказальнік на Масіў складаецца з 27 знакаў. А гэта для, у дадзеным выпадку, гэта 27-- Я ўпэўнены, што ўсе вы, як, чакаць, ёсць 26 літары алфавіту. Чаму ў нас 27? Таму ў залежнасці ад як вы гэта рэалізаваць, гэта ад PSET, што дазволена для апострафы. Дык вось чаму дадатковы адзін. Вы таксама будзеце мець у некаторыя выпадкі нулявы тэрмінатар уключаны ў якасці аднаго з персанажы, што гэта дазволена быць, і вось як яны правяраюць, каб убачыць, калі гэта канец слова. Калі вы зацікаўлены, праверыць Відэа Кевіна на study.cs50, а таксама Вікіпедыі ёсць некаторыя добрыя рэсурсы там. Але мы збіраемся прайсці праз толькі збольшага пра тое, як вы маглі б працаваць праз спробы калі вы далі адзін. Таму ў нас ёсць супер просты адзін тут, што няма слоў "кажан" і "зум" ў іх. І, як мы бачым тут, гэта мала месца тут прадстаўляе нашу Ьоо што кажа, так, гэта слова. А потым гэта карыстаецца нашым масівы сімвалаў, ці не так? Такім чынам, мы збіраемся прайсці праз знайсці "бітай" у гэтым спробы. Так пачынаюцца ў верхняй часткі, ці не так? І мы ведаем, што б адпавядае другі індэкс, другі элемент у гэтым масіве, таму што і б. Так прыкладна другая. І гэта кажа, у парадку, крута, вынікае, што ў наступны масіў, таму што, калі мы памятаем, гэта не што кожная з іх фактычна ўтрымлівае элемент. Кожны з гэтых масіваў ўтрымлівае паказальнік, ці не так? Гэта важнае адрозненне, каб зрабіць. Я ведаю, што гэта будзе be-- спрабуе з'яўляюцца вельмі цяжка атрымаць на першы раз, таму, нават калі гэта другі ці трэці раз і ён па-ранейшаму выгляд уяўнай цяжка, Я абяцаю, калі вы ідзяце гадзіны Карацей заўтра, гэта, напэўна, зрабіць нашмат больш сэнсу. Гэта займае вельмі шмат, каб пераварыць. Я да гэтага часу часам я як, чакаць, што гэта спроба? Як я магу выкарыстоўваць гэта? Такім чынам, мы б і ў гэтым выпадку, якая з'яўляецца нашым другім паказчыкам. Калі б мы мелі, скажам, з або d або любы іншы літарай, мы павінны адлюстраваць гэтую спіной да індэксе нашага масіва, які адпавядае. Такім чынам, мы б як rchar, і мы проста адняць ад супаставіць яго ў 0 да 25. Усё добра, як мы Карта нашых герояў? Добра. Так мы ідзем да другога і мы бачыць, што, так, гэта не NULL. Мы можам перайсці да наступным масіве. Такім чынам, мы пяройдзем да гэтай наступнай масіва тут. І мы кажам: добра, зараз мы ці трэба гэта тут. З'яўляецца нулявым або робіць гэта на самай справе рухацца наперад? Так на самай справе рухаецца наперад у гэтым масіве. І мы кажам: добра, т наша апошняя літара. Так мы ідзем у т у індэксе. А потым мы рухаемся наперад таму што ёсць яшчэ адзін. І гэта кажуць у асноўным, што, так, ён кажа, што ёсць слова here-- што калі вы будзеце прытрымлівацца гэтым Шлях, вы прыехалі пры слове, якое мы ведаем, "Лятучая мыш". Так? АЎДЫТОРЫЯ: Гэта стандартная мець што як індэкс 0, а затым ёсць свайго роду ў 1 або мець у канцы? СПІКЕР 1: Не. Так што, калі мы азірнемся на наш Дэкларацыя тут, гэта лагічны, так што гэта яго ўласны элемент у вузле. Так што гэта не частка масіва. Прахладны. Так што, калі мы скончым наша слова, і мы у гэтым масіве, тое, што мы хочам зрабіць гэта зрабіць чэк на гэтае слова. І ў гэтым выпадку, ён вернецца да. Так на гэтай ноце, мы ведаем, што "заапарк" - мы ведаем, як людзі, якія "заапарк" гэтае слова, ці не так? Але будуць спрабаваць тут будзе кажуць, не, гэта не так. І было б сказаць, што, таму што мы ня пазначаныя як словы тут. Нават пры тым, што мы можам прайсці да гэтага масіва, гэта спроба магла сказаць, што, не, заапарк не ў слоўніку таму што ў нас не пазначыўшы яго як такой. Так адзін з спосабаў зрабіць that-- ой, прабачце, гэта адзін. Такім чынам, у дадзеным выпадку, "заапарк" не Слова, але гэта ў нашай спробы. Але ў гэтым, сказаць, што мы хочам яго ўвесці слова "лазня", тое, што адбываецца гэта мы ідзём through-- B, A, т. Мы ў гэтым масіве, і мы ідзем шукаць ч. У гэтым выпадку, калі мы паглядзіце на паказальнік на гадзіну, гэта паказвае на NULL, ОК? Так, калі гэта не відавочна паказваючы на ​​іншага масіва, Вы мяркуеце, што ўсе ўказальнікі у гэтым масіве паказваючы на ​​нуль. Такім чынам, у гэтым выпадку, ч паказвае абнуліць таму мы нічога не можам зрабіць, так яно і вернецца ілжывым, "лазня" не тут. Так што цяпер мы на самай справе збіраюся прайсці праз як бы мы на самай справе сказаць, што "заапарк" знаходзіцца ў нашай спробы. Як мы ўстаўляем "заапарк" у нашай спробы? Такім чынам, у адной і той жа спосабам, што мы пачалі з наш звязаны спіс, мы стартуем з кораня. Калі вы сумняваецеся, пачніце з корань гэтых рэчаў. І мы будзем казаць, добра, г. г існуе ў гэтым, і ён робіць. Такім чынам, вы, як перайсці да Ваш наступны масіў, ОК? А потым на наступны, мы кажам, добра, сапраўды пра існуюць? Ён робіць. Гэта яшчэ раз. І так на нашым наступным, мы ўжо казалі, ОК, "заапарк" ужо існуе тут. Усё, што трэба зрабіць, гэта ўсталяваць гэта роўна праўдзіва, што ёсць слова там. Калі вы вынікалі ўсе да перад тым пунктам, гэтае слова, так што проста ўсталяваць яго роўным такія. Так? АЎДЫТОРЫЯ: Такім чынам робіць, што азначае, што "ба" гэта слова таксама? СПІКЕР 1: Не. Такім чынам, у дадзеным выпадку, "ба", мы атрымаем тут, мы б сказалі, гэта слова, ня, і гэта ўсё роўна будзе не. Добра? Mmhmm? АЎДЫТОРЫЯ: Таму, як толькі вы гэта Слова і вы кажаце, так, то гэта будзе ўтрымліваць пайсці ў м? СПІКЕР 1: Так што гэта мае дачыненне да with-- вы загружаеце гэта. Вы кажаце, "заапарк" гэтае слова. Калі вы ідзяце ў check-- як, скажам, вы хочаце сказаць ,, значыць "заапарк" існуюць у гэтым слоўніку? Вы толькі збіраецеся шукаць "заапарк" а затым праверыць, калі гэтае слова. Вы ніколі не збіраецеся пераехаць да м, таму што гэта не тое, што вы шукаеце. Так што, калі мы на самай справе хацелі дадаць "ванну" у гэтай спробе, мы будзем рабіць тое ж самае як мы гэта рабілі з "заапаркам" акрамя мы ўбачым, што, калі мы паспрабаваць дабрацца да ч, яго не існуе. Такім чынам, вы можаце думаць пра гэта як спрабуюць каб дадаць новы вузел ў звязаным спісе, такім чынам, мы павінны былі б дадаць яшчэ адзін адзін з гэтых масіваў, як і. І тады тое, што мы робім, мы проста ўсталяваць гадзіну элемент гэтага масіву, якія паказваюць на гэта. І тады тое, што мы хацелі б зрабіць тут? Дадаць гэта роўна справядліва таму што гэтае слова. Прахладны. Я ведаю. Спрабуе не самая захапляльная. Паверце мне, я ведаю. Так адна справа разумець, з спроб, Я сказаў, што яны вельмі эфектыўныя. Такім чынам, мы бачылі яны заняць да тону прасторы. Яны накшталт заблытанай. Дык чаму б нам калі-небудзь выкарыстоўваць іх? Мы выкарыстоўваем іх, таму што яны неверагодна эфектыўны. Так што калі вы калі-небудзь шукаеце да Словам, вы толькі абмежаваныя па даўжыні слова. Так што калі вы шукаеце Слова, якое мае даўжыню пяць, Вы толькі калі-небудзь прыйдзецца зрабіць у большасці пяць параўнанняў, ОК? Такім чынам, гэта робіць яго ў асноўным пастаяннай. Як ўстаўкі і пошуку у асноўным пастаянная часу. Так што калі вы можаце калі-небудзь атрымаць што-то ў пастаянным часу, гэта так жа добра, як ён атрымлівае. Вы не можаце паправіцца, чым Пастаянная часу для гэтых рэчаў. Так, што з'яўляецца адным з Вялізныя плюсы спробаў. Але гэта шмат месца. Такім чынам, вы, здаецца, павінны вырашыць, што для вас важней. І на сучасных кампутарах, прастору, што спроба можа заняць да можа быць, не ўплывае Вы так шмат, але, можа быць, Вы маеце справу з чым-то што мае значна, значна больш рэчаў, і паспрабаваць проста не разумна. Так? АЎДЫТОРЫЯ: Пачакайце, так у вас ёсць 26 Літары ў кожным адзін? СПІКЕР 1: Mmhmm. Так, у вас ёсць 26. У вас ёсць нейкі ёсць слова маркер, а затым у вас ёсць 26 паказальнікаў у кожным з. І яны point-- АЎДЫТОРЫЯ: І кожны 26, яны адзін у 26? СПІКЕР 1: Так. І вось чаму, як вы можаце см, яна пашыраецца даволі хутка. Добра. Такім чынам, мы збіраемся, каб атрымаць у дрэвы, якія Я адчуваю, што гэта прасцей і, верагодна, быць міленькі адтэрміноўка ад спробаў ёсць. Будзем спадзявацца, што большасць з вас бачылі дрэва раней. Не так, як даволі тыя, за межамі, якія я не ведаю, калі хто- пайшоў на адкрытым паветры ў апошні час. Я пайшоў збор яблыкаў у гэтыя выходныя, і о, чорт вазьмі, гэта было прыгожа. Я не ведаў, лісце можа выглядаць, што даволі. Так што гэта проста дрэва, ці не так? Гэта толькі некаторыя вузел, і ён паказвае на кучу іншых вузлоў. Як вы бачыце тут, гэта выгляд паўтаральнай тэмай. Вузлы, які паказвае на вузлах з'яўляецца свайго роду Сутнасць многіх структур дадзеных. Усё залежыць ад таго, як мы каб яны паказваюць адзін з адным і як мы перасякаем праз іх і, як мы ўставіць тое, што вызначае іх розныя характарыстыкі. Так што некаторыя тэрміны, якія я выкарыстаў раней. Так корань ўсё, што знаходзіцца на самым версе. гэта дзе мы заўсёды пачынаем. Вы можаце думаць пра гэта як кіраўнік таксама. Але для дрэў, мы, як правіла, ставяцца да яго як корань. Усё ў ніжняй here-- у вельмі, вельмі bottom-- лічацца лісце. Так што ідзе разам з усё дрэва, што, ці не так? Лісце па краях дрэве. І тады ў нас таксама ёсць некалькі Умовы казаць аб вузлах сувязі адзін да аднаго. Таму ў нас ёсць бацька, дзеці, браты і сёстры. Такім чынам, у дадзеным выпадку, з'яўляецца 3 Бацька 5, 6, і 7. Так бацька ўсё, што адзін крок вышэй, што вы знаходзіцеся са спасылкай на, так што проста як радаводу. Будзем спадзявацца, што гэта ўсё трохі трохі больш зразумелым, чым спробаў. Браты і сёстры з'яўляюцца любыя, якія маюць тое ж самае з бацькоў, ці не так? Яны на тым жа ўзроўні, тут. А потым, як я быў кажучы, дзеці проста усё, што на адзін крок ніжэй дадзены вузел, ОК? Прахладны. Так бінарнае дрэва. Можа хто-небудзь здагадку на адным з характарыстыкі бінарнага дрэва? АЎДЫТОРЫЯ: Макс два ліста. СПІКЕР 1: Права. Так макс двух лісця. Такім чынам, у гэты перш, у нас быў гэты адзін што было тры, але ў бінарным дрэве, ў вас ёсць макс двух дзяцей на бацькоў, ці не так? Там іншая Цікавай асаблівасцю. Хто-небудзь ведае, што? Бінарнае дрэва. Так бінарнае дрэва будзе мець усе на the-- гэты ня sorted-- але ў адсартаваны бінарнага дрэва, усе справа больш, чым бацькоў, і ўсё злева менш, чым бацькоў. І што было віктарына Пытанне перш, так добра ведаць. Так як мы вызначаем гэта, зноў, у нас ёсць яшчэ адзін вузел. Гэта выглядае вельмі падобна на што? Ўдвая Аўдыторыя: Змяненні, спісы СПІКЕР 1: двайны звязаны спіс, ці не так? Так што, калі мы заменім гэты з папярэднім і наступным, гэта было б ўдвая звязаны спіс. Але ў дадзеным выпадку, мы на самай справе ёсць левы і правы, і гэтым усё сказана. У адваротным выпадку, гэта сапраўды гэтак жа. У нас яшчэ ёсць элемент Вы шукаеце, і вы проста павінны два паказальніка збіраецца ўсё, што будзе далей. Так, так бінарнае дрэва. Калі мы заўважаем, усё на тут больш than-- або ўсё адразу каб прама тут больш, чым усё, тут менш. Так што, калі б мы павінны былі шукаць праз, яго павінен выглядаць вельмі блізка да бінарнага пошуку тут, ці не так? Акрамя замест таго каб шукаць на палове масіва, мы проста гледзячы на ​​любым злева бок або правая бок дрэва. Так ён атрымлівае крыху прасцей, я думаю. Так што калі ваш корань NULL, Відавочна, што гэта проста хлусня. І калі гэта ёсць, відавочна, што гэта праўда. Калі гэта менш, чым, мы шукаем левага. Калі гэта больш, чым, мы шукаем права. Гэта так жа, як бінарны пошук, проста іншая структура дадзеных што мы выкарыстоўваем. Замест масіва, гэта проста бінарнае дрэва. ОК, стэкі. А таксама, падобна, што мы можа мець трохі часу. Калі мы гэта зробім, я шчаслівы пайсці за ўсё гэта зноў. Такім чынам, стэкі. Хто-небудзь памятае, што stacks-- любыя характарыстыкі стэка? Такім чынам, большасць з нас, я думаю, што, ядуць у сталовай halls-- столькі, колькі мы, магчыма, не падабаецца. Але відавочна, што вы можаце думаць аб стэку літаральна толькі ў выглядзе чаркі латкоў або чарка рэчаў. І, што важна каб зразумець, што гэта something-- характарыстыка што мы называем гэта по-- з'яўляецца ЛИФО. Хто-небудзь ведае, што гэта азначае? Mmhmm? АЎДЫТОРЫЯ: апошнім прыйшоў, першым з. СПІКЕР 1: справа, апошнім прыйшоў, першым з. Так што, калі мы ведаем, калі мы кладка рэчаў да, прасцей за ўсё захапіць off-- і, можа быць, адзінае, што мы можам захапіць , Калі б наш стэк вялікі enough-- з'яўляецца тое, што верхні элемент. Таму, што б было паставіць на last-- як мы бачым тут, што было штурхнуў на найбольш recently-- з'яўляецца будзе першым рэч, якую мы паліць, ОК? Такім чынам, што мы маем тут справу іншы ЬурейеЕ структура. Гэта на самай справе проста хацеў Crash Course ў структуры дадзеных, так што ёсць шмат кінутыя на вас, хлопцы. Я ведаю. Так яшчэ адзін структура. Ура для структур. І ў гэтым выпадку, гэта нейкая паказальнік у масіў, які мае пэўны патэнцыял. Такім чынам, гэта ўяўляе наш стэк тут, як і наш фактычны масіў што трымае нашы элементы. А потым тут у нас ёсць некаторыя памеры. І, як правіла, вы хочаце, каб захаваць трэк, наколькі вялікі ваш стэк таму, што ён збіраецца, каб дазволіць Вы зрабіць гэта, калі вы ведаеце памер, гэта дазваляе сказаць, ОК, я на поўную магутнасць? Ці магу я дадаць нічога больш? І гэта таксама кажа вам, дзе ў верхняй частцы вашага стэка так вы ведаеце, што вы можа на самай справе зняць. І што на самой справе адбываецца ў быць трохі больш ясна. Такім чынам, для штуршка, З аднаго боку, калі вас былі калі-небудзь рэалізаваць штуршок, як я толькі што казаў, ваша Стэк мае абмежаваны памер, ці не так? Наш масіў быў некаторы патэнцыял. Гэта масіў. Гэта фіксаваны памер, так што нам трэба пераканацца, што мы не ставілі больш у нашым масіве, чым мы на самай справе ёсць месца для. Так што, калі вы ствараеце штуршок Функцыя, першае, што вам зрабіць, гэта скажам, у парадку, у мяне ёсць месца ў маёй стэка? Таму што, калі я не раблю, прабачце, Я не магу захоўваць элемент. Калі я, то вы хочаце захаваць гэта на вяршыні стэка, ці не так? І менавіта таму ў нас ёсць адсочваць нашага памеру. Калі мы не адсочваць нашага памеру, мы не ведаем, куды яго пакласці. Мы не ведаем, як шмат рэчаў у нашым масіве ўжо. Як відавочна, ёсць спосабы што, можа быць, вы маглі б зрабіць гэта. Вы можаце ініцыялізаваць усё, каб NULL а затым праверыць наяўнасць апошняй NULL, але значна прасцей рэч проста сказаць, у парадку, адсочваць памер. Як я ведаю, у мяне ёсць чатыры элемента ў маім масіве, так наступная рэч што мы ставім на, мы збіраецеся захоўваць у індэксе 4. І тады, вядома, гэта азначае, што Вы паспяхова штурхнуў што-то на свой стэк, вы хачу павялічыць памер так што вы ведаеце, дзе вы знаходзіцеся, так што вы можаце націснуць больш рэчаў на. Так што, калі мы спрабуем поп што-то з стэка, што можа быць у першую чаргу што мы хочам, каб праверыць? Ты спрабуеш ўзяць што-то ад вашага стэка. Вы ўпэўненыя, што ёсць што-то ў вашым стэку? Няма. Так што, магчыма, мы хочам праверыць? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Праверце памер? Памер. Таму мы хочам, каб праверыць, калі наш памер больш 0, ОК? І калі гэта так, то мы хочам, каб паменшыць наш памер 0 і вярнуць гэта. Чаму? У першым з іх мы былі штурхаючы, мы вылучылі яго на памер і затым абноўленай памеру. У гэтым выпадку, мы памяншаючы памер і тое, прымаючы яго, выскубанне яго з нашага масіва. Чаму мы можам гэта зрабіць? Так што, калі ў мяне ёсць адна рэч, на мой стэк, што б мой памер на той момант? 1. А дзе элемент 1 захоўваецца? На тое, што індэкс? АЎДЫТОРЫЯ: 0. СПІКЕР 1: 0. Такім чынам, у дадзеным выпадку, мы заўсёды трэба рабіць sure-- замест таго каб вярнуцца памер мінус 1, таму што мы ведаем, што наш элемент будуць захоўвацца на 1 менш усе наш памер, гэта проста клапоціцца пра яго. Гэта крыху больш элегантны спосаб. І мы проста паменшыць OUR Памер, а затым вярнуць памер. Mmhmm? Аўдыторыя: Я думаю, проста ў цэлым, навошта гэтая структура дадзеных быць карысным? СПІКЕР 1: Гэта залежыць ад кантэксту. Такім чынам, для некаторых з тэорыі, калі вы працуеце with-- ОК, дайце мне паглядзець, ці ёсць выгадна адзін што з'яўляецца карысным для больш, чым звонку з CS. З стэкаў, у любы час вам трэба адсочваць тое, што з'яўляецца найбольш нядаўна дададзенага, калі Вы збіраецеся хочаце выкарыстоўваць стэк. І я не магу думаць аб добрым прыклад, што цяпер. Але кожны раз, калі самая апошняя Справа ў тым, найбольш важныя для вас, вось калі стэк будзе карысна. Я спрабую думаць, калі ёсць добры варыянтам. Калі я думаю пра добры, напрыклад, у наступным 20 хвілін, я, безумоўна, скажу вам. Але ў цэлым, калі ёсць што-небудзь, як я сказаў, што большасць, дзе апошняя самае галоўнае, што гэта дзе чарка уступае ў гульню. У той час як чарзе з'яўляюцца свайго роду супрацьлегласць. І ўсе маленькія сабакі. Хіба гэта не выдатна, ці не так? Я адчуваю, што павінен проста ёсць трусік відэа прама ў сярэдзіне падзел для вас, хлопцы таму што гэта з'яўляецца інтэнсіўным падзел. Так чарзе. У асноўным чэргі як лінія. Вы, хлопцы, я ўпэўнены, што выкарыстанне гэтага кожны дзень, сапраўды гэтак жа як у нашых сталовых. Такім чынам, мы павінны пайсці ў і атрымаць у свае латкі, я што ў вас ёсць, каб стаяць у чарзе сурвэткі або атрымаць вашу ежу. Такім чынам, розніца тут у тым, што гэта FIFO. Так што, калі ЛИФО апошні раз быў у першую па-за, FIFO з'яўляецца першым прыйшоў, першым сышоў. Так што гэта, дзе ўсё, што вы паклалі на першы ваш самы важны. Так што, калі вы чакалі у line-- магу вас Уявіце сабе, калі вы пайшлі ў пайсці атрымаць новы iPhone і гэта быў стэк, дзе апошні чалавек у лініі атрымаў яго першым, людзі будуць забіваць адзін аднаго. Так FIFO, мы ўсе добра знаёмыя з у рэальным свеце тут, і ўсё гэта мае дачыненне да рэчаіснасці выгляд аднаўлення ўсю гэтую лінію і чэргаў структуру. Так у той час як са стэкам, у нас ёсць штуршок і поп-музыкі. З чаргу, мы маем паставіць у чаргу і выдалення з чаргі. Так паставіць у чаргу ў асноўным азначае, пакласці яго на спіну, і вываду са сродкаў ўзяць ад з фронту. Такім чынам, наша структура дадзеных крыху больш складана. У нас ёсць другое, для адсочвання. Так што без галавы, гэта менавіта стэк, ці не так? Гэта тое ж самае будынак, як стэк. Адзінае адрозненне ў цяперашні час з'яўляецца ў нас ёсць гэтая галава, якая, што вы думаеце збіраецца адсочваць? АЎДЫТОРЫЯ: Першы. СПІКЕР 1: справа, Першае, што мы ўкладваем у. Кіраўнік нашай чарзе. Той, хто гэта першы ў чарзе. Добра, так што калі мы робім у чаргу. Зноў жа, з любым з гэтыя структуры дадзеных, так як мы маем справу з масівам, мы павінны праверыць, калі ў нас ёсць прастора. Гэта накшталт як мне распавядаў хлопцы, калі вы адкрываеце файл, Вы павінны праверыць на нуль. З любы з гэтых стэкаў і чэргі, вам трэба каб убачыць, калі ёсць вольнае месца, таму што мы справу з масівам фіксаванага памеру, як мы бачым, here-- 0, 1 за ўсё да 5. Так, што мы робім у гэтым выпадку з'яўляецца праверка каб убачыць, калі ў нас яшчэ ёсць прастора. Ці з'яўляецца наша памер менш магутнасці? Калі гэта так, мы павінны захоўваць яго ў хвост, і мы адновім наш памер. Так што, магчыма, хвост будзе ў гэтым выпадку? Гэта відавочна не выпісаныя. Як бы мы захоўваем гэта? Што б хвост быць? Так што давайце ісці праз гэты прыклад. Так што гэта масіў памерам 6, ці не так? І ў нас ёсць цяпер, наш памер 5. І калі мы ставім яго ў, ён збіраецца ісці ў пятым індэкса, ці не так? Так захоўваць у хвасце. Яшчэ адзін спосаб напісаць хвост б проста быць наш масіў з індэксам памеру, ці не так? Гэта памер 5. Наступная рэч, якую збіраецца пайсці ў 5. Прахладны? Добра. Гэта становіцца крыху больш складана, калі мы пачынаем песціцца з галавой. Так? АЎДЫТОРЫЯ: Ці азначае гэта, што мы абвясціў б масіў, было даўно пяць элементаў і Затым мы дадаем на яго? СПІКЕР 1: Не. Такім чынам, у дадзеным выпадку, гэта стэк. Гэта будзе абвешчаны у выглядзе масіва памерам 6. І ў гэтым выпадку мы ёсць толькі адзін касмічны налева. Такім чынам, адна справа знаходзіцца ў гэтым так, калі наша галава на 0, Затым мы проста можаце дадаць яго ў памерах. Але гэта становіцца крыху больш складана таму што на самой справе, яны няма слайд для гэтага, так што я збіраюся каб зрабіць адзін, таму што гэта не так проста, як толькі вы пачаць збавенне ад рэчаў. Так у той час як са стэкам Вы толькі калі-небудзь турбавацца аб тым, што памер калі вы дадаеце нешта на, з чаргой вы таксама павінны пераканацца, Пераканайцеся, што ваша галава даводзілася, таму што выдатна, што пра чэргі з'яўляецца тое, што, калі вы не на поўную магутнасць, вы можаце зрабіць гэта абгарнуць вакол. Такім чынам, адзін thing-- о, гэта жудасна мел. Адна рэч, каб разгледзець гэтую справу. Мы проста робім пяць. Такім чынам, мы збіраемся кажуць галава тут. Гэта азначае 0, 1, 2, 3, 4. Кіраўнік там, і калі ласка, што ў іх. І мы хочам, каб дадаць нешта ў, ці не так? Так, што мы павінны ведаю, што галава заўсёды будзе рухацца гэтым шляхам і Затым цыкл назад вакол, ОК? Так гэтая чаргу мае месца, ці не так? У ім ёсць месца ў самым пачатку, выгляд супрацьлегласці гэта. Так што нам трэба зрабіць, гэта мы трэба разлічыць хвост. Калі вы ведаеце, што ваш галава не пераехаў, хвост проста ваш масіў у Індэкс памеру. Але на самай справе, калі вы карыстаецеся чаргу, Ваша галава, верагодна, абнаўляецца. Так што вам трэба зрабіць, гэта на самай справе вылічыць хвост. Так што мы робім, гэта формула тут, якія я збіраюся даць вам хлопцы, думаеце пра, і тады мы будзем казаць пра гэта. Так што гэта магутнасць. Так што гэта будзе на самой справе даць вам спосаб зрабіць гэта. Таму што ў гэтым выпадку, тое, што? Наша галава на 1, наш памер 4. Калі мы мод, што на 5, атрымліваем 0, які з'яўляецца, дзе мы павінны ўвесці яго. Так то ў наступным выпадку, калі мы павінны былі зрабіць гэта, мы кажам, добра, давайце з чаргі што-то. Мы з чаргі гэта. Вымаем гэты элемент, ці не так? І цяпер наша галава паказваючы тут, і мы хочам дадаць у іншым. Гэта, у асноўным назад ад нашай лініі, ці не так? Чэргі могуць абгарнуць вакол масіва. Гэта адна з асноўных адрозненняў. Чаркі, вы не можаце зрабіць гэта. З чэргамі, вы можаце таму што ўсё, што мае значэнне з'яўляецца тое, што вы ведаеце, што зусім нядаўна быў дададзены. Паколькі ўсё будзе дададзены ў гэты кірунак налева, у гэтым выпадку, а затым абгарнуць вакол, вы можаце працягнуць ўвод новых элементаў у пярэдняй частцы масіва таму што гэта не сапраўды пярэдняя частка масіва больш. Вы можаце думаць аб пачатку Масіў як дзе ваша галава на самай справе. Так гэтая формула, як Вы разлічыць свой хвост. Ці значыць гэта, мае сэнс? Добра. ОК, з чаргі, а затым вы, хлопцы, ёсць 10 хвілін задаваць мне любыя удакладняючыя пытанні Вы хочаце, таму што я ведаю, што гэта вар'ят. Добра, так у тым жа way-- Я не ведаю, калі вы, хлопцы заўважылі, але CS гэта ўсё аб ўзорамі. Рэчы даволі шмат ж, толькі з малюсенькімі хітрыкаў. Гэтак жа і тут. Нам трэба праверыць, каб убачыць, калі мы на самай справе ёсць што-то ў нашай чарзе, дакладна? Скажам, у парадку, наша памер больш 0? Прахладны. Калі мы гэта зробім, то мы перанясем наша галаву, якая гэта тое, што я толькі што прадэманстраваў тут. Мы абнаўляем нашу галаву яшчэ адна. А потым мы памяншаем нашы Памер і вяртае элемент. Існуе значна больш бетону Код на study.cs50.net, і я вельмі рэкамендую рух праз яго, калі ў вас ёсць час, нават калі гэта ўсяго толькі псеўда-код. І калі вы, хлопцы, жадаеце пагаварыць праз што са мной адзін на адзін, калі ласка, паведаміце мне, ведаю. Я быў бы шчаслівы. Структуры дадзеных, калі вы бераце CS 124, вы будзеце ведаю, што структуры дадзеных атрымаць вельмі весела і гэта толькі пачатак. Так што я ведаю, гэта цяжка. Гэта нармальна. Мы змагаемся. Я да гэтага часу. Так што не турбуйцеся пра гэта занадта шмат. Але гэта ў асноўным праграмы Your Crash Course ў структурах дадзеных. Я ведаю, што гэта шмат. Ёсць што-небудзь, што мы хацеў бы пайсці зноў? Усё, што мы хочам пагаварыць праз? Так? АЎДЫТОРЫЯ: Для гэтага, напрыклад, так новы хвост на 0 над гэтым? СПІКЕР 1: Так. АЎДЫТОРЫЯ: ОК. Такім чынам перажывае, Вы павінны былі б 1 плюс 4 или-- СПІКЕР 1: Такім чынам, вы казалі, калі мы хочам пайсці і зрабіць гэта зноў? АЎДЫТОРЫЯ: Так. Так што, калі вы былі высветліць out-- дзе Вы разліку хвост з ў тым, што? СПІКЕР 1: Так хвост быў in-- я змяніў гэта. Такім чынам, у гэтым прыкладзе тут, гэта было масіў, мы глядзім на, ОК? Таму ў нас ёсць рэчы, у 1, 2, 3, і 4. Таму ў нас ёсць наша галава роўная 1 на гэтая кропка, і наш памер роўны 4 на дадзены момант, ці не так? Вы ўсё згодныя, што гэта так? Так мы робім галаву плюс памер, які дае нам 5, а затым мы мод на 5. Мы атрымліваем 0, якая кажа нам, што 0 з'яўляецца дзе наша хвост, дзе ў нас ёсць прастора. АЎДЫТОРЫЯ: Што шапка? СПІКЕР 1: Ёмістасць. Прабачце. Так што гэта памер вашага масіва. Так? АЎДЫТОРЫЯ: [неразборліва], перш чым мы вяртае элемент? СПІКЕР 1: Так мы рухаемся ўзначаліць або вярнуць час? Так што, калі мы пяройдзем адзін, паменшыць памер? Ўтрымліваць. Я вызначана забыўся яшчэ адзін. Нічога. Існуе не адна формула. Так, вы хацелі б, каб вярнуцца кіраўнік, а затым вярнуць яго назад. АЎДЫТОРЫЯ: ОК, таму што ў гэты Кропка, галава была на 0, а затым вы хочаце, каб вярнуцца Індэкс 0, а затым зрабіць галаўнога 1? СПІКЕР 1: Права. Я думаю, што ёсць яшчэ адзін Формула накшталт як гэта. У мяне няма яго на верхняй галаву, як Я не хачу, каб даць вам не той. Але я думаю, што гэта цалкам дапушчальна, каб скажам, у парадку, захоўваць гэтую element-- ўсе элемент галава is-- паменшыць ваш памер, перамяшчаць галаву над, і вяртанне усё, што элемент. Гэта зусім справядліва. Добра. Я адчуваю, што гэта не як most-- вы не збіраецца выйсці адсюль як, так, я ведаю спробаў. Я атрымаў усё гэта. Гэта добра. Я абяцаю. Але структуры дадзеных з'яўляюцца чым-тое, што яна займае шмат часу, каб прывыкнуць. Верагодна, гэта адзін з самых складаных рэчы, я думаю, што, у курсе. Так што, безумоўна, займае Паўтарэнне і гледзячы at-- I на самай справе не ведаю, сувязныя спісы пакуль я не зрабіў занадта шмат з імі, такім жа чынам, што не зрабіў сапраўды зразумець паказальнікі пакуль у мяне не было, каб навучыць яго на дваіх гадоў і зрабіць свае ўласныя psets з ім. Гэта займае шмат паўтарэння і час. І ў рэшце рэшт, гэта будзе свайго роду націсніце. Але ў той жа час, калі ў вас ёсць выгляд з глыбокага знаёмства з таго, што гэта зрабіць, іх плюсы і cons-- што і мы сапраўды, як правіла, падкрэсліваюць, асабліва ў інтра вядома. Маўляў, навошта нам выкарыстоўваць паспрабуйце над масівам? Маўляў, тое, што станоўчыя бакі і негатывы кожнага з іх? І разуменне кампрамісаў паміж кожнай з гэтых структур з'яўляецца тое, што значна больш важна цяпер. Там можа быць адзін вар'ят Пытанне або два гэта папрашу вас, каб рэалізаваць штуршок або ажыццявіць поп або паставіць у чаргу і выдалення з чаргі. Але па большай частцы, якія маюць, што вышэй разуменне ўзроўню і больш з інтуітыўнае разуменне з'яўляецца важней, чым на самай справе будучы ў стане яго рэалізаваць. Гэта было б сапраўды выдатна, калі вы ўсё маглі выйсці і пайсці рэалізаваць спробу, але мы разумеем, што гэта не абавязкова самае разумнае цяпер. Але вы можаце ў PSET, калі вы хочаце на, а затым вы атрымаеце практыку, і тады, магчыма, вы будзеце сапраўды разумею. Так? АЎДЫТОРЫЯ: ОК, так, якія з іх мы хацелі выкарыстоўваць у PSET? Ці трэба выкарыстоўваць адну з іх? СПІКЕР 1: Так. Так у вас ёсць выбар. Я думаю, у гэтым выпадку, мы можам казаць аб PSET трохі таму што я прабег гэтыя. Так што ў вашым PSET, у вас ёсць свой Выбар спробаў або хэш-табліцы. Некаторыя людзі будуць спрабаваць і выкарыстоўваць цвіцення фільтры, але тыя, тэхнічна не правільна. З-за іх імавернасны характар, яны даюць ілжывыя спрацоўвання часам. Яны халодны погляд у, хоць. Вельмі рэкамендую гледзячы на іх, па меншай меры. Але ў вас ёсць выбар паміж хэш-табліцу і паспрабаваць. І што будзе, калі Вы загружаеце ў слоўніку. І вы павінны будзеце выбраць Ваш хэш-функцыя, Вы павінны будзеце выбраць, колькі Вядра ў вас ёсць, і яна будзе мяняцца. Як калі ў вас ёсць больш вядра, можа быць, ён будзе працаваць хутчэй. Але, можа быць, вы дарма шмат месца, што шлях, хоць. Вы павінны зразумець гэта. Mmhmm? АЎДЫТОРЫЯ: Вы казалі, што мы можам выкарыстоўваць іншыя хэш-функцый, што мы не павінны стварыць хэш-функцыі? СПІКЕР 1: Так, дакладна. Так літаральна за хэш-функцыі, Як і Google "хэш функцыя" і шукаць нейкія новых і прышпільных. Вы не мяркуецца пабудаваць Вашы ўласныя хэш-функцыі. Людзі марнуюць іх тэзісы аб гэтых рэчах. Так што не турбуйцеся аб будаўніцтве самастойна. Знайсці адно онлайн, каб пачаць з. Некаторыя з іх вы павінны маніпуляваць трохі каб пераканацца, што вяртаюцца тыпы супадаюць і яшчэ шмат чаго, так што ў пачатку, Я б рэкамендаваў выкарыстоўваць што-то вельмі лёгка, што, можа быць, проста хэшы па першай літары. А потым, як толькі ў вас ёсць, што працу, ўключэння кулер Хэш-функцыі. Mmhmm? АЎДЫТОРЫЯ: б паспрабаваць быць ці эфектыўным, але толькі складаней, like-- СПІКЕР 1: Так паспрабаваць, я думаю, Інтуітыўна цяжка рэалізаваць але вельмі хутка. Тым не менш, займае больш месца. Зноў жа, вы можаце аптымізаваць і тых, хто ў розныя спосабы і ёсць спосабы to-- АЎДЫТОРЫЯ: Як мы ацэньваюцца з гэтай нагоды? Ці значыць гэта matter-- СПІКЕР 1: Такім чынам, вы ацэньваюцца звычайным спосабам. Вы збіраецеся ацэньваюцца па дызайне. Які б шлях вы ні рабілі, вы хочаце, каб пераканайцеся, што гэта так элегантна, як гэта можа быць і так эфектыўна, як гэта можа быць. Але калі вы выбіраеце спробу або хэш Табліца таго часу, пакуль ён працуе, мы задаволеныя, што. А калі вы выкарыстоўваеце нешта, што хэшы па першай літары, гэта нармальна, як, можа быць, як дызайн-мудрым. Мы таксама дасягненні Кропка ў гэтым semester-- Я не ведаю, калі вы Хлопцы noticed-- калі вы Pset гатункі зніжацца трохі з-за дызайну і яшчэ шмат чаго, гэта выдатна. Гэта становіцца ў кропку, дзе ваш Праграмы становяцца ўсё больш складанымі. Ёсць яшчэ месцы Вы можаце палепшыць. Так што гэта цалкам нармальна. Гэта не тое, што вы робіць горш на PSET. Гэта проста мы быць мацней на вас цяпер. Такім чынам, кожны адчувае гэта. Я проста ацэньваюцца ўсе вашы psets. Я ведаю, што ўсе адчуваюць гэта. Так што не турбуйцеся пра гэта. І калі ў вас ёсць якія-небудзь пытанні Папярэднія psets або спосабаў, вы можаце палепшыць, Я стараюся і каментаваць канкрэтныя месцы, але часам гэта позна і я стамляюся. Ці ёсць іншыя рэчы каля структуры дадзеных? Я ўпэўнены, што вы, хлопцы, не вельмі хачу пагаварыць пра іх больш, але калі ёсць, я шчаслівы ісці па іх, а таксама што-небудзь З лекцыі ў мінулую тыдзень ці на мінулым тыдні. Я ведаю, на мінулым тыдні было ўсё агляд, так мы, магчыма, прапусцілі на працягу некаторага перагляду ад лекцыі. Любыя іншыя пытанні я магу адказаць? ОК, усё ў парадку. Ну, вы, хлопцы, выходзьце 15 хвілін раней. Я спадзяюся, што гэта быў паў-карыснымі, па меншай меры, і я буду бачыць вас, хлопцы на наступным тыдні, або чацвер працоўныя гадзіны. Ёсць просіць для закусак на наступным тыдні, гэта-то і справа? Таму што я забыўся цукеркі сёння. І я прынёс цукеркі апошні тыдзень, але гэта быў Дзень Калумба, такім чынам, было як шэсць чалавек, якія было чатыры мяшка цукерак да сябе. Я магу прывесці Starbursts зноў, калі вам падабаецца. Starbursts? Добра, добра гучыць. Майце вялікі дзень, хлопцы.