[Гуляе музыка] 

ANDI Пэн: Сардэчна запрашаем у тыдзень 6 падзелу. Мы адхіліліся ад нашага стандарту раздзел час у аўторак днём, каб гэты выдатны нядзелю раніцай. Дзякуй за ўсім, што далучыўся да мяне сёння, але сур'ёзна, апладысменты. 

Гэта даволі вялікі высілак. Я амаль не нават зрабіць яго у той час, але гэта было ў парадку. Так што я ведаю, што ўсе вы толькі што зрабілі яго ў віктарыне. Перш за ўсё, сардэчна запрашаем у адваротны бок гэтага. 

Па-другое, мы пагаворым пра гэта. Мы пагаворым аб віктарыне. Мы пагаворым аб тым, як Вы робіце ў класе. Вы будзеце ў парадку. У мяне ёсць свае віктарыны для Вы ў канцы тут, так што калі вы, хлопцы, жадаеце, каб прыняць Погляд на яго, цалкам нармальна. 

Так хутка перш чым мы пачнем, то Парадак дня на сёння выглядае наступным чынам. Як вы можаце бачыць, мы у асноўным хуткае звальненне праз цэлую кучу структур дадзеных сапраўды, сапраўды, сапраўды хутка. Так як такое, яно не будзе супер інтэрактыўная сёння. Гэта будзе проста мне быццам крычаць рэчы, якія вы, і калі я блытаю вас, калі я іду занадта хутка, дайце мне ведаць. Яны проста розныя дадзеныя структуры, а таксама ў рамках Вашай PSET для гэтага Наступны тыдзень, вы будзеце будзе прапанавана рэалізаваць адзін з іх, магчыма, два з them-- два з іх у PSET. ОК, так што я проста хачу, каб пачаць з некаторых аб'яваў. Мы пойдзем па стэкаў і чэргаў у больш Глыбіня, чым тое, што мы рабілі раней віктарыны. Мы пойдзем па звязаны спіс зноў, зноў, больш падрабязна, чым тое, што мы мелі да віктарыны. І тады мы будзем казаць аб Хэш сталы, дрэвы і спрабуе, якія ўсё даволі неабходна для вашага PSET. І тады мы будзем ісці над некаторымі Карысныя парады для pset5. 

Такім чынам, віктарына 0. Сярэдняя быў 58%. Гэта была вельмі нізкай, і так вы, хлопцы, усе зрабіў вельмі, вельмі добра ў адпаведнасці з гэтым. 

Даволі шмат, правіла, калі вы у стандартным адхіленні ад сярэдняга асабліва, бо мы знаходзімся ў менш зручныя раздзел, вы цалкам нармальна. Вы на верным шляху. Жыццё добрая. 

Я ведаю, што гэта страшна думаць, што Я атрымаў, як 40% на гэтым конкурсе. Я збіраюся на правал гэтага класа. Я абяцаю вам, вы не адбываецца збой клас. Ты зусім нармальна. 

Для тых з вас, хто атрымаў больш сярэдняе, уражвае, уражвае, як сур'ёзна добра зроблена. Я іх са мной. Не саромейцеся, атрымаць іх У канцы часткі. Дазвольце мне ведаць, калі ў вас ёсць пытанні, пытанні з імі. Калі мы дадамо ваш рахунак так, дайце нам ведаць. 

Такім чынам, pset5, гэта сапраўды дзіўна тыдзень Ельскім універсітэце ў сэнсе што наша PSET звязана У сераду ў апоўдні ў тым ліку канцы дня, так што на самой справе Тэарэтычна з-за аўторак апоўдні. Напэўна, ніхто не скончыў на аўторак апоўдні. Гэта зусім нармальна. Мы збіраемся, каб мець прыёмныя гадзіны сёння, а таксама ў панядзелак увечары. І ўсе раздзелы гэтым тыдні будзе фактычна ператварыўся ў майстэрнях, так што не саромейцеся поп любы перасек хочаце, і яны будуць свайго роду міні-PSET семінары для дапамогі ў гэтым. Так як такое, гэта адзіны раздзел, дзе мы навучальны матэрыял. Усе іншыя раздзелы будуць факусоўкі выключна на дапамогу для PSET. Да? 

АЎДЫТОРЫЯ: Дзе рабочыя гадзіннік? 

ANDI Пэн: Гадзіннік tonight-- аб, добры пытанне. Я думаю, што сёння ўвечары офіс гадзін у Teal або абшчын. Калі вы паглядзіце онлайн CS50 і вы ідзяце да офіснай гадзін, павінен быць графік, што кажа вам, дзе ўсе з іх. 

Я ведаю, як сёння ці заўтра чырок, і я думаю, што мы, магчыма, фонду для іншай ночы. Я не ўпэўнены. Добры пытанне. Праверце CS50. 

Прахалодныя, любыя пытанні, якія тычацца Графік на наступны, як тры дні? Я абяцаю вам, хлопцы, як Давіда сказаў, што гэта вяршыня ўзгорка. Вы, хлопцы, амаль няма. Усяго тры больш дзён. Атрымаць там, а затым мы ўсё сыдзе. Мы будзем мець добры CS-бясплатны перапынак. Мы вернемся. Мы ў сеткі ныраць праграмаванне і распрацоўка, рэчы, якія вельмі весела параўнанні у некаторых іншых psets. І гэта будзе холад і мы будзем мець шмат весялосці. Мы будзем мець больш цукерак. На жаль для цукерак. Я забыўся цукеркі. Гэта быў грубы раніцай. Такім чынам, вы, хлопцы, амаль там, і я вельмі ганаруся вамі, хлопцы. 

ОК, так што стэкі. Хто любіў пытанне пра Джэка і яго вопратка на віктарыне? Ніхто? ОК, гэта нармальна. 

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

Па сутнасці, думаць аб стэк, як любы стэк аб'ектаў дзе вы паклалі рэчы на ​​вяршыні, і то вы поп іх зверху. Так ЛИФО з'яўляецца абрэвіятурай нам падабаецца каб use-- Апошняе увайшоў, першым выйшаў. І так, каб працягвацца ў верхняй частцы стэк першым, які выходзіць. І так два члены мы хацелі б звязаць з, што называецца штуршок і поп-музыкі. Калі вы націскаеце на тое стэк, і вы поп яго назад. 

І таму я думаю, гэта свайго роду абстрактнае паняцце для тых з вас, хто хоча бачыць, як практычная рэалізацыя у рэальным свеце. Як многія з вас напісалі эсэ можа быць, як гадзіну, перш чым ён быў з-за, і вы выпадкова выдалілі велізарны кавалак ёй, як выпадкова? І тады тое, што кіраванне раблю мы выкарыстоўваем, каб пакласці яго назад? Control-Z, так? Control-Z, так што колькасць часу што Control-Z выратаваў маё жыццё, выратаваў маю азадак, кожны раз, які рэалізуецца праз стэк. 

Па сутнасці ўся інфармацыя што на вашым дакуменце Word, ён атрымлівае штурхнуў і выскачыў на волю. І так кожны раз, калі вам істотна выдаліць што-небудзь, вы поп яго назад. І потым, калі вам гэта трэба зноў, вам штурхаць яго, што гэта тое, што Ctrl + C робіць. І так рэальны свет функцыя пра тое, як просты структуры дадзеных можа дапамагчы з вашай паўсядзённым жыцці. 

Такім чынам, структура з'яўляецца спосабам, якім мы на самай справе стварыць стэк. Набіраем вызначыць-структуру, а затым мы называем гэта стэк на дне. І ў стэку, у нас ёсць два параметру што мы можам па сутнасці маніпуляваць, так што мы павінны сЬаг зоркі радкоў магутнасці. 

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

Так, напрыклад, гэты выдатны Пытанне было на віктарыне. Па сутнасці, як мы штурхаць на верх стэка. Даволі проста. Калі вы паглядзіце на яго, мы будзем ісці праз гэта. Калі [неразборліва] размер-- памятаеце, калі вы хочаце атрымаць доступ да любой Параметр у структуры, вы імя struct.parameter. 

У гэтым выпадку, з-за імя нашага стэка. Мы хочам, каб адкрыць памер гэта, таму мы робім s.size. Так што, пакуль памер не роўная магутнасці або да тых часоў, а гэта менш, чым ёмістасць, альбо будзе працаваць тут. 

Вы хочаце атрымаць доступ да ўнутранай вашага стэка, так s.strings, і вы збіраецеся пакласці, што новы нумар што вы хочаце ўставіць у там. Давайце проста скажам, мы хочам, каб ўстаўце Int N ў стэк, мы маглі б зрабіць s.strings, кранштэйны, s.size роўны п. Таму што памер дзе мы у цяперашні час у стэку калі мы збіраемся, каб падштурхнуць гэта, мы проста доступ там, дзе памер, тым ток паўната стэка, і мы націскаем Int N на яго. А потым мы хочам, каб пераканацца, што мы таксама павялічваючы памер п, так што мы можам адсочваць мы ў дадалі дадатковы прадмет у стэк. Цяпер у нас ёсць большы памер. Ці значыць гэта, тут сэнс усе, як лагічна гэта працуе? Гэта быў свайго роду хутка. АЎДЫТОРЫЯ: Ці можаце вы перайсці у s.stringss.strings [s.size] яшчэ раз? ANDI Пэн: Вядома, так, што робіць s.size цяперашні час нам дае? АЎДЫТОРЫЯ: Гэта бягучы памер. ANDI Пэн: Роўна, таму бягучы індэкс, што наш памер на, і таму мы хочам, каб паставіць новы цэлы лік што мы хочам, каб ўставіць у s.size. Ці мае гэта сэнс? Таму s.strings, усё, што гэта з'яўляецца імя масіва. Усё гэта звяртаецца да Масіў у нашай структуры, і таму, калі мы хочам, каб размясціць п у гэтым індэксе, мы можам проста адкрыць яго з дапамогай кранштэйнаў s.size. Прахладны. 

Добра, поп, я псевдокод яго для вас, хлопцы, але аналагічнай канцэпцыі. Ці мае гэта сэнс? Калі памер больш, нуля, то вы ведаю, што вы хочаце ўзяць нешта з-за, калі памер не больш за нуль, то вы не маюць нічога ў стэку. 

Такім чынам, вы хочаце толькі выконваць гэты код, ён можа толькі поп, калі ёсць што-тое, каб поп-музыкі. Такім чынам, калі памер больш чым 0, то мінус памер. Мы памяншаем памер, а затым вярнуцца усё, што ўнутры яго, таму што Суя, мы хочам, каб Доступ усё, што захоўваецца ў індэксе вяршыні стэка. Усе сэнс? Калі б я зрабіў, вы, хлопцы напісаць гэта, вы, хлопцы, будзе мець магчымасць запісаць яго? ОК, вы, хлопцы, можаце пагуляць з ім. Не турбуйцеся, калі вы не атрымаеце яго. Мы не паспелі закадаваць гэта сёння, таму што мы ёсць шмат гэтых структур каб прайсці, але па сутнасці псевдокод, вельмі, вельмі падобныя, каб падштурхнуць. Проста выконвайце ўздоўж логікі. Пераканайцеся, што вы звяртаецеся ўсе асаблівасці вашай мадэлі правільна. Да? 

АЎДЫТОРЫЯ: Ці будуць гэтыя слайды і Уся гэтая рэч будзе да сёння-иш? ANDI Пэн: Заўсёды, так. Я збіраюся паспрабаваць паставіць гэта да, як праз гадзіну пасля. Я электроннай пошце Давіда, Дэвід будзе спрабаваць пакласці яго, як праз гадзіну пасля гэтага. 

ОК, так што потым мы пяройдзем у гэты іншы выдатны структура дадзеных, званая чаргу. Як вы, хлопцы, можаце паглядзець тут, А Чаргу, для ангельцаў сярод нас, Усё гэта ўяўляе сабой лінію. Так насуперак таму, што Вы думаеце, што стэк, чаргу менавіта тое, што лагічна вы думаеце. Ён праводзіцца па правілах FIFO, які з'яўляецца першым увайшоў, першым выйшаў. Калі вы першы адзін у лініі, вы першае, што выходзіць з лініі. 

Такім чынам, што мы хацелі б назваць гэта у вызваленні пакета з чаргі і enqueueing. Калі мы хочам нешта дадаць ў нашай чарзе, мы ў чаргу. Калі мы хочам, каб з чаргі, або ўзяць то прэч, мы з чаргі. 

Гэтак жа сэнс, што мы накшталт стварэння элементаў фіксаванага памеру, што мы можа захоўваць пэўны рэчы, але мы можам таксама змяніць, дзе мы размяшчэння Параметры ўнутры іх на аснове таго, які тып Функцыянальнасць мы хочам. Так стэкаў, мы хацелі апошні Адзін з іх, N, каб быць першым з. Чаргу мы хочам першае і быць першае, што. 

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

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

АЎДЫТОРЫЯ: [неразборліва] ANDI Пэн: Роўна, вы хочаце, каб дадаць гэта ў залежнасці ад вы напісалі гэта. Альбо гэта пусты ці пусты. Такім чынам, вы хочаце, каб дадаць яго, верагодна, тут, таму што, калі памер is-- калі яны ўсе поўныя, вы хочаце каб дадаць яго прама тут, прама? 

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

Я не мог адпавядаць гэтай лініі на адзін, але па сутнасці гэта кавалак кода павінны знаходзіцца на адной лініі. Правядзіце як 30 секунд. Зірніце, і зразумець, чаму гэта шлях, што гэта. 

Вельмі, вельмі падобныя структура, вельмі, вельмі Падобная структура, як і папярэдні стэк для, магчыма, за выключэннем таго, аднаго радка кода. І, што адной радкі кода вызначае функцыянальнасць. І гэта сапраўды адрознівае чаргу з чаркі. 

Хто-небудзь хоча прыняць ўдар на тлумачэнне, чаму вы атрымаў гэтую складаную рэч у тут? Мы бачым вяртанне нашага выдатны сябар модуль. Як вы, хлопцы, хутка прыйдзе прызнаць у праграмаванні, амаль у любы час трэба нешта абгарнуць вакол нічога, модуль будзе шлях, каб зрабіць гэта. Так, ведаючы, што, хто-небудзь хоча паспрабаваць тлумачачы, што радкі кода? Так, усе адказы прымаюцца і ўхваляюцца. АЎДЫТОРЫЯ: Вы кажаце мне? ANDI Пэн: Так. АЎДЫТОРЫЯ: О, не прабачце. ANDI Пэн: ОК, так што давайце хадзіць праз гэты код. Таму, калі вы спрабуеце нешта дадаць на чарзе, ў выдатным выпадку, што кіраўнік здараецца каб быць тут, гэта вельмі лёгка для нас проста ісці да канца ўставіць нешта, праўда? Але ўся сутнасць у чарзе што кіраўнік можа на самай справе дынамічна мяняцца ў залежнасці ад дзе хочаце пачатак нашага ц быць, і, як такой, хвост Таксама зменіцца. 

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

Цяпер мы хочам, каб дадаць нешта гэтая чаргу, але, як вы, хлопцы, можаце бачыць, гэта не так проста, як проста дадаць ўсе, што пасля памеру таму што тады мы бяжым з Межы нашага фактычнага масіва. Дзе мы хочам, каб сапраўды дадаць тут. Гэта прыгажосць чарзе з'яўляецца тое, што для нас, візуальна Падобна на тое, што лінія ідзе, як гэта, але пры захоўванні ў структуры дадзеных, яны даюць яго ў якасці як цыкл. Гэта свайго роду абцякае да фронту такім жа чынам што лінія можа таксама абгарнуць вакол у залежнасці ад ўсюды, дзе вас хачу пачатку радка, каб быць. І таму, калі мы бярэм шукаць тут, давайце што мы хочам, каб стварыць Функцыя называецца Дадае. Мы хацелі, каб дадаць Int N ў гэтай в. Калі q.size q-- мы называем гэта нашы дадзеныя structure-- калі наша queue.size ня роўна магутнасці або калі гэта менш, чым ёмістасць, q.strings гэта масіў у нашай ц. Мы збіраемся ўсталяваць што роўна q.heads, што прама тут, плюс q.size Модуль ёмістасцю, якая абгарнуць нас тут. 

Такім чынам, у гэтым прыкладзе, індэкс кіраўніка 1, праўда? Індэкс памеру 0, 1, 2, 3, 4. Такім чынам, мы можам зрабіць 1 плюс 4 модуля нашай здольнасці, якая 5. Што гэта нам дае? Што такое індэкс, які выходзіць з гэтага? 

АЎДЫТОРЫЯ: 0. 

ANDI Пэн: 0, бывае тут, і таму мы хочам, каб мець магчымасць ўставіць ў прама тут. І так гэта раўнанне тут від проста працуе з любымі нумарамі у залежнасці ад таго, дзе ваш галава і ваш памер ёсць. Калі вы ведаеце, што тыя, рэчы, вы ведаеце, менавіта там, дзе вы хочаце ўставіць усё, што пасля чарзе. Ці мае гэта сэнс для ўсіх? 

Я ведаю, накшталт мозгу тізер асабліва, так як гэта прыйшлі ў пасля вашага тэсту. Але, спадзяюся, усё Цяпер можна зразумець Таму гэта рашэнне ці гэта функцыя так, што гэта такое. Любы трохі незразумела з гэтай нагоды? ДОБРА. 

І вось зараз, калі вы хацеў з чаргі, гэта дзе наша галава будзе пераход таму што, калі мы павінны былі з чаргі, мы не зняць канец в. Мы хочам, каб з галавы, праўда? Так што ў выніку, галава зменіцца, і таму, калі вы ў чаргу, Вы павінны сачыць за дзе ваша галава і ваш памер павінны мець магчымасць ўставіць у правільнае становішча. 

І таму, калі вы з чаргі, Я таксама псевдокод яго. Не саромейцеся, калі вы хочаце паспрабаваць кадавання гэта. Вы хочаце, каб перамясціць галаву, праўда? Калі б я хацеў, каб з чаргі, я будзе рухацца галаву над. Гэта будзе галава. 

І наша бягучы памер будзе адняць, таму што мы больш не чатыры элемента ў матрыцы. У нас ёсць толькі тры, а потым мы хочам вярнуцца усё было захоўваць ўнутры кіраўніка, таму што мы хочам, каб гэта Значэнне так, вельмі падобная на стэк. Проста вы прымаеце з іншага месца, і ў вас ёсць, каб перадаць сваю паказальнік у іншым месцы ў якасці выніку. Лагічна, кожны прытрымлівацца? Выдатна. 

ОК, так што мы збіраемся крыху пагаварыць больш падрабязна аб звязаных спісаў таму што яны вельмі, вельмі каштоўны для вас у ходзе гэтым тыдні psets. Звязаныя спісы, як вы, хлопцы, памятаю, яны ўсё з'яўляюцца вузламі, якія вузлы упэўнены значэння як значэння і паказальнік якія звязаны адзін з адным па гэтых паказальнікам. І таму ад таго, як структура мы ствараем вузел тут мы ёсць Int N, які з'яўляецца тое, што значэнне ў краме ці струннага п або што вы хочаце, каб гэта называюць, паўкокс зорка н. Структура, вузел зорка, якая з'яўляецца паказальнікам што вы хочаце, каб у кожным вузле, Вы будзеце мець, што кропка паказальнік да наступнага. Вы будзеце мець галаву з звязанага спісу, што гэта збіраецца паказваюць на астатняй значэння гэтак далей, і гэтак далей пакуль вы ў канчатковым выніку не дойдзе да канца. І гэта апошні вузел проста адбываецца, каб не мець паказальнік. Гэта будзе паказваць на NULL, і што, калі вы ведаеце, што стукнуў канец вашай звязанага спісу калі ваш апошні паказальнік не паказвае ні на што. 

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

АЎДЫТОРЫЯ: Таму што яны ўсе звязаны, але вы цалкам не ведаю, дзе [Неразборліва]. 

ANDI Пэн: Так, менавіта так памятаю што бляск масіва было тое, што ў нас было аператыўнае запамінальная прылада, дзе калі б я хацеў значэнне з індэкса шэсць, я мог проста сказаць індэкс шэсць, дайце мне гэта значэнне. І гэта таму, што масівы сартуюцца ў бесперапынным прасторы памяці у адным месцы, у той час як выгляд звязаных спісаў выпадкова перамяжоўваюцца ўсім, і адзіны спосаб вы можаце знайсці адзін праз паказальнік, які кажа вам, адрас, дзе, што ў наступным вузел. 

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

І таму код, у якім мы рэалізуем гэта, і гэта трохі новага для вас, хлопцы, так як вы Хлопцы на самай справе не казаў пра ці калі-небудзь прагледжана ўказальнікі ў тым, як пошук з дапамогай паказальнікаў, такім чынам, мы будзем ісці праз гэта вельмі, вельмі павольна. Так пошук лагічны, права, давайце прадставім, што мы хочам стварыць функцыю з імем Пошук, які вяртае сапраўднае калі вы знайшлі значэнне ўнутры звязаны спіс, і вяртае ілжывае у адваротным выпадку. Вузел зорка спіс У цяперашні час толькі паказальнік да першага пункту ў вашым звязанага спісу. INT п значэнне, што вы пошук у гэтым спісе. 

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

І тое, як толькі вы атрымаеце тут, у той час як паказальнік ня роўны нулю, так што гэта пятля, у якой мы будзе пасля праходжання астатнія нашым спісе, таму што тое, што адбываецца, калі паказальнік роўны NULL? Мы ведаем, што have-- 

АЎДЫТОРЫЯ: [неразборліва] 

ANDI Пэн: Роўна, таму мы ведаем, што мы дасягнулі канца спісу, дакладна? Калі вы ідзяце сюды, кожны вузел павінен быць накіраваны на іншы вузел і гэтак далей, і гэтак далей пакуль вы не націснеце ў канчатковым выніку хвост вашага звязанага спісу, які мае паказальнік, які проста не паказваюць, чым у любым іншым няма. І так вы ведаеце, што ў асноўным Ваш спіс ёсць яшчэ да да паказальніка ня робіць не роўныя нуль, таму што калі-то ён роўны нулю, Вы ведаеце, што няма больш матэрыялу. 

Так што гэта пятля, у якой мы будзе мець рэальную пошуку. І калі pointer-- вы бачыце што выгляд функцыі стрэлка там? Так што, калі паказальнік паказвае п, калі паказальнік на п роўны роўны п, так, што азначае, што калі паказальнік, што вы пошуку на канцы кожнага вузел фактычна роўна значэнню Вы шукаеце, то Вы хочаце, каб вярнуцца праўда. Так у асноўным, калі вы знаходзіцеся на вузле, які мае значэнне, што вы шукаеце, Вы ведаеце, што вы былі ў стане паспяхова шукаць. 

У адваротным выпадку, вы хочаце ўсталяваць паказальнік на наступны вузел. Гэта тое, што гэтая лінія тут робіць. Паказальнік роўная паказальнік побач. Усе бачыць, як гэта працуе? 

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

Хай гэта замачыць у для няшмат. Гэта будзе даволі важна для вашага PSET. Логіка вельмі простая, магчыма сінтаксічна толькі яго рэалізацыі. Вы, хлопцы, жадаеце, каб Пераканайцеся, што вы разумееце. Прахладны. 

Такім чынам, як мы б ўстаўкі вузлоў, права, у спісе, таму што памятаю, якія тое, што перавагі мець звязаны спіс супраць масіў з пункту гледжання захоўвання? 

АЎДЫТОРЫЯ: Гэта дынамічны, так лягчэй, мэтай якіх 

ANDI Пэн: Роўна, так што гэта дынамічны, які азначае, што ён можа пашырацца і сціскацца у залежнасці ад патрэбаў карыстальніка. І так, у гэтым сэнсе, мы не павінны марнаваць непатрэбнага памяць, таму што я калі я не ведаю, колькі я хачу значэння у краме, гэта не мае сэнсу для мяне стварыць масіў, таму што калі я хачу, каб захоўваць 10 значэнняў і стварыць масіў 1000, гэта шмат марна памяць, выдзелена. Вось чаму мы хочам выкарыстоўваць звязаны Спіс, каб мець магчымасць дынамічна змяніць або паменшыць памер нашай. 

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

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

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

Гэта будзе адзін з рэальных праблем. Адзін з самых галоўных пытанняў Вы будзеце мець на вашым PSET з'яўляецца тое, што вы збіраецеся, каб паспрабаваць стварыць звязаны спіс і дадаць рэчы, але потым проста страціць астатняя частка вашага звязанага спісу. І вы будзеце, як я Не ведаю, чаму гэта адбываецца? І гэта боль, каб прайсці праз і шукаць усё вашыя паказальнікі. 

І я гарантую вам на гэтым PSET, пісаць і маляваць гэтыя вузлы з будзе вельмі, вельмі карысна. Такім чынам, вы можаце цалкам адсочваць дзе ўсе вашы паказальнікі, што адбываецца не так, дзе ўсе вашы вузлы, тое, што вы павінны зрабіць, каб атрымаць доступ да або ўставіць або выдаліць або любога з іх. Усё добра з гэтым? Прахладны. 

Так што, калі мы хацелі паглядзець на код? О, я не ведаю, калі мы можна ўбачыць the-- OK, так у верхняй усё гэта з'яўляецца функцыяй імя устаўка, дзе мы хочам ўставіць Int N ў звязаным спісе. Мы збіраемся прайсці праз гэта. Гэта шмат кода, шмат новага сінтаксісу. Мы ў парадку. 

Так на вяршыні, калі мы хочам, каб стварыць што-небудзь што нам трэба зрабіць, асабліва калі вы Хочаце яго нельга захоўваць у стэку але ў кучы? Мы ідзем у Таноса, праўда? Такім чынам, мы збіраемся стварыць паказальнік. Вузел, паказальнік, новыя роўна Таноса памер вузла таму што мы хочам, што вузел будзе створаны. Мы хочам, каб колькасць памяці, што вузел займае каб быць адведзена для Стварэнне новага вузла. 

А потым мы збіраемся, каб праверыць, ўбачыць, калі новыя роўна роўная нуля. Памятаеце, што мы гаварылі? Што б вы ні Таноса, Што неабходна заўсёды рабіць? Вы заўсёды павінны праверыць, каб убачыць ці не, што гэта NULL. 

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

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

Усё, што мы робім, ствараючы новы вузел, усталяваўшы паказальнік на NULL, а затым перапрызначэння гэта ў галаве, калі мы ведаю, што мы хочам, каб ўставіць яго ў галаву. А потым галава будзе паказваюць на тое новага вузла. Усё ў парадку з гэтым? 

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

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

ОК, так што код будзе тут. Вы, хлопцы, зірніце пасля падзелу. Гэта будзе там. 

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

АЎДЫТОРЫЯ: Гэта будзе па-ранейшаму быць аналагічны працэс з, як прысваенне і паказальнік то прызначэнне гэтага паказальніка, але мы павінны знайсці там. 

ANDI Пэн: Роўна, так дакладна той жа самы працэс, акрамя вас павінны знайсці, дзе менавіта вы хачу, каб новы паказальнік, каб пайсці ў, так што калі я хачу, каб ўставіць у сярэдзіна звязаны list-- ОК, давайце казаць, што наш звязаны спіс. Калі мы хочам, каб ўставіць яе прама тут, мы збіраемся стварыць новы вузел. Мы збіраемся Таноса. Мы збіраемся стварыць новы вузел. Мы збіраемся прызначыць паказальнік гэтага вузла тут. 

Але праблема, якая адрозніваецца адкуль галава з'яўляецца тое, што мы дакладна ведалі, дзе галава. Гэта было прама на першай, ці не так? Але тут мы павінны адсочваць дзе мы уставіўшы яго ў. Калі мы ўстаўляем наш вузел тут, у нас ёсць каб пераканацца, што адным папярэдняя да гэтага вузла гэта той, які прысвойвае паказальнік. Такім чынам, вы павінны выгляд адсочваць дзве рэчы. Калі вам адсочваць, дзе гэта вузел у цяперашні час ўстаўкі ст. Вы таксама павінны адсочваць, дзе папярэдні вузел, які вы глядзіце на Таксама там. Усё добра з гэтым? ДОБРА. 

Як наконт ўстаўкі ў рэшце рэшт? Калі б я хацеў, каб дадаць яго here-- калі я хацеў каб дадаць новы вузел у канец спісу, як я мог бы ісці аб тым, што рабіць? АЎДЫТОРЫЯ: Так сабе, то апошні паказалі на нуль. ANDI Пэн: Так. Дакладна, так што гэта адно У цяперашні час адзначаецца ведаць, і таму я думаю, у гэтым сэнсе, гэта вельмі лёгка дадаць да канца спісу. Усё, што вам трэба зрабіць, гэта ўсталяваць яго роўны нулю, а затым бум. Прама там, вельмі лёгка. Вельмі проста. 

Вельмі падобны на галаву, але лагічна вас хочаце, каб пераканацца, што крокі, вы бераце да рабіць усё гэта, вы вынікаеце. Гэта вельмі лёгка, у сярэдзіне ваш код, ўгразнуць ў, ой, у мяне так шмат паказальнікаў. Я не ведаю, дзе што-небудзь, паказваючы на. Я нават не ведаю, які вузел я на. Што адбываецца? 

Паслабцеся, супакойцеся, зрабіце глыбокі ўдых. Намалюйце свой звязаны спіс. Калі вы кажаце, я ведаць, дзе менавіта Мне трэба ўставіць гэта ў і я дакладна ведаю, як перадаць мой паказальнікі, значна, значна лягчэй прадставіць out-- значна прасцей ня заблудзіцца ў багаў у кодзе. Усё ў парадку з гэтым? ДОБРА. 

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

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

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

Такім чынам, гэта тып дадзеных, Структура цалкам існуе, і структура для вельмі, вельмі проста, за выключэннем ўсё, што вы маючы гэта, а не проста паказальнік на наступны, ў вас таксама ёсць паказальнік на папярэдні. Вось і ўся розніца была. Усё добра з гэтым? Прахладны. 

Добра, так што зараз я сапраўды выдаткаваць, напэўна, як ад 15 да 20 хвілін або навалам у астатні час у раздзеле казаць пра хэш-табліцах. Як многія з вас, хлопцы, прачытаў pset5 спецыфікацыі? Добра, добра. Гэта вышэй, чым 50%, як правіла. Добра. 

Такім чынам, як вы, хлопцы, ўбачыце, Вы задача ў pset5 будзе рэалізаваць слоўнік дзе вы загрузіць больш 140000 слоў што мы даем вам і праверка арфаграфіі гэта супраць усяго тэксту. Мы дамо вам выпадковых шт літаратуры. Мы дамо вам Адысея. Мы дамо вам Іліяду. Мы дамо вам Осцін Пауэрс. 

І ваша задача будзе праверка арфаграфіі кожнае слова за ўсё з тых слоўнікаў па сутнасці, з нашай арфаграфіі. І так ёсць некалькі частак стварэння гэтай PSET, Спачатку вы хочаце быць ў стане фактычна загрузіць ўсе словы ў ваш слоўнік, а затым вам хачу, каб мець магчымасць арфаграфіі і ўсё з іх. І так, як, напрыклад, вы збіраецеся патрабаваць структура дадзеных, якая можа зрабіць гэта хутка і эфектыўна і дынамічна. 

Таму я мяркую, самы просты спосаб зрабіць гэта, вам верагодна стварыць масіў, праўда? Самы просты спосаб захоўвання вас можна стварыць масіў 140000 слоў і проста размясціць іх там, і ўсё затым прайсці іх бінарнага пошуку ці выбараў ці не-- шкада, што гэта сартаванне. Вы можаце сартаваць іх, а затым прайсці іх двайковы пошук або проста лінейны пошук і толькі канчатковыя словы, але займае велізарную колькасць памяці, і гэта не вельмі эфектыўна. 

І такім чынам мы збіраемся пачаць казаць пра спосабы вырабу наша працягласць больш эфектыўным. І наша мэта, каб атрымаць пастаянная часу, дзе гэта амаль як масівы, дзе ў вас ёсць імгненны доступ. Калі б я хацеў, каб шукаць што-небудзь, Я хачу, каб мець магчымасць проста, бум, знайсці яго дакладна, і выцягнуць яго. І так структура, у якой мы будзем становіцца вельмі блізка каб быць у стане атрымаць доступ да пастаянным Час, гэта Святой Грааль у праграмаванні пастаяннага час называецца Хэш-табліцы. І так Дэвід згадвалася раней [Неразборліва] трохі ў лекцыі, але мы збіраемся, каб сапраўды апусканне ў глыбокі гэтым тыдні на кавалак, які адносна як хэш-табліца працуе. 

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

І вось, калі мы хочам для захоўвання ангельскія словы, мы маглі патэнцыйна проста, я не ведаеце, ператварыць ўсе першыя літары ў нейкі нумар. І таму, напрыклад, калі б я хацеў А быць сінонімам apple-- або з індэксам 0, а У сінонімам 1, мы можам мець 26 запісаў што можа проста захоўваць усе літары алфавіт, што мы пачнем з. І тады мы можам мець яблык на індэксам 0. Мы можам мець банан індэкса 1, дыня ў індэксе 2, і гэтак далей, і гэтак далей. І такім чынам, калі я хацеў, каб пошук мой хэш-табліца і доступ яблык, Я ведаю, яблык пачынаецца з Л-і я дакладна ведаю, што яна павінна быць і хэш Табліца з індэксам 0, таму што функцыі, прысвоеныя. 

Так што я не ведаю, мы праграма карыстальніка, дзе Вы будзеце плаціць з arbitrarily-- не адвольна, у спробе задуменна думаць аб добрым раўнанняў каб мець магчымасць распаўсюджвацца усе вашы значэнняў такім чынам, яны могуць лёгка атрымаць доступ да гэта пазней з як ўраўненні што вы, самі, ведаеце. Такім чынам, у сэнсе, калі я хацеў, каб перайсці да манга, я ведаю, пра, гэта пачынаецца з м. Яна павінна быць у індэксе 12. Я не прыйдзецца шукаць ва ўсім. Я ведаю, exactly-- я мог бы проста пайсці ў індэкс 12 і цягнуць гэта. 

Усё ясна, як Функцыя Hash Table працуе? Гэта свайго роду проста больш складаны масіў. Гэта ўсё, што ёсць. ДОБРА. 

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

Так што, калі я спрабую ўставіць пахаваць у хэш табліца, ужо банан на ім, што адбудзецца, калі Вы спрабуеце ўставіць, што? Дрэнныя рэчы, таму што банан ўжо існуе ў індэксе што вы хочаце, каб захоўваць яго ў. Бэры роду, як, ах, што ж мне рабіць? Я не ведаю, куды ісці. Як вырашыць гэтую праблему? 

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

І вось, калі я хацеў ўставіць ягаду, Я ведаю, добра, я збіраюся ўвесці гэта праз мой хэш-функцыі. Я збіраюся скончыць з індэксам 1, а затым я збіраюся быць у стане мець проста менш падмноства гэтага гігант слоўнік 140,000 слова. І тады я магу проста паглядзець праз 1/26, што. 

І так, то я магу проста ўставіць ягады альбо да, альбо пасля таго, як банан у гэтым выпадку? Пасля, праўда? І так вы будзеце жадаць, каб ўставіць гэты вузел пасля банана, і такім чынам Вы збіраецеся ўставіць у хвасце гэтай звязанага спісу. Я збіраюся вярнуцца у гэтым папярэднім слайдзе, так што вы, хлопцы, можаце ўбачыць, як Хэш функцыя працуе. 

Так хэш функцыя гэта раўнанне што вы працуеце выгляд вашага ўваходу праз, каб атрымаць усе індэкс Вы хочаце, каб прызначыць яго да. І так, у гэтым прыкладзе, усе мы хацелі трэба было ўзяць першую літару, сваю чаргу, што ў індэкс, то можа захоўваць, што ў нашай хэш-функцыі. Усё, што мы робім тут мы пераўтварэнні першую літару. Так KeyKey [0] толькі першая літара за ўсё, што радок мы з, мы перадаем ст. Мы пераўтварэнні, што верхні і мы адымаючы загалоўнымі А, таму ўсе, што робіць дае нам шэраг у якіх мы можам хэш нашы каштоўнасці на. 

А потым мы збіраемся вярнуцца хэш модуль ПАМЕР. Будзьце вельмі, вельмі асцярожныя, таму, тэарэтычна, тут Ваш хэш-значэнне можа быць бясконцым. Гэта можа быць проста пайсці далей і далей і далей. Гэта можа быць некаторыя сапраўды, сапраўды вялікае значэнне, а таму, што ваш хэш-табліцы, што Вы стварылі толькі мае 26 індэксаў, Вы хочаце, каб пераканацца, што ваш modulusing, так што вы ня run-- гэта тое ж самае што ў якасці queue-- так што вы не сышлі з Дно Вашай хэш-функцыі. 

Вы хочаце, каб абгарнуць яго назад вакол гэтак жа, як у [неразборліва], калі ў вас, як вельмі, вельмі вялікая літара, вы не хачу, каб проста бегчы канец. Тое ж самае тут, вы хочаце, каб пераканацца, што ён не працуе з канца, накладваючыся вакол верхняй частцы табліцы. Так што гэта проста вельмі проста хэш функцыя. Усё, што зрабіў першы ўзяць Ліст якой наш прыход быў і ператварыць гэта ў індэкс, мы маглі б паставіць у нашу хэш-табліцы. 

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

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

Калі б я хацеў, каб insert--, што гэта садавіна, які пачынаецца з, я не ведаю B, акрамя ягад, банан. 

АЎДЫТОРЫЯ: Ажына. 

ANDI Пэн: Blackberry, ажына. Дзе ажыны ісці сюды? Ну, мы на самай справе не сартуюцца гэта яшчэ, але тэарэтычна калі б мы хацелі, каб гэта ў алфавітным парадку, дзе павінны BlackBerry ісці? 

АЎДЫТОРЫЯ: [неразборліва] 

ANDI Пэн: Роўна, пасля тут, праўда? Але так як гэта вельмі складана reorder-- Я думаю, гэта да вас, хлопцы. Вы, хлопцы, можаце цалкам ажыццявіць усе, што вы хочаце. Чым больш эфектыўны спосаб рабіць гэта, магчыма, будзе сартаваць ваш звязаны спіс у алфавітным парадку, і таму, калі вы ўстаўкі рэчы, вы хочаце каб пераканацца, што ўставіць іх ў алфавітным парадку так што потым, калі вы спрабуюць шукаць іх, Вы не павінны прайсці ўсе. Вы сапраўды ведаеце, дзе яна ёсць, і гэта прасцей. 

Але калі вы, здаецца, ёсць рэчы перамяжоўваюцца выпадкова, Вы па-ранейшаму будзеце мець прайсці яго ў любым выпадку. І таму, калі я хацеў, каб проста ўстаўце ажыны тут і я хацеў, каб шукаць гэта, ведаю, ох, ажына павінны пачаць з індэксам 1, так што я ведаю, імгненна проста шукаць на 1. І тады я магу роду прайсці звязаны спіс пакуль я не атрымаць да BlackBerry, і then-- так? 

АЎДЫТОРЫЯ: Калі вы спрабуеце create-- Я думаю, як гэта вельмі просты хэш функцыя. І калі мы хочам, каб зрабіць некалькі слаёў, што, як, ОК, мы хочам, каб аддзяліць ў як і ўсе алфавітна а потым зноў хацеў іншы набор з літар алфавіту ў працягу, што, мы пакласці як хэш табліца ў хэш-табліцы, ці як функцыі ўнутры функцыі? Або that-- 

ANDI Пэн: Так ваш хэш function-- свой хэш-табліцу можа быць як вялікі, як вы хочаце. Такім чынам, у гэтым сэнсе, я думаў, гэта было вельмі лёгка, вельмі проста для мяне, каб проста накшталт аснове на літары першага слова. І так ёсць толькі 26 варыянтаў. Я магу атрымаць толькі 26 варыянтаў з 0 да 25, таму што яны могуць толькі пачаць ад А да Z. Але калі вы хочаце дадаць, мабыць, больш за складанасці або хутчэй бегчы да вашага часу Хэш-табліца, вы абсалютна можа зрабіць усё віды рэчаў. Вы можаце зрабіць свой уласны Раўнанне, якое дае вам больш рассылання ў слоў, то пры пошуку, гэта будзе хутчэй. 

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

Але тады вы павінны высветліць спосаб сартавання рэчы так, каб яны ў належным вядро яны павінны быць у. Але потым, калі вы на самой справе хачу паглядзець на гэтага вядра, гэта нашмат хутчэй, таму што ёсць менш рэчы ў кожным вядры. І так, так, гэта на самай справе трук для вас, хлопцы ў pset5 з'яўляецца тое, што вы будзеце выклік проста стварыць усё, што з'яўляецца найбольш эфектыўным Функцыя Вы можаце думаць, каб быць магчымасць захоўвання і праверкі гэтых значэнняў. 

Усяго да вас, хлопцы Аднак вы хочаце, каб гэта зрабіць, але гэта сапраўды добрая кропка. Тое, што такая логіка вы хачу, каб пачаць думаць аб , Ну, чаму я не зрабіць больш вядра. І тады я павінен шукаць менш рэчаў, і тады, магчыма, я маюць розную хэш-функцыю. 

Так, ёсць шмат спосабаў зрабіць гэта PSET, некаторыя хутчэй, чым іншыя. Я цалкам збіраюся проста паглядзець, як хутка стаў самым хуткім вы, хлопцы, быць у стане атрымаць вашыя функцыі на працу. ОК, усё добра на Іерархіі сервераў і хэш-табліцы? Гэта на самай справе, як вельмі просты паняцце, калі вы думаеце пра гэта. Усё гэта з'яўляецца падзел ўсё Вашы ўваходы ў вёдры, сартуючы іх, а затым шукаюць у спіс, што там звязана з. 

Прахладны. Добра, зараз у нас ёсць рознага роду структуры дадзеных, якая называецца дрэвам. Давайце ісці далей і казаць пра спробы якія істотна адрозніваюцца, але ў той жа катэгорыі. Па сутнасці, усё дрэва замест гэтага арганізацыі дадзеных у лінейным чынам што хэш-табліца does-- вас Ведаеце, ён атрымаў верх і ніз а затым вы накшталт спасылаюцца прэч it-- ў Дрэва мае верхні, што вы называеце корань, і то ён мае лісце ўсё вакол яго. 

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

Хэш табліца выглядае як табліца. Дрэва выглядае як дрэва. Усё гэта з'яўляецца асобным спосаб арганізацыі вузлоў у залежнасці ад таго, што вашыя патрэбы. 

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

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

Дык вось, калі я збіраюся шукаць значэнне 66, я магу пачаць у 55 гадоў. Гэта больш, чым 66 55? Так, гэта, так што я ведаю, што я муз пошук я н права паказальнік гэтага дрэва. Я іду да 77. ОК, гэта менш, чым 66 або больш, чым 77? Гэта менш, чым, так што вы ведаеце, о, які павінен быць злева вузел. 

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

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

Добра, мы на самай справе адбываецца проста ўзяць некалькі хвілін. Такім чынам, мы збіраемся, каб вярнуцца сюды. Як я ўжо казаў, Я накшталт растлумачыў логіка, як мы будзе шукаць праз гэта. Мы збіраемся, каб паспрабаваць pseudocoding гэты, каб убачыць калі мы можам роду прымяніць Тая ж логіка бінарнага пошуку на іншы тып структуры дадзеных. Калі вы, хлопцы, жадаеце, каб прыняць як пара хвілін, каб проста думаць пра гэта. ДОБРА. Добра, я збіраюся на самай справе проста не дасць вам the-- няма, мы будзем казаць аб псевдокоде першым. Дык хто-небудзь хоча даць ўдар на тое, што першае, што вы хочаце рабіць, калі Вы пачынаеце пошук па? Калі мы шукаем значэнне 66, што Першае, што мы хочам рабіць, калі мы хочам, каб гэты бінарны пошук дрэва? 

АЎДЫТОРЫЯ: Вы хочаце, каб глядзець прама і паглядзіце налева і ўбачыце [неразборліва] большая колькасць. 

ANDI Пэн: Так, менавіта так. Такім чынам, вы будзеце глядзець на корані. Там шмат спосабаў вы можаце патэлефанаваць гэта, вашы бацька вузла людзі кажуць. Я хацеў бы сказаць, таму што корань гэта як корань дрэва. Вы збіраецеся глядзець на Ваш каранёвай вузел, і вы ўбачыце 66 больш або менш, чым 55. І калі гэта больш, чым, ну, гэта больш, чым, дзе мы хочам, каб паглядзець? Куды мы хочам шукаць зараз, праўда? Мы хочам, каб пошук у Правая палова гэтага дрэва. 

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

Я збіраюся паказаць Вам фактычны Код, і гэта шмат кода. Няма неабходнасці хвалявацца. Мы будзем казаць праз яго. 

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

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

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

Ці мае гэта сэнс для ўсіх? Так як бінарны пошук, якія захоўваюць Магчымасці звязаных спісаў. Халодны, і так другі тып структуры дадзеных вы, хлопцы можа паспрабаваць рэалізаваць на PSET, ў вас ёсць толькі адзін спосаб выбраць. Але, магчыма, альтэрнатыўны метад хэш-табліца з'яўляецца тое, што мы называем сінтаксічнага дрэва. 

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

Такім чынам, вузел, як мы будзе вызначаць сінтаксічнага дрэва што мы хочам, каб мець Лагічнае, з слова, праўда? Такім чынам, вузел Лагічны як сапраўднае або ілжывае, у першую чаргу ў галаву што масіў, гэтае слова? Па-другое, вы хочаце, каб паказальнікі да таго, што астатнія з іх. Трохі складаны, трохі абстрактна, але Я растлумачу, што гэта ўсё сродкі. 

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

І тады ў вас ёсць ад 0 да 26 лісты, якія вы можаце захоўваць. Калі б я хацеў, каб пошук для лятучай мышы, я іду да вяршыні і я гляджу на В. Я знаходжу ў маім B масіў, так што я ведаю, добра, гэта B слова? У гэта не тое слова, так, такім чынам, Я павінен працягваць пошукі. Я іду ад B, і я з нецярпеннем да паказальнік, які паказвае на B і я бачу яшчэ адзін масіў інфармацыі, тая ж структура, што ў нас было раней. 

І here-- ой, наступны Ліст у [неразборліва] гэта А. Такім чынам, мы з нецярпеннем ў гэтым масіве. Мы знаходзім восьмы значэнне, і тады мы паглядзіце, ох, эй, гэта тое, што словам, гэта У-А слова? Гэта не словы. Мы павінны працягваць пошукі. 

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

Так, то вы можаце роду пошук ўніз. Замест таго, каб хэшавання функцыю і прысваенне значэння, звязанага спісу, вы можаце проста рэалізаваць Trie, што пошук downwords. Сапраўды, сапраўды складанай рэчы. Ня лёгка думаць пра, таму што я, як пляўкі так шмат структур дадзеных з у вас, але робіць усё роду зразумець, як логіка гэта працуе? 

ОК, крута. Так B-A-T, а затым Вы збіраецеся шукаць. У наступны раз вы збіраецеся каб бачыць, аб, эй, гэта праўда, Такім чынам, я ведаю, што гэта павінна быць слова. 

Тое ж самае для заапарка. Дык вось у чым справа прама цяпер, калі мы хацеў шукаць заапарку, прама зараз, У цяперашні час заапарк не слова ў нашым слоўніку таму што, як вы, хлопцы, можаце бачыць, Першае месца, што мы маем лагічны вяртае ісціну ў канцы маштабавання. У нас ёсць Z-O-O-M. 

І вось, мы на самай справе не маюць слова, заапарк, у нашым слоўніку таму што гэты сцяжок не ўсталяваны. Такім чынам, кампутар не ведаю, што заапарк гэтае слова таму што шлях, які мы захоўваць яго, толькі зум тут на самай справе мае лагічнае значэнне які быў ператвораны праўда. Так што, калі мы хочам, каб ўставіць Слова, заапарк, у нашым слоўніку, як бы мы ісці аб тым, што рабіць? Што мы павінны зрабіць, каб пераканацца, што нашы кампутар ведае, што Z-О-О слова а не першае слова Z-О-О-М? 

АЎДЫТОРЫЯ: [неразборліва] 

ANDI Пэн: Роўна, мы хочаце, каб пераканацца, што гэта вось, што Лагічнае значэнне галачка, што гэта праўда. Z-О-О, то мы збіраемся праверыць, што так мы дакладна ведаем, эй, заапарк з'яўляецца слова. Я збіраюся расказаць кампутар, што гэтае слова так што, калі кампутар правярае, ён ведае, што заапарк гэтае слова. 

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

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

І так потым прыходзіць Праблема як бы мы ісці аб ўстаўцы то што на самой справе не? Так што давайце проста сказаць, што мы хочам, каб ўставіць слова, ванна, у нашай сінтаксічнага дрэва. Як вы, хлопцы, можаце ўбачыць, як у цяперашні час усё, што мы маем цяпер, гэта У-А-Т, і гэтая новая структура дадзеных ёсць меў пінту, што паказаў на нуль, таму што мы лічым, што, ох, няма ніякіх слоў, пасля B-A-T, чаму мы павінны трымаць маючы рэчы пасля гэтага Т. 

Але праблема ўзнікае, калі мы робім вам хочаце мець слова, якое прыходзіць пасля Т-х. Калі ў вас ёсць ванна, вы збіраецца хочаце H права. І так як мы збіраемся зрабіць гэта мы збіраемся стварыць асобны вузел. Мы не вылучыць любую суму памяці для гэтай новай масіва, і мы збіраемся перапрызначыць паказальнікі. 

Мы збіраемся прызначыць Н, У першую чаргу, гэта нулявы, мы збіраемся пазбавіцца. Мы збіраемся, каб мець Н кропка ўніз. Калі мы бачым H, мы хочам яго ісці кудысьці яшчэ. 

Тут, мы можам праверыць з так. Калі мы трапілі ў H пасля Т, аб, то мы ведаем, што гэтае слова. Лагічнае збіраецца вярнуцца праўда. Усё ясна, як гэта адбылося? ДОБРА. 

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

І так pset4, з 5-- ой, што гэта няправільна. Pset5 з'яўляецца памылкамі друку. Як я ўжо казаў раней, вы будзеце, калі-то зноў, спампаваць зыходны код з нас. Там будзе тры асноўных рэчы, якія вы будзеце загружаць. Вы спампаваць слоўнікі, KERS, і тэксты. 

Усе гэтыя рэчы з'яўляюцца альбо слоўнікі слоў што мы хочам, каб вы праверыць ці выпрабаванне інфармацыі што мы хочам, каб вы праверка арфаграфіі. І так слоўнікі мы даем вам збіраемся каб даць вам канкрэтныя словы, якія мы хочам захоўваць як-то ў спосабе, якім гэта больш эфектыўным, чым масіў. І тады тэксты будзе тое, што мы прашу вас праверыць правапіс, каб пераканацца, усе словы ёсць рэальныя словы. 

І так тры блокі праграмы, якія мы дамо вам называюцца dictionary.c, dictionary.h і speller.c. А так усё робіць, dictionary.c тое, што вы прасілі рэалізаваць. Ён загружае словы. Гэты заклён правярае іх, і гэта гарантуе, што ўсё правільна адсутнічае. 

diction.h гэта проста файл бібліятэкі які аб'яўляе усе гэтыя функцыі. І speller.c, мы збіраемся даць вам. Вам не трэба змяняць любы з яго. Усе speller.c робіць гэта прыняць, што загружае яго, правярае хуткасць яго, тэстуе адзнаку ў накшталт як хутка вы зможаце зрабіць рэчы. 

Гэта пішучы. Толькі не зьвязвайцеся з ім, але зрабіць што вы разумееце, што ён робіць. Мы выкарыстоўваем функцыю пад назвай getrusage, што тэстуе прадукцыйнасць вашага загаворы праверкі. Усё гэта робіць у асноўным пратэставаць Час усё ў слоўніку, таму пераканайцеся, што вы разумееце, што. Будзьце асцярожныя, каб не звязвацца з ім ці астатняе ўсё не будзе працаваць належным чынам. 

І вялікая частка гэтай праблемы з'яўляецца для вы, хлопцы, сапраўды змяніць dictionary.c. Мы збіраемся даць вам 140000 слоў у слоўніку. Мы збіраемся даць вам тэкст файл, які мае тыя словы, і мы хочам, каб вы маглі арганізаваць іх у хэш-табліцы або сінтаксічнага дрэва таму што, калі мы просім вас загавор check-- ўявіце сабе, калі вы загавор праверкі, як Адысея Гамера. Гэта як гэтага велізарнай, велізарнай тэсту. 

Уявіце сабе, калі кожны Слова, якое вы павінны былі шукаць праз масіў 140000 значэнняў. Гэта будзе доўжыцца вечна для вашай машыны, каб бегчы. Менавіта таму мы хочам, каб арганізаваць нашы дадзеныя ў больш эфектыўных структур дадзеных такіх як хэш-табліцы або сінтаксічнага дрэва. І тады вы, хлопцы, можаце выгляд калі вы шукаць доступ рэчы больш лёгка і больш хутка. 

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

Можа быць, вы хочаце, каб дадаць усе літары разам. Можа быць, вы хочаце, каб зрабіць падабаецца дзіўныя рэчы да адказнасці шэраг лістоў, што заўгодна. Да вас, хлопцы, як вы хочаце зрабіць. Калі вы хочаце зрабіць хэш-табліцу, калі вы хачу паспрабаваць сінтаксічнага дрэва, цалкам залежыць ад вас. Я папярэджваю вас загадзя, што Trie, як правіла, крыху больш складана толькі таму, што ёсць шмат больш паказальнікі адсочваць. Але цалкам да вас, хлопцы. Гэта значна больш эфектыўна, у большасці выпадкаў. Вы хочаце, каб сапраўды быць у стане трымаць трэк ўсіх вашых паказальнікаў. Як зрабіць тое ж самае што я тут раблю. Калі вы спрабуеце ўставіць значэння ў хэш-табліцу або выдаліць, пераканайцеся, што вы сапраўды адсочвання дзе ўсё, таму што гэта сапраўды лёгка, калі я спрабую ўставіць, як слова, Эндзі. Давайце проста скажам, што гэта рэальнае слова, слова, Эндзі, ў гіганцкі спіс з слоў. 

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

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

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

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

АЎДЫТОРЫЯ: Мы дазволілі, калі хацеў даследаваць хуткія спосабы зрабіць хэш-табліцы на сайце, мы можам зрабіць што і цытаваць код чужое? ANDI Пэн: Так, цалкам нармальна. Так што, калі вы, хлопцы, чытаць спецыфікацыі, ёсць лінія у спецыфікацыі сказана, што вы, хлопцы цалкам вольныя даследаваць хэш функцыі на тое, што некаторыя з хуткіх хэш-функцый весці справы праз ў Пакуль вы прывесці гэты код. Такім чынам, некаторыя людзі ўжо высветлілі хуткіх спосабаў рабіць праверку арфаграфіі, хуткага спосабы захоўвання інфармацыі. Усяго да вас, хлопцы, калі вам хачу проста ўзяць, так? Пераканайцеся, што вы цытавання. Задача тут сапраўды што мы спрабуем праверыць пераканаўшыся, што вы ведаеце, Ваш шлях вакол паказальнікі. Як далёка, як вы рэалізацыі фактычны хэш-функцыя і, падышоўшы з падобным матэматыка, каб зрабіць гэта, вы, хлопцы, можаце даследаваць ўсе метады онлайн вы, хлопцы, жадаеце. Да? 

АЎДЫТОРЫЯ: Ці можам мы Прывяду толькі з дапамогай [неразборліва]? 

ANDI Пэн: Так. Вы можаце проста ў свой каментар, Вы можаце цытаваць, як, ну, ўзятыя з балбатня, балбатня, йада, хэш-функцыя. Хто-небудзь ёсць якія-небудзь пытанні? Мы на самай справе веяў праз падзел і сёння. Я буду сюды, каб адказаць на пытанні, а таксама. 

Акрамя таго, як я сказаў, офіс гадзін сёння вечарам і заўтра. Спецыфікацыя гэтым тыдні на самай справе супер проста і супер кароткія чытаць. Я хацеў бы прапанаваць зірнуць, проста прачытаць цалкам ад яго. 

І на самай справе Zamyla правядзе вас праз кожную з функцый неабходна рэалізаваць, і таму вельмі, вельмі ясна, як усе. Проста пераканайцеся, што вы адсочванне паказальнікаў. Гэта вельмі складаная PSET. 

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

І так поўнае і абсалютнае вера ў вас хлопцы, каб мець магчымасць перамагчы нашу [неразборліва] Напісанне. Я на самой справе не якой-небудзь пісьмовае шахту пакуль няма, але я збіраюся напісаць мой. Таму, калі вы пішаце тваё, я буду пісаць мае. Я збіраюся паспрабаваць зрабіць мой хутчэй, чым ваша. Мы ўбачым, хто мае самы хуткі адзін. 

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