Джэйсан Хиршхорн: Вітаю ўсіх у раздзеле Seven. Мы знаходзімся ў тыдзень сем курса. І мае быць чацвер Дзень усіх Святых, так што я апранутыя як гарбуз. Я не мог нахіліцца і пакласці на мае чаравікі, дык вось чаму я проста насіць шкарпэткі. Я таксама нічога не насіць пад гэта, таму я не магу зняць яго, калі гэта адцягваючы да вас. Загадзя прашу прабачэння за гэта. Вам не трэба прадставіць што адбываецца. Я нашу баксёраў. Так што ўсё добра. 

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

Зноў жа, pset6 з'яўляецца памылкамі друку, PSET на гэтым тыдні. І гэта таксама заклікае вас, і я рэкамендуем вам, каб выкарыстоўваць некаторыя іншыя рэсурсы спецыяльна для гэтай PSet. У прыватнасці, тры ў мяне ёсць пералічаныя на экране - GDB, які мы былі знаёмыя з і выкарыстоўвалі на некаторы час цяпер, з'яўляецца будзе вельмі карысна на гэтым тыдні. Так што я паклаў, што тут. Але кожны раз, калі вы працуеце з C, вы заўсёды павінны выкарыстоўваць GDB для адладкі праграм. На гэтым тыдні таксама Valgrind. Хто-небудзь ведае, што Valgrind робіць? 

АЎДЫТОРЫЯ: Ён правярае уцечак памяці? 

Джэйсан Хиршхорн: Valgrind правярае ўцечкі памяці. Так што калі вы Таноса нешта ў вашым Праграма, вы просіце памяці. У канцы праграмы, у вас ёсць напісаць бясплатна на ўсё, што вы malloced даць памяць назад. Калі вы не пішаце бясплатна ў канцы і ваша праграма прыходзіць да высновы, усё аўтаматычна быць вызваленыя. А для невялікіх праграм, гэта не так ужо страшна. Але калі вы пішаце доўгі ход праграма, якая ня выйдзе, абавязкова, на працягу некалькіх хвілін або пару секунд, затым ўцечкі памяці можа стаць велізарная здзелка. 

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

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

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

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

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

Там вельмі шмат адбываецца на экране. Але ўсё гэта павінна быць адносна знаёмыя з вамі. На першай лініі, мы аб'явіць новы вузел. А потым ўнутры гэтай новага вузла, я паставіў цэлы лік у гэтым вузле да аднаго. Мы бачым, на наступным радку я раблю Е каманда, але я шэрым колерам каманда Е, таму што на самой справе Важнай часткай з'яўляецца гэтая лінія тут - new_node.n. Што кропка на ўвазе? 

АЎДЫТОРЫЯ: Перайдзіце ў вузел і ацаніць кошт н для яго. 

Джэйсан Хиршхорн: Гэта Цалкам дакладна. Dot азначае пераходу да паўночная частка гэтага новага вузла. У наступным радку што робіць? Майкл. 

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

Джэйсан Хиршхорн: Дык гэта не стварыць новы вузел. Ён стварае тое, што? 

АЎДЫТОРЫЯ: Паказальнік. 

Джэйсан Хиршхорн: паказальнік на вузел, як паказана гэтым вузел * тут. Такім чынам, гэта стварае паказальнік на вузел. І які вузел ён паказваючы каб, Майкл? 

АЎДЫТОРЫЯ: Новы вузел? 

Джэйсан Хиршхорн: Новы вузел. І гэта паказвае там, таму што мы даў яму адрас новага вузла. І зараз у гэтай лініі мы бачым два розных спосабу выказваючы тое ж самае. І я хацеў бы адзначыць, як гэтыя дзве рэчы аднолькавыя. У першым радку мы разыменовать паказальнік. Так мы ідзем да вузла. Гэта тое, што гэтая зорка азначае. Мы бачылі, што перад з паказальнікамі. Да гэтага вузла. Вось у дужках. А потым доступ праз аператара пункту н элементам гэтага вузла. 

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

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

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

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

Давайце разбярэм, што ўніз і ісці трохі павольней. Я збіраюся паказаць на борце. Так у нас ёсць вузел пяць, што мы стварылі ў mallocs. Чаму ўсе смяюцца? Жартую. ОК. Такім чынам, мы malloced пяць. Мы стварылі гэты вузел дзесьці ў іншым месцы. У нас ёсць гэта гатовыя пайсці. Мы пачынаем у пярэдняй частцы наш спіс з двума. І мы хочам, каб ўставіць у адсартаваным моды. 

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

АЎДЫТОРЫЯ: Патэлефануйце паказальнік да наступнага вузла. 

Джэйсан Хиршхорн: І чаму мы ідзем да наступнага? 

АЎДЫТОРЫЯ: Таму што гэта Наступны вузел у спісе. І мы ведаем толькі, што іншае месца. 

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

Пяць больш чатырох. Так мы працягваем. І зараз мы ў шэсць. І што ж мы бачым у шэсць? Так, Карлас? 

АЎДЫТОРЫЯ: Шэсць больш пяці. 

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

АЎДЫТОРЫЯ: Два. 

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

АЎДЫТОРЫЯ: Вы павінны былі б атрымаць, што пустую кропку. Замест таго, нулявую кропку, якую вы павінны былі б дадаць элемент, а затым ёсць ён паказваў на дзевяці. 

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

АЎДЫТОРЫЯ: Прытрымлівайцеся яго на пачатку ці ў канцы. 

Джэйсан Хиршхорн: Прытрымлівайцеся яго на пачатак ці канец. Які мы павінны рабіць? Бобі? Чаму канец? 

АЎДЫТОРЫЯ: Таму што пачатак ўжо запоўнены. 

Джэйсан Хиршхорн: ОК. Пачатак ужо запоўненая. Хто хоча спрачацца з Бобі. Маркус. 

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

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

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

АЎДЫТОРЫЯ: Вярнуцца хлусня? 

Джэйсан Хиршхорн: Вярнуцца ілжывым. Мы не знайшлі яго. Калі вы дойдзе да канца спісу і Вы не знайшлі нумар, які вы знаходзіцеся шукаю, гэта не там. Любыя пытанні аб знайсці? Калі б гэта было адсартаваны спіс, што б быць рознымі для нашага пошуку? Так. 

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

Джэйсан Хиршхорн: Цалкам дакладна. Так што, калі гэта адсартаваны спіс, калі мы дабяромся да нешта, што гэта больш, чым тое, што мы шукаем, мы не павінны працягваць ісці ў канец спісу. Мы можам у гэтай кропцы вярнуцца ілжывым таму што мы не збіраемся, каб знайсці яго. Пытанне цяпер, мы гаварылі пра захоўваючы звязаныя спісы сартуюцца, трымаць іх без сартавання. Гэта будзе тое, што вы знаходзіцеся , Верагодна, прыйдзецца думаць аб калі праблема кадавання ўсталяваць пяць, калі вы выбраць хэш-табліцу з асобнай ланцужкі падыход, які мы пагаворым крыху пазней. 

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

Нарэшце, выдаленне. Мы бачылі выдалення. Гэта падобна на пошук. Мы шукаем элемента. Скажыце, што мы спрабуем выдаліць шэсць. Так мы знаходзім шэсць прама тут. Справа ў тым, што мы павінны пераканацца, што мы рабіць тое, што ўсё, што паказвае на шэсць - як мы бачым у дзеянні два ўніз тут - што б ні паказваючы на ​​шасці патрэбаў у прапусціць шэсць цяпер і быць зменены на усе шэсць паказвае на. Мы не хочам, каб калі-небудзь сіротам астатнюю частку наш спіс, забыўшыся ўсталяваць, што папярэдняя паказальнік. А потым часам, у залежнасці па праграме, яны проста выдаліць гэты вузел цалкам. Часам вы хочаце, каб вярнуцца значэнне, якое знаходзіцца ў гэтым вузле. Дык вось, як выдаленне работ. Любыя пытанні па выдаліць? 

АЎДЫТОРЫЯ: Дык што, калі вы хочаце сцерці гэта, вы б проста выкарыстоўваць бясплатна, таму што як мяркуецца, было malloced? 

Джэйсан Хиршхорн: Калі вы хочаце, каб вызваліць тое, што зусім дакладна, і вы malloced яго. Скажам мы хацелі вярнуцца гэта значэнне. Мы маглі б вярнуцца шэсць, а затым бясплатна гэты вузел і выклік бясплатна на яго. Ці мы, верагодна, тэлефанаваць бясплатна першы , А затым вярнуцца шэсць. 

ОК. Так давайце пяройдзем да практыкі кадавання. Мы збіраемся, каб закадаваць тры функцыі. Першы з іх завецца insert_node. Так у вас ёсць код, які я паслаў па электроннай пошце вам, і калі вы глядзіце гэта пазней Вы можаце атрымаць доступ да кода ў linked.c на сайце CS50. Але ў linked.c, ёсць некаторыя шкілет код, які ўжо была напісана для вас. А тут яшчэ пару ФУНКЦЫІ вам трэба напісаць. 

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

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

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

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

Давайце пачнем з напісання некаторых псевдокод на дошцы. Хто можа даць мне першую лінію псевдокод для гэтай праграмы? Для гэтай функцыі, а - insert_node. Олдэн? 

АЎДЫТОРЫЯ: Таму першае, што я зрабіў, было стварыць новы паказальнік на вузел і I ініцыялізацыі ён паказваючы на ​​тое ж самае рэч, якая спіс паказвае на. 

Джэйсан Хиршхорн: ОК. Так вы ствараеце новы паказальнік у спіс, а не да вузла. 

АЎДЫТОРЫЯ: Дакладна. Так. 

Джэйсан Хиршхорн: ОК. А потым што мы хочам зрабіць? Што пасля гэтага? А як наконт вузла? У нас няма вузла. Мы проста мець значэнне. Калі мы хочам, каб ўставіць вузел, што мы трэба зрабіць, перш чым мы можам нават думаць пра уставіўшы яго? 

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

Джэйсан Хиршхорн: Выдатна. Давайце зробім - ОК. Не можаце дасягнуць гэтага максімуму. ОК. Мы збіраемся ісці ўніз, а затым мы выкарыстоўваем два слупкі. Я не магу пайсці, што - ОК. Стварыце новы вузел. Вы можаце стварыць яшчэ адзін паказальнік на спіс ці вы можаце проста выкарыстоўваць спіс, як яна існуе. Вы сапраўды не трэба гэтага рабіць. 

Так мы ствараем новы вузел. Вялікі. Гэта тое, што мы робім у першую чаргу. Што далей? 

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

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

АЎДЫТОРЫЯ: Вызваліце ​​яго. 

Джэйсан Хиршхорн: Так. Напэўна вызваліць яго. ОК. Што мы робім пасля таго як мы стварыць новы вузел? Эні? 

АЎДЫТОРЫЯ: Ставім лік у вузле? 

Джэйсан Хиршхорн: Цалкам дакладна. Мы, лік - мы Malloc прастору. Я збіраюся пакінуць гэта усе як адзін радок. Але вы маеце рацыю. Мы Malloc прабел, а затым мы ставім нумар цалі Мы можам нават ўсталяваць паказальнік частка яе да нуля. Вось менавіта. І тое што казаць аб пасля гэтага? Мы намаляваў гэтую карціну на дошцы. Дык што ж нам рабіць? 

АЎДЫТОРЫЯ: Мы ідзем па спісе. 

Джэйсан Хиршхорн: Прайсціся па спісе. ОК. І што ж мы правяраем для кожнага вузла. Курт, што ж мы правяраем для кожнага вузла? 

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

Джэйсан Хиршхорн: ОК. Я збіраюся зрабіць - так, добра. Так што гэта п - Я збіраюся сказаць, калі значэнне больш чым гэты вузел, то што ж нам рабіць? 

АЎДЫТОРЫЯ: Ну, тады мы ўстаўляем рэч прама перад гэтым. 

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

АЎДЫТОРЫЯ: Тады вам проста працягваць ісці калі гэта не апошні. 

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

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

Джэйсан Хиршхорн: Так. Улічваючы гэта - Маркус правоў. Мы маглі б, можа быць, зроблена нешта іншае. Але, улічваючы, што мы стварылі яго, тут мы павінны вызваліць, а затым вярнуцца. Аб хлопчык. Так лепш? Як гэта? ОК. Бясплатны і тое што мы вярнуцца, [неразборліва]? ОК. Мы не напісалі нічога? Дык куды мы адсочванне папярэдняга вузла? 

Залы: Я думаю, што гэта пойдзе пасля стварэння новага вузла. 

Джэйсан Хиршхорн: ОК. Таму ў пачатку мы, напэўна, - так, мы можам стварыць паказальнік на новы вузел, як папярэдні паказальнік вузла і бягучы паказальнік вузла. Так што давайце ўставіць, што тут. Стварэнне бягучы і папярэдні паказальнікі на вузлах. Але калі мы наладзіць гэтыя паказальнікі? Дзе ж нам рабіць, што ў кодзе? Джэф? 

АЎДЫТОРЫЯ: - умовы значэнне? 

Джэйсан Хиршхорн: Якія адзін, у прыватнасці? 

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

Джэйсан Хиршхорн: Дык што, калі наша значэнне больш, чым значэнне гэтага вузла. 

АЎДЫТОРЫЯ: Так, то вы хацелі б ісці далей па лініі, ці не так? 

Джэйсан Хиршхорн: Дакладна. Такім чынам, мы не ўстаўляйце яго тут. Калі значэнне менш гэтага вузла, то мы ідзем да наступнага вузла - ці тады мы ўставіць раней. 

АЎДЫТОРЫЯ: Пачакайце, што гэта вузел і што значэнне? 

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

АЎДЫТОРЫЯ: Калі гэтае значэньне большае чым гэтага вузла. 

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

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

ОК. Пачнем. Асам, як мы ствараем новы вузел? 

АЎДЫТОРЫЯ: Вы структуры *. 

Джэйсан Хиршхорн: Такім чынам, мы ёсць, што тут. Ой, прабачце. Вы казалі структуру *. 

АЎДЫТОРЫЯ: А потым [? выгляд?] вузел або з вузлом. 

Джэйсан Хиршхорн: ОК. Я буду называць яго new_node так што мы можам заставацца паслядоўным. 

АЎДЫТОРЫЯ: І вы хочаце ўсталяваць, што ўзначаліць, першы вузел. 

Джэйсан Хиршхорн: ОК. Так што зараз гэта, які паказвае на - дык гэта ня стварыў новы вузел яшчэ. Гэта проста паказваючы на Першы вузел у спісе. Як стварыць новы вузел? Калі мне трэба прастору, каб стварыць новы вузел. Malloc. І наколькі вялікі? 

АЎДЫТОРЫЯ: Памер структуры. 

Джэйсан Хиршхорн: памер структуры. І што структура называецца? 

АЎДЫТОРЫЯ: Вузел? 

Джэйсан Хиршхорн: Вузел. Так Таноса (SizeOf (вузел)); дае нам прастору. І гэтая лінія - адно няправільнае на гэтай лініі. З'яўляецца new_node паказальнік на структуру? Гэта агульная назва. Што гэта - вузел, дакладна. Гэта вузел *. І што ж нам рабіць адразу пасля мы Malloc нешта, Асан? Што першае, што мы робім? Што рабіць, калі ён не працуе? 

АЎДЫТОРЫЯ: О, праверыць, калі ён паказвае на вузле? 

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

АЎДЫТОРЫЯ: Вы павінны былі б зрабіць вузел *. Вы павінны былі б зрабіць адзін не для new_node але для вузлы ў нас ужо ёсць. 

Джэйсан Хиршхорн: ОК. Такім чынам, бягучы вузел мы на. Я пазваню, што ін. Добра. Мы вырашылі, што мы хочам захаваць два, таму што мы павінны ведаць што перад ім. Што яны ініцыялізуюцца? 

АЎДЫТОРЫЯ: Іх каштоўнасць у нашым спісе. 

Джэйсан Хиршхорн: Так у чым жа Першае, што ў нашым спісе? Ці як мы ведаем, дзе пачатак нашым спісе ёсць? 

АЎДЫТОРЫЯ: Хіба гэта не прайшло у функцыю? 

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

АЎДЫТОРЫЯ: Спіс. 

Джэйсан Хиршхорн: Спіс. Вось менавіта. Зараз ён мае адрас пачатак нашага спісу. А як наконт папярэдні? 

АЎДЫТОРЫЯ: Спіс мінус адна? 

Джэйсан Хиршхорн: Там у нічога перад ім. Так што мы можам зрабіць, каб паказаць, нічога? 

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

Джэйсан Хиршхорн: Так. Гэта гучыць як добрая ідэя. Выдатна. Дзякуй. Прайсціся па спісе. Канстанцін, як доўга мы будзем ісці па спісе? 

АЎДЫТОРЫЯ: пакуль мы не дасягнем нулявы. 

Джэйсан Хиршхорн: ОК. Так што калі, у той час, на працягу цыклу. Што мы робім? 

АЎДЫТОРЫЯ: Можа быць, для цыкла? 

Джэйсан Хиршхорн: Давайце зробім цыкл. ОК. 

АЎДЫТОРЫЯ: І мы гаворым на - да бягучага паказальніка ня роўны NULL. 

Джэйсан Хиршхорн: Дык што, калі мы ведаем, што стан, як мы можам напісаць цыкл заснаваныя ад гэтага ўмовы. Якія цыкле мы павінны выкарыстоўваць? 

АЎДЫТОРЫЯ: У той час як. 

Джэйсан Хиршхорн: Так. Гэта мае больш сэнсу, заснаваную ад таго, што вы сказалі. Калі мы проста хочам, каб увайсці ў мы гэта было б проста ведаю, што рэч, было б сэнс рабіць нейкі час цыклу. У той час як ток не роўны NULL, калі значэнне менш гэтага вузла. Akshar, дай мне гэтую лінію. 

АЎДЫТОРЫЯ: Калі ток-> п н менш кошту. Або зваротная што. Перамыкач што кранштэйн. 

Джэйсан Хиршхорн: Выбачайце. 

АЎДЫТОРЫЯ: Зменіце кранштэйн. 

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

АЎДЫТОРЫЯ: Гэта ўсё яшчэ я? 

Джэйсан Хиршхорн: Так. 

АЎДЫТОРЫЯ: Вы - new_node-> наступная. 

Джэйсан Хиршхорн: Так у чым што збіраецца раўняцца? 

АЎДЫТОРЫЯ: Гэта будзе роўнай току. 

Джэйсан Хиршхорн: Цалкам дакладна. І так з другога - што яшчэ трэба для абнаўлення? 

АЎДЫТОРЫЯ: Пераканайцеся, што міма роўная нуля. 

Джэйсан Хиршхорн: Калі папярэдняя - так што калі перад роўная нуля. 

АЎДЫТОРЫЯ: Гэта азначае, што ён збіраецца стаць кіраўніком. 

Джэйсан Хиршхорн: Гэта азначае гэта стаць кіраўніком. Такім чынам, што ж нам рабіць? 

АЎДЫТОРЫЯ: Мы робім галаву роўна new_node. 

Джэйсан Хиршхорн: Кіраўнік роўная new_node. І чаму ўзначаліць тут, не пералічыць? 

АЎДЫТОРЫЯ: Таму што галава з'яўляецца сусветным зменная, якая з'яўляецца адпраўной кропкай. 

Джэйсан Хиршхорн: Салодкі. ОК. І - 

АЎДЫТОРЫЯ: Тады вы яшчэ перад-> Наступны роўна new_node. А потым вы вернецеся праўда. 

Джэйсан Хиршхорн: Куды мы ўсталёўваем new_node канец? 

Залы: Я - Я усталяваў, што ў пачатку. 

Джэйсан Хиршхорн: Так што лінія? 

АЎДЫТОРЫЯ: Пасля таго, як калі заяву праверкі, калі ён вядомы. 

Джэйсан Хиршхорн: Прама тут? 

АЎДЫТОРЫЯ: я зраблю new_node-> п роўная кошту. 

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

АЎДЫТОРЫЯ: Калі гэтае значэньне большае чым вал-> п - 

Джэйсан Хиршхорн: Як зрабіць мы ідзем да наступнага вузла? 

АЎДЫТОРЫЯ: Кэр-> п роўная new_node. 

Джэйсан Хиршхорн: Так п якая частка структуры? Цэлае. І new_node з'яўляецца паказальнікам на вузел. Так што частка цёк мы павінны абнавіць? Калі не я, то што іншая частка? Най, што іншая частка. 

АЎДЫТОРЫЯ: О, у наступны. 

Джэйсан Хиршхорн: Далей, дакладна. Менавіта так. Наступная з'яўляецца правільным. А што яшчэ трэба абнавіць, Ной? 

АЎДЫТОРЫЯ: Паказальнікі. 

Джэйсан Хиршхорн: Так мы абнавілі ток. 

АЎДЫТОРЫЯ: Папярэдні-> наступная. 

Джэйсан Хиршхорн: Так. Добра, мы паўзу. Хто можа дапамагчы нам тут? Ману, што мы павінны рабіць? 

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

Джэйсан Хиршхорн: ОК. Што-небудзь яшчэ? Akshar. 

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

Джэйсан Хиршхорн: Так шкада, дзе? На якой лініі? Гэтая лінія? 

АЎДЫТОРЫЯ: Так. Зрабіць вал роўная вал-> наступная. 

Джэйсан Хиршхорн: Дык вось правільна паколькі ў цяперашні час з'яўляецца паказальнік да вузла. І мы хочам, каб яна паказвала на наступны вузел, што становіцца ў цяперашні час паказаў на. Сам Кэр мае наступны. Але калі б мы павінны былі абнавіць curr.next, мы будзе абнаўляць фактычныя ведама сама не там, дзе гэта паказальнік паказваў. А як наконт гэтай лініі, хоць. Аві? 

АЎДЫТОРЫЯ: Папярэдні-> наступная роўная ін. 

Джэйсан Хиршхорн: Такім чынам, яшчэ раз, калі перад з'яўляецца паказальнік на вузел, прад-> наступны з'яўляецца Фактычны паказальнік ў вузле. Так што гэта будзе абнаўленне паказальнік ў вузле да Curr. Мы не хочам, каб абнавіць паказальнік на вузел. Мы хочам, каб абнавіць папярэдні. Так як жа нам гэта зрабіць? 

АЎДЫТОРЫЯ: Было б проста быць прад. 

Джэйсан Хиршхорн: Дакладна. Папярэдні з'яўляецца паказальнікам на вузел. Цяпер мы мяняем яго на Новы паказальнік на вузел. ОК Давайце рухацца ўніз. Нарэшце, апошняя ўмова. Джэф, што мы робім тут? 

АЎДЫТОРЫЯ: Калі значэнне роўная вал-> п. 

Джэйсан Хиршхорн: Выбачайце. Аб божа мой. Што? Значэнне == вал-> п. Што нам рабіць? 

АЎДЫТОРЫЯ: Вы б вызваліць нашу new_node, і тады вы б вярнуцца ілжывым. 

Джэйсан Хиршхорн: Гэта тое, што мы напісалі да гэтага часу. Хто-небудзь ёсць нічога дадаць, перш чым зрабіць? ОК. Давайце паспрабуем. Кантроль можа дайсці да канца з не-пустата функцыі. Аві, што адбываецца? 

АЎДЫТОРЫЯ: Вы павінны паставіць вяртанне праўда за межамі час цыкла? 

Джэйсан Хиршхорн: Я не ведаю. Вы хочаце, каб я? 

АЎДЫТОРЫЯ: Не бярыце ў галаву. Няма. 

Джэйсан Хиршхорн: Akshar? 

Залы: Я думаю, што вы прызначаныя для пакласці вяртанне ілжывым у канцы з той час цыклу. 

Джэйсан Хиршхорн: Дык дзе Вы хочаце, каб гэта пайшло? 

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

Джэйсан Хиршхорн: ОК. Дык што ж нам рабіць тут? 

АЎДЫТОРЫЯ: Вы вярнуцца ілжывым там жа. 

Джэйсан Хиршхорн: О, мы зрабіць гэта ў абодвух месцах? 

АЎДЫТОРЫЯ: Так. 

Джэйсан Хиршхорн: ОК. Калі мы ідзем? Аб божа мой. Мне вельмі шкада. Я прашу прабачэння за экрана. Гэта свайго роду бескантрольнага паводзін на нас. Так што выбірайце опцыю. Нуль, у адпаведнасці з кодам, выходзіць з праграмы. Адзін ўстаўляе нешта. Давайце ўставіць тры. Устаўка ня была паспяховай. Я збіраюся раздрукаваць. Я не маю нічога. ОК. Можа быць, гэта была проста выпадковасць. Устаўце адзін. Ня паспяховым. ОК. Давайце разгледзім GDB вельмі хутка каб праверыць, што адбываецца. 

Запомніць GDB. / Імя вашага Праграма атрымлівае нас у GDB. Шмат гэта ці мала, каб справіцца? Міргае? Напэўна. Зачыніце вочы і зрабіце некалькі глыбокіх дыхае, калі вы стамляецеся глядзець на гэта. Я ў GDB. Што першае, што я раблю ў GDB? Мы павінны высветліць, што адбываецца тут. Давайце паглядзім. У нас ёсць шэсць хвілін, каб зразумець , Што адбываецца. Перапынак асноўнай. А потым што мне рабіць? Карлас? Запусціце. ОК. Давайце абярэм опцыю. І што N рабіць? Наступная. Так. 

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

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

АЎДЫТОРЫЯ: О, гэта памёр. 

Джэйсан Хиршхорн: Я проста выцягнуў яго. ОК. 

АЎДЫТОРЫЯ: Можа быць, гэта Іншы канец дроту. 

Джэйсан Хиршхорн: Нічога сабе. Так сутнасць - што ты сказаў? 

Залы: Я сказаў, што іронія тэхнічная Цяжкасці ў гэтым класе. 

Джэйсан Хиршхорн: Я ведаю. Калі б толькі я меў кантроль над гэтай часткай. [Неразборліва] Гэта гучыць выдатна. Чаму б вам не пачаць думаць пра тое, што мы маглі б зрабіць так, і мы вернемся ў 90 секунд. 

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

АЎДЫТОРЫЯ: Што? 

Джэйсан Хиршхорн: Какая команда GDB Я выкарыстоўваю, каб зайсці ўнутр гэтай функцыі? 

АЎДЫТОРЫЯ: Крок? 

Джэйсан Хиршхорн: Крок праз С. Гэта бярэ мяне ўнутры. ОК. New_node mallocing некаторы прастору. Гэта ўсё выглядае як яго збіраюцца. Давайце разгледзім new_node. Ён атрымаў некаторую адрас памяці. Давайце праверым - гэта ўсё правільна. Так што ўсё тут, здаецца, працуе правільна. 

АЎДЫТОРЫЯ: У чым розніца паміж Р і дысплея? 

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

ОК. Такім чынам, мы знаходзімся на лініі 80 нашага кода, ўстаноўка вузла * Curr роўную спісу. Давайце раздрукаваць ін. Яна роўная спіс. Салодкі. Пачакайце. Яна роўная нешта. Гэта не здаецца правільным. Там мы ідзем. Гэта таму, што ў GDB, справа, калі гэта лінія ты на ім яшчэ не выканана. Так што вам трэба на самай справе тып Наступны выканаць лінію перш, чым бачыць яго вынікі. І вось мы. Мы толькі што выканалі гэтую лінію, папярэдняя роўная нуля. Такім чынам, яшчэ раз, калі мы друкуем папярэдняя мы не ўбачым нічога дзіўнага. Але калі мы на самай справе выканаць, што лінія, то мы ўбачым, што гэтая лінія працавала. 

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

АЎДЫТОРЫЯ: Не. 

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

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

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

Джэйсан Хиршхорн: ОК. Ці будзе гэта вырашыць нашу праблему, хоць? 

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

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

АЎДЫТОРЫЯ: Калі ў вас ужо ёсць вузел malloced, вы маглі б проста сказаць, new_node-> наступная роўная нуль, таму што ён павінен быць у канцы. Або new_node-> наступная роўная нуля. 

Джэйсан Хиршхорн: ОК. Выбачайце. New_node-> наступная роўна нуль , Таму што мы знаходзімся ў канцы. Гэта не пакласці яго цалі Як мы пакласці яго ў спісе? Дакладна. Вось толькі паклаўшы яе роўнай. Няма, як жа мы на самай справе пакласці яго ў спісе? Што паказваючы на канец спісу? 

АЎДЫТОРЫЯ: заг. 

Джэйсан Хиршхорн: Выбачайце? 

АЎДЫТОРЫЯ: кіраўнік паказвае ў канцы спісу. 

Джэйсан Хиршхорн: Калі няма нічога ў спіс, галава паказваючы на канец спісу. Так што буду працаваць на Першы ўстаўкі. Што, калі ёсць некалькі рэчы ў спісе? Чым мы не хочам, каб усталяваць ўзначаліць роўна new_node. Што мы хочам, каб там рабіць? Да? Напэўна папярэдні. Ці будзе гэта працаваць? Нагадаем, што папярэдняя проста паказальнік на вузел. І папярэдняя з'яўляецца лакальнай зменнай. Так гэтая лінія будзе ўстаноўлена лакальная зменная, папярэдні, роўнай або паказваючы на ​​гэтым новым вузле. Гэта не будзе на самой справе паклаў яго у нашым спісе, хоць. Як мы пакласці яго ў нашым спісе? Akchar? 

Залы: Я думаю, што вы зрабіць бягучы-> Next. 

Джэйсан Хиршхорн: ОК. вал-> наступная. Такім чынам, яшчэ раз, адзіная прычына, мы ўніз вось, што значыць ток, роўны? 

АЎДЫТОРЫЯ: Роўна нуля. 

Джэйсан Хиршхорн: І так, што адбудзецца, калі мы робім нуль-> далей? Што мы збіраемся атрымаць? Мы атрымаем памылку сегментацыі. 

АЎДЫТОРЫЯ: Do вал роўная нуля. 

Джэйсан Хиршхорн: Гэта тое ж самае, як папярэдняя, ​​хоць, таму што ёсць лакальная пераменная мы ўсталёўваем роўным гэтаму новаму вузла. Давайце вернемся да нашай карціне ўстаўкі нешта. Скажыце, што мы, уключыўшы ў канцы з спісу, так прама тут. У нас ёсць бягучы паказальнік Гэта паказваючы на ​​нуль і папярэдні пункт які, паказваючы на ​​8. Дык што ж нам трэба абнавіць, Аві? 

АЎДЫТОРЫЯ: Папярэдні-> далей? 

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

АЎДЫТОРЫЯ: Гэта збіраецца вярнуцца хлусня ў гэтым выпадку? 

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

АЎДЫТОРЫЯ: Ці ёсць папярэдняя ранейшаму роўная нуль у верхняй частцы спісу? 

Джэйсан Хиршхорн: Так папярэдняя яшчэ роўная нуль ў самым пачатку. Так як мы можам пераадолець гэта? Да? 

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

Джэйсан Хиршхорн: ОК. Так што давайце ісці сюды. У чэк. Калі - 

АЎДЫТОРЫЯ: Дык што, калі кіраўнік роўная роўная нуля. 

Джэйсан Хиршхорн: Калі галава роўная роўная нуль - што нам скажа, калі гэта пусты спіс. 

АЎДЫТОРЫЯ: І тады вы зрабіць кіраўнік роўна новая. 

Джэйсан Хиршхорн: Кіраўнік роўная new_node? А што яшчэ трэба зрабіць? 

АЎДЫТОРЫЯ: А потым вы вернецеся праўда. 

Джэйсан Хиршхорн: Не зусім. Мы не хапае на адзін крок. 

АЎДЫТОРЫЯ: new_node побач павінен паказваць на нуль. 

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

АЎДЫТОРЫЯ: Так. 

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

АЎДЫТОРЫЯ: Не. 

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

ОК. Давайце запусціць гэтую праграму яшчэ раз. Ня паспяховым. 

АЎДЫТОРЫЯ: Вы не зрабілі гэта. 

Джэйсан Хиршхорн: О, Я не рабіў гэта. Добры пытанне, Майкл. Давайце дадамо марку звязаныя паміж сабой. Лінія 87 ёсць памылка. Лінія 87. Олдэн, гэта была лінія вы мне далі. Што не так? 

АЎДЫТОРЫЯ: Яна павінна быць на нуль. 

Джэйсан Хиршхорн: Выдатна. Цалкам дакладна. Ён павінен быць нулявым. Давайце зробім зноў. Кампіляцыя. ОК. Давайце ўставіць тры. Устаўка была паспяховай. Давайце раздрукаваць яго. О, калі б мы маглі праверыць. Але мы яшчэ не зрабілі раздрукаваць функцыю яшчэ. Давайце ўвядзем нешта яшчэ. Што мы павінны ўвесці? 

АЎДЫТОРЫЯ: Сем. 

Джэйсан Хиршхорн: Сем? 

АЎДЫТОРЫЯ: Так. 

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

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

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

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

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

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

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

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

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

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

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

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

АЎДЫТОРЫЯ: Ён можа знайсці індэкс за пастаянны час? 

Джэйсан Хиршхорн: Гэта не тое, што гэта значыць. Але гэта добрае здагадку. Хто-небудзь яшчэ ёсць здагадка да таго, што гэта азначае? Гэта добрая хэш-функцыя дэтэрмінавана? Эні? 

АЎДЫТОРЫЯ: Гэта ключавы можна супаставіць толькі у адным месцы ў хэш-табліцы. 

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

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

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

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

АЎДЫТОРЫЯ: Нуль. 

Джэйсан Хиршхорн: Чаму нуля? 

АЎДЫТОРЫЯ: Таму што тры модулю тры роўная нулю? 

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

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

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

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

Так што я паклаў у гарбуз. Гэта вяртае нуль. І я паклаў гарбуз тут. Тады я паклаў у - што яшчэ адзін Дзень усіх Святых-тэматычны рэч? 

АЎДЫТОРЫЯ: Цукеркі. 

Джэйсан Хиршхорн: Цукеркі! Гэта выдатнае. Я паклаў у цукеркі, і цукеркі таксама дае мне нуля. Што мне рабіць? Ёсць ідэі? Таму што ўсё, што вы, здаецца, ведаю што асобныя ланцужкі з'яўляецца. Так любыя ідэі, што рабіць? Так. 

АЎДЫТОРЫЯ: Увод радок на самай справе ў хэш-табліцы. 

Джэйсан Хиршхорн: Такім чынам, мы збіраемся прыцягнуць добрую ідэю тут. ОК. 

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

Джэйсан Хиршхорн: ОК. Маркус, які быў выдатным. Я збіраюся разбурыць гэта. Маркус кажу, не перазапісаць гарбуз. Гэта было б дрэнна. Не стаўце цукеркі дзесьці ў іншым месцы. Мы збіраемся паставіць іх абодвух на нулі. Але мы збіраемся мець справу з пакласці іх у нулі стварэнне спісу на нулі. І мы збіраемся стварыць спіс усё, што адлюстроўваецца на нуль. І лепшы спосаб мы навучыліся ствараць спіс, які можа павялічвацца і памяншацца дынамічна не знаходзіцца ў межах іншы масіў. Так не мнагамерны масіў. Але проста стварыць звязаны спіс. 

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

АЎДЫТОРЫЯ: Паказальнікі на - 

Джэйсан Хиршхорн: Таму што вам сказаў звязаны спіс, а значыць - 

АЎДЫТОРЫЯ: Node паказальнікі? 

Джэйсан Хиршхорн: Node паказальнікі. Калі рэчы ў наш звязаны Спіс вузлы, то яны павінны быць паказальнікі вузлоў. І што ж яны роўныя першапачаткова? 

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

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

АЎДЫТОРЫЯ: Я збіраюся зрабіць здагадку. Таму, калі вы атрымліваеце цукеркі. 

Джэйсан Хиршхорн: Так. Ну, мы атрымалі гарбуз. Давайце наш першы. Мы атрымалі гарбуз. 

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

Джэйсан Хиршхорн: Як мы пакласці яго ў звязаным спісе? 

АЎДЫТОРЫЯ: О, фактычны сінтаксіс? 

Джэйсан Хиршхорн: Проста хадзіць - сказаць больш. Што нам рабіць? 

АЎДЫТОРЫЯ: Вы проста ўставіць гэта як першы вузел. 

Джэйсан Хиршхорн: ОК. Такім чынам, мы маем нашу вузла, гарбуз. А цяпер, як я ўводжу яго? 

АЎДЫТОРЫЯ: Вы прызначаеце гэта да паказальніка. 

Джэйсан Хиршхорн: Якія паказальнік? 

АЎДЫТОРЫЯ: Паказальнік на нулі. 

Джэйсан Хиршхорн: Дык дзе робіць гэта сэнс? 

АЎДЫТОРЫЯ: Каб абнуліць прама цяпер. 

Джэйсан Хиршхорн: Ну, гэта паказвае на нуль. Але я стаўлю ў гарбуз. Дык дзе ён павінен паказваць? 

АЎДЫТОРЫЯ: Каб гарбуз. 

Джэйсан Хиршхорн: Для гарбузы. Менавіта так. Так што гэта паказвае на гарбуз. А прычым тут гэты паказальнік ў гарбузы кропкі? Да 

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

Джэйсан Хиршхорн: Каб абнуліць. Менавіта так. Так што мы проста ўстаўляецца нешта ў звязаным спісе. Мы толькі што напісаў гэты код, каб зрабіць гэта. Амаль мы амаль атрымалася цалкам расколіны. Цяпер мы ўстаўляем цукеркі. Наша цукеркі таксама імкнецца да нуля. Дык што ж нам рабіць з цукеркамі? 

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

Джэйсан Хиршхорн: Гэта Цалкам дакладна. Гэта залежыць ад наяўнасці або адсутнасці мы спрабуем ўладзіць яго. Давайце выкажам здагадку, што мы не збіраецца ўладзіць яго. 

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

Джэйсан Хиршхорн: ОК. Трымайся. Дазвольце мне стварыць цукеркі прама тут. Так гэты паказальнік - 

АЎДЫТОРЫЯ: Так, трэба зараз быць паказваючы на ​​цукеркі. Тады ёсць паказальнік ад цукеркі паказваюць на гарбуз. 

Джэйсан Хиршхорн: Як што? І сказаць, што мы атрымалі яшчэ адзін што трэба супаставіць з нуля? 

АЎДЫТОРЫЯ: Ну, вы проста зрабіць тое ж самае? 

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

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

Зала: А чаму вы паставіць гарбуз і цукеркі ў тое ж самае частка хэш-табліцы? 

Джэйсан Хиршхорн: Добры пытанне. Чаму мы ставім іх у тое ж самае частка хэш-табліцы? Ну, у гэтым выпадку наша хэш-функцыя вяртае нуль для іх абодвух. Такім чынам, яны павінны пайсці на нулі Indice таму што там мы збіраемся глядзець на іх, калі мы калі-небудзь хачу паглядзець іх. Зноў жа, з лінейнай зандзіравання падыход мы б не пакласці іх абодвух у нулі. Але ў асобным падыходзе ланцуга, мы збіраемся паставіць іх абодвух у нулі а затым стварыць спіс з нуля. 

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

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

АЎДЫТОРЫЯ: У працяг да гэтага, што вы маеце на ўвазе наступнае месца? У хэш-табліцы або ў звязаным спісе. 

Джэйсан Хиршхорн: Для лінейных праграмаванне, не звязаныя спісы. На наступны пляма на хэш-табліцы. 

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

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

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

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

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

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

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