ЈАСОН Hirschhorn: Добредојдовте сите на Дел Седум. Ние сме во недела седум на курсот. И оваа претстојните четврток е Ноќта на вештерките, па јас сум облечени како тиква. Не можев да се превиткуваат и го стави на моите чевли, па тоа е причината зошто јас сум само носи чорапи. Јас сум исто така не носат ништо под ова, па не можам да го симнат ако тоа е оттргнува вас. Јас се извинувам однапред за тоа. Вие не треба да се замисли што се случува. Јас сум облечен боксери. Па тоа е добро. 

Имам подолга сторија за тоа зошто јас сум облечен како тиква, но јас ќе одам да се спаси за подоцна во ова поглавје затоа што сакаат да започнете. Имаме многу возбудливи нешта да се оди во текот на оваа недела. Повеќето од нив се однесуваат директно на овој Проблемот сет недела, грешките во правописот. Ние ќе се случува во текот поврзани листи и хаш маси за целиот дел. Ја ставив оваа листа секоја недела, листа на ресурси за да ви помогнат со материјал на овој курс. Ако во загуба, или ако во потрага за некои повеќе информации, проверете еден од овие ресурси. 

Повторно, pset6 е спелувањето грешки, pset оваа недела. И тоа, исто така, ги охрабрува и јас ве охрабруваме да, да користите некои други ресурси специјално за овој pset. Особено, три сум наведени на екранот - gdb, кои ние сме биле запознаени со и се користат за некое време сега, е ќе биде многу корисна оваа недела. Па јас се стави дека тука горе. Но, кога си работат со C, секогаш треба да биде со користење gdb да debug вашите програми. Оваа недела, исто така, valgrind. Дали некој знае што valgrind прави тоа? 

Публика: Тоа проверки за меморија протекување? 

ЈАСОН Hirschhorn: Valgrind проверки за меморија протекување. Па ако Примерок нешто во вашата програма, ти си прашува за меморија. На крајот на вашата програма, ќе имаат да се напише бесплатно на сè што сте malloced да се даде на меморија назад. Ако не напише бесплатно на крајот и вашата програма доаѓа до заклучок, сè што автоматски ќе да бидат ослободени. И за мали програми, тоа е не толку голема зделка. Но, ако сте пишување прекинати програма со која не се откажува, мора, во неколку минути или неколку секунди, а потоа меморија протекување може да стане голем договор. 

Значи за pset6, за очекување е дека ќе имаат нула меморија протекување со вашата програма. Да се ​​провери за меморија протекување, работи valgrind и тоа ќе ви даде некои убави излез допуштајќи знаете дали или не се беше бесплатно. Ние ќе вежбате со него подоцна денес, се надевам. 

Конечно, разл команда. Сте користеле нешто слично на тоа во pset5 со ѕиркаат алатка. Дозволено да се погледне внатре. Можете исто така се користи разл, исто така, по проблемот постави спецификации. Но, во што е дозволено да се споредба на две датотеки. Вие би можеле да се споредат bitmap датотека и инфо заглавија на персоналот решение и вашето решение во pset5 ако сте одбрале да го користите. Разл ќе ви овозможи да направат тоа, како и. Можете да ги споредувате точен одговор на проблем оваа недела во собата да се вашиот одговор и види дали линии или види каде грешките се. 

Значи тоа се три добри алатки кои треба да го користите за оваа недела, и дефинитивно проверете ја вашата програма со овие три алатки пред да наполнат внатре Повторно, како што спомнавме секоја недела, ако имате било какви повратни информации за мене - и позитивна и конструктивна - се чувствуваат слободни да се упатат кон веб-страница на дното на овој слајд и влез таму. Јас навистина го цениме било и сите повратни информации. И ако ми даде конкретни работи кои Можам да направам за да се подобри или дека јас сум прави добро што би ме сакал да продолжи, јас се земе дека на срцето и навистина се обиде тешко да се слуша да вашето мислење. Не можам да ветам дека ќе одам да направите сè, иако, како што носи тиква костим секоја недела. 

Па ние се случува да поминат најголемиот дел од дел, како што веќе напоменав, зборувајќи за поврзани листи и хаш маси, кои ќе биде директно применлива до проблем во собата оваа недела. Поврзани листи ќе одиме над релативно брзо, бидејќи ние си трошат фер малку на време да оди над тоа во делот. И така што ќе добиете директно во кодирање проблеми за поврзани листи. А потоа на крајот ние ќе зборуваме за хеш табели и како тие се однесуваат на овој Проблемот недела во собата. 

Сте виделе овој код пред. Ова е struct, а тоа е дефинирањето нешто ново нарекува јазол. И во внатрешноста на јазол постои број токму тука и таму е покажувач кон друг јазол. Видовме тоа порано. Ова е доаѓаат за неколку недели. Тоа е комбинација на покажувачи, кој го работат со, а structs, кои им овозможуваат ни да се комбинираат две различни работи во една тип на податок. 

Има многу случува на екранот. Но сето тоа треба да биде релативно запознаени со вас. На првата линија, ние прогласи нов јазол. А потоа внатре дека новиот јазол, јас во собата цел број со тоа, што јазол еден. Ние гледаме на следната линија правам со printf команда, но јас сум неактивни на printf команда, бидејќи навистина важен дел е оваа линија тука - new_node.n. Што значи точка значи? 

ПУБЛИКАТА: Одете до јазол и процени n вредност за тоа. 

ЈАСОН Hirschhorn: Тоа е точно во право. Точка значи пристап до n дел на овој нов јазол. Овој следната линија што прави? Мајкл. 

Публика: Тоа создава друг јазол кои ќе укажуваат на нов јазол. 

ЈАСОН Hirschhorn: Значи тоа не го прави се создаде нов јазол. Тоа создава она? 

ПУБЛИКАТА: покажувач. 

ЈАСОН Hirschhorn: покажувач на еден јазол, како што е наведено од страна на овој јазол * тука. Па тоа создава покажувач на еден јазол. И кој јазол е тоа што покажуваат да, Мајкл? 

Публика: Нов јазол? 

ЈАСОН Hirschhorn: Нови јазол. И тоа е покажувајќи таму, бидејќи ние сме со оглед на тоа на адреса на новиот јазол. И сега во оваа линија гледаме два различни начини на изразување на истото. И јас сакав да се истакне како овие две работи се исти. Во првата линија, ние dereference на покажувачот. Па ние одиме на јазол. Тоа е она што оваа ѕвезда значи. Видовме дека пред со покажувачи. Оди до тој јазол. Тоа е во голема заграда. А потоа пристап преку операторот точка на n елемент на тој јазол. 

Значи тоа е преземање на синтаксата видовме токму тука и сега го користите со покажувач. Се разбира, таа добива вид на зафатен, ако сте пишување оние загради - таа ѕвезда и дека точка. Тоа добива малку зафатен. Па ние имаме некои синтаксички шеќер. И оваа линија, токму тука - ptr_node-> n. Дека го прави истото точната нешто. Значи овие две линии на код се еквивалент и ќе направи иста работа. 

Но јас сакав да истакнам оние пред да одиме понатаму па да се разбере дека навистина тоа нешто, токму тука е само синтаксички шеќер за dereferencing покажувачот, а потоа ќе на n дел од тоа struct. Било какви прашања во врска со овој слајд? OK. 

Па ние ќе да поминат низ неколку на операции што можете да направите за поврзани листи. А поврзана листа, да се потсетиме, е серија на јазли кои упатуваат на една со друга. И ние обично почнуваат со покажувач наречен главата, генерално, што укажува на првото нешто во листата. Па на првата линија тука, ние имаме оригинални L прв план. Така што нешто што може да мисли на - оваа текст, токму тука можете да мислам на како само на покажувачот ние сме се чуваат некаде дека поени на првиот елемент. И во овој поврзана листа имаме четири јазли. Секој јазол е голема кутија. Поголемите кутија во внатрешноста на големите кутија е цел дел. И тогаш имаме покажувач дел. 

Овие кутии не се подготвени да скала, бидејќи колку е голема е цел број во бајти? Колку е голема сега? Четири. И колку е голема е покажувачот? Четири. Значи, навистина, ако ние требаше да се подготви ова за да ја двете кутии ќе биде иста големина. Во овој случај, ние сакаме да го вметнете нешто во поврзана листа. Така можете да видите овде долу ние сме вметнување пет Ние напречни преку поврзана листа, најдете, каде пет оди, а потоа да го внесете. 

Ајде да се скрши дека долу и да си одат малку побавно. Одам да се укаже на одборот. Па ние имаме јазол пет кои ние сме создадени во mallocs. Зошто е сите се смеат? Само се шегувам. OK. Па ние сме malloced пет. Ние направивме овој јазол некаде на друго место. Ние го имаме подготвени да одите. Започнуваме во предниот дел нашата листа со две. И ние сакаме да се вметне во сортирани начин. 

Па ако гледаме две и ние сакаме да се стави во пет, што ќе правиме кога ќе го видиме нешто помалку од нас? Што? Ние сакаме да го внесете пет во оваа поврзана листа, одржувањето подредени. Гледаме број два. Па што ќе правиме? Маркус? 

ПУБЛИКАТА: Јавете се на покажувачот кон следниот јазол. 

ЈАСОН Hirschhorn: И зошто ние одиме на следниот? 

Публика: Затоа што тоа е следниот јазол во листата. И ние знаеме само дека друга локација. 

ЈАСОН Hirschhorn: И пет е поголема од две, особено. Бидејќи ние сакаме тоа да го чува подредени. Така пет е поголема од две години. Па ние се движи кон следниот. А сега доаѓаме до четири. И она што се случува кога ќе стигнат до четири? 

Пет е поголема од четири. Па ние продолжувам да одам. А сега ние сме во шест. И она што го гледаме во шест? Да, Карлос? 

ПУБЛИКАТА: Шест е поголем од пет. 

ЈАСОН Hirschhorn: Шест е поголема од пет. Па тоа е каде што сакате за да вметнете пет. Сепак, имајте на ум дека ако ние имаат само еден покажувач тука - ова е нашиот дополнителни покажувачот тоа е traversing преку листата. И ние сме посочувајќи шест. Изгубивме пратите на она што доаѓа пред шест. Значи, ако сакаме да го внесете нешто во оваа листа одржувањето подредени, ние најверојатно треба колку совети? 

ПУБЛИКАТА: Два. 

ЈАСОН HIRSCHORN: Два. Еден да ги пратите на тековната еден и еден да ги пратите на претходниот. Ова е само поединечно поврзана листа. Тоа само оди во една насока. Ако имавме двојно поврзана листа, каде што сè беше да се покажува кон нешто после тоа и нешто пред тоа, тогаш ние не би требало да го направите тоа. Но во овој случај ние не сакаме да се изгуби ги пратите на она што се случило пред нас во случај ние треба да го вметнете пет некаде во средината. Велат бевме вметнување девет. Што ќе се случи кога стигнавме до осум? 

Публика: Ќе треба да се добие дека нула точка. Наместо нула точка ќе треба за да додадете елемент и потоа имаат тоа се укаже на девет. 

ЈАСОН HIRSCHORN: Токму така. Па да добиеме осум. Ние до крајот на листата, бидејќи ова е да се покажува кон нула. И сега, наместо тоа упатуваат на нула имаме таа точка на нашиот нов јазол. И ние го поставите покажувачот во нашиот нов јазол на нула. Дали некој има било какви прашања за вметнување? Што ако јас не се грижат за водење на листа подредена? 

Публика: Стап тоа во почетокот или на крајот. 

ЈАСОН HIRSCHORN: Стап тоа во на почетокот или на крајот. Кој треба да правиме? Боби? Зошто на крајот? 

ПУБЛИКАТА: Бидејќи на почетокот е веќе исполнет. 

ЈАСОН HIRSCHORN: OK. Почетокот е веќе исполнет. Кој сака да се аргументира против Боби. Маркус. 

ПУБЛИКАТА: Па веројатно сакате да ја држи тоа во почетокот, бидејќи инаку, ако го стави на На крајот ќе треба да напречни целата листа. 

ЈАСОН HIRSCHORN: Токму така. Значи, ако ние сме размислување за траење, на траење на вметнување на крајот ќе биде n, на големина. Што е голема О траење на вметнување на почетокот? Постојана време. Па ако не се грижат за одржување нешто подредени, многу подобро да се само вметнете во почетокот на оваа листа. И дека може да се направи во постојан време. 

OK. Следната операција е да најдете, кои други - ние сме изразена ова како за пребарување. Но ние ќе да се погледне преку поврзана листа за некој предмет. Вие момци го виделе код за бара пред во предавање. Но, ние вид на само тоа го направи со внесување, или барем вметнување нешто подредени. Ќе се погледне преку, ќе јазол од јазол, додека не се најде бројот што сте барате. Што се случува ако го достигнете на крајот на листата? Кажам јас сум во потрага по девет и јас до крајот на листата. Што ќе правиме? 

ПУБЛИКАТА: Враќање лажни? 

ЈАСОН HIRSCHORN: Враќање лажни. Ние не го најдете. Ако стигнат до крајот на листата и не си го најде бројот што сте во потрага по, тоа не е таму. Какви прашања во врска најдете? Ако ова беше Подредена листа, што би да бидат различни за нашите пребарување? Да. 

ПУБЛИКАТА: Тоа ќе го најде на првата вредност дека е поголема од онаа сте во потрага за и потоа се врати лажни. 

ЈАСОН HIRSCHORN: Токму така. Значи, ако тоа е Подредена листа, ако ние се да нешто што е поголема од она што ние сме во потрага по, ние не треба да се се насочи на крајот на листата. Ние во тој момент може да се врати лажни бидејќи ние нема да го најдете. Прашањето е сега, ние разговаравме за водење на поврзани листи подредени, држејќи ги несортиран. Тоа ќе биде нешто што сте веројатно ќе треба да се размислува за кога кодирање проблем постави пет ако изберете хеш табелата со посебни врзувањето на пристап, кој ние ќе разговараме за подоцна. 

Но тоа е достоен за тоа да се задржи на списокот сортирани и потоа да биде во можност да можеби имаат побрзо пребарувања? Или е подобро за побрзо вметнување нешто во постојан траење но потоа имаат подолг пребарување? Тоа е Губитокот право таму дека добие да се одлучи што е посоодветна за вашиот специфичен проблем. И таму не е нужно апсолутно точен одговор. Но тоа е секако одлука ќе добиете да се направи, и веројатно добро да се брани дека во, да речеме, коментар или две зошто сте одбрале еден над друг. 

Конечно, бришење. Видовме бришење. Тоа е слично на пребарувањето. Ние со нетрпение за елементот. Велат дека ние се обидуваме да го избришете шест. Па ние се најде шест овде. Она што ние треба да бидете сигурни дека ние не е дека она што е да се покажува кон шест - како што гледаме во чекор две надолу тука - Што и покажувајќи на шест потреби да прескокнете шест сега и да се промени во што шест е да се покажува. Ние не сакаме да некогаш сирак остатокот од нашата листа од заборавање да ја постави таа претходната покажувач. А потоа, понекогаш, во зависност на програмата, тие само ќе ја избришете оваа јазол во целост. Понекогаш ќе сакаат да се вратат вредноста што е во овој јазол. Па тоа е како бришење дела. Било какви прашања за бришење? 

Публика: Значи, ако си оди за да го избришете тоа, ќе ти само ги користат бесплатно, бидејќи се претпоставува дека тоа беше malloced? 

ЈАСОН HIRSCHORN: Ако сакате да се ослободи нешто што е точно во право и ти malloced тоа. Велат дека ние сакаше да се врати оваа вредност. Ние би можеле да се вратат шест, а потоа бесплатно овој јазол и повик бесплатно на неа. Или ние веројатно би ја нарекол бесплатно првата а потоа се врати шест. 

OK. Па ајде да се движат за да се практикуваат кодирање. Ние ќе се шифрираат три функции. Првиот се нарекува insert_node. Па имате кодот кој ви преку е-маил, и ако гледате оваа подоцна можете да пристапите на кодот во linked.c на веб-сајтот CS50. Но, во linked.c, има некои скелет код кој е веќе е напишано за вас. А потоа, тука е неколку функции што треба да се напише. 

Прво ние ќе се пишува insert_node. И она што го прави insert_node IS внесува цел број. И си даваат на број во поврзана листа. А особено, треба да се задржи листа подредена од најмалите до најголемите. Исто така, вие не сакате да го внесете кој било дупликати. Конечно, како што можете да видите insert_node враќа bool. Па си требал да ги споделите на корисникот знаат дали или не вметнете беше успешна со враќање точно или неточно. На крајот на оваа програма - и за оваа фаза не треба да се грижите за ослободување ништо. Така што сите што го правиш е преземање на цел број и вметнување во листата. 

Тоа е она што јас сум те прашам да се направи сега. Повторно, во linked.c, кои можете сите имаат, е скелетот код. И треба да го видите на дното примерокот функција декларација. Сепак, пред да замине во кодирање тоа во C, Силно ве охрабруваме да се оди низ чекорите ние сме биле практикување секоја недела. Ние веќе поминале низ слика од ова. Така ќе треба да имаат некои разбирање за тоа како тоа функционира. Но, јас би ве охрабруваме да се напише некои pseudocode пред нуркање внатре И ние ќе одам во текот pseudocode како група. А потоа, откако ќе ги напишав вашата pseudocode, и кога ќе сум напишал нашата pseudocode како група, можете да одат во кодирање тоа во C. 

Како на главите нагоре, на insert_node функција е веројатно најтешко од трите ние ќе се напише, бидејќи јас додадени некои дополнителни ограничувања за Вашиот програмирање, особено што вие нема да го вметнете било дупликати и дека листата треба да остане подредени. Па ова е не-тривијални програма дека треба да се код. И зошто не ги 06:55 минути само за да се работи на pseudocode и кодот. И тогаш ќе почнеме ќе како група. Повторно, ако имате било какви прашања само подигне својата рака и јас ќе дојдат околу. . 

Ние, исто така, обично се овие - или јас не се експлицитно велиш можат да работат со луѓе. Но, очигледно, Силно ве охрабруваме, ако имате прашања, да побара од сосед седи до тебе или дури и да работат со некој друго, ако сакате да. Ова не мора да се биде индивидуален молчи активност. 

Да почнеме со пишување на некои pseudocode на табла. Кој може да ми даде на првата линија на pseudocode за оваа програма? За оваа функција, наместо - insert_node. Alden? 

Публика: Така првото нешто што го направив беше се создаде нов покажувач на јазол и јас иницијализира тоа укажувајќи на истиот нешто што листа е да се покажува. 

ЈАСОН HIRSCHORN: OK. Па ти си создавање на нов покажувач на листата, да не јазол. 

ПУБЛИКАТА: Право. Да. 

ЈАСОН HIRSCHORN: OK. И тогаш што сакаме да направам? Што е после тоа? Што е со јазол? Ние немаме еден јазол. Ние само имаат вредност. Ако сакаме да вметнете јазол, она што ние треба да се направи пред да можеме дури и се размислува за вметнување тоа? 

Публика: Ох, извинете. ние треба да Примерок простор за јазол. 

ЈАСОН HIRSCHORN: Одлично. Ајде да се направи - OK. Не можат да постигнат толку високо. OK. Ние ќе одат надолу, а потоа ние сме со користење две колони. Не можам да одам дека - OK. Се создаде нов јазол. Можете да креирате друг покажувачот на листата или едноставно можете да го користите листа како што постои. Вие навистина не треба да го направите тоа. 

Па ние се создаде нов јазол. Одлично. Тоа е она што го правиме во прв план. Што е следно? 

ПУБЛИКАТА: Чекај. Ние треба да се создаде нов јазол сега или треба да чекаме да бидете сигурни дека нема дупликати на јазол на листата, пред да го создаде? 

ЈАСОН HIRSCHORN: Добро прашање. Ајде да се одржи за подоцна, бидејќи Поголемиот дел од времето ние ќе биде создавање на нов јазол. Па ние ќе продолжиме тоа овде. Но, тоа е добро прашање. Ако ние го создаде и ги наоѓаме дупликат, она што треба правиме пред да се врати? 

ПУБЛИКАТА: Слободен неа. 

ЈАСОН HIRSCHORN: Да. Веројатно тоа бесплатно. OK. Што ќе правиме откако ќе се создаде нов јазол? Annie? 

ПУБЛИКАТА: Ние се стави на број во јазол? 

ЈАСОН HIRSCHORN: Токму така. Ние се стави број - ние Примерок простор. Одам да го оставиме тоа сите што една линија. Но ти си во право. Ние Примерок простор, а потоа ќе стави број внатре Ние дури и може да го поставите покажувачот дел од неа на нула. Тоа е точно. А потоа, она што за после тоа? Ние привлече оваа слика на табла. Па што ќе правиме? 

Публика: Ние одиме преку листата. 

ЈАСОН HIRSCHORN: Оди преку листа. OK. И што правиме ние се провери за на секој јазол. Курт, што ги проверуваме за на секој јазол? 

Публика: Види дали n вредноста на тој јазол е поголема од n вредност на нашите јазол. 

ЈАСОН HIRSCHORN: OK. Одам да се направи - Да, во ред. Па тоа е n - Одам да се каже ако вредноста е поголема од овој јазол, тогаш што правиме? 

ПУБЛИКАТА: Па, тогаш ние вметнете нешто право пред тоа. 

ЈАСОН HIRSCHORN: OK. Па ако е поголема од ова, тогаш ние сакаме да го внесете. Но, ние сакаме да го вметнете право пред затоа што ние, исто така, ќе треба да биде следење, тогаш, на она што беше порано. Па вметнете порано. Па веројатно пропуштил нешто порано на. Ние најверојатно треба да биде зачувана ги пратите на она што се случува. Но ние ќе се вратам таму. Па што вредност е помала од? Курт, што ќе правиме ако вредност е помала од? 

ПУБЛИКАТА: Тогаш сте само продолжувам да одам освен ако тоа е последен. 

ЈАСОН HIRSCHORN: Ми се допаѓа тоа. Така одат кон следниот јазол. Освен ако тоа е последната - ние сме веројатно проверка за кои во однос на состојбата. Но, да, следниот јазол. И тоа е добивање премногу ниска, па ние ќе се пресели овде. Но ако - може сите да се види ова? Ако ние сме еднакви, што ќе правиме? Ако вредноста ние се обидуваме да го вметнете е еднаква на вредноста на овој јазол? Да? 

ПУБЛИКАТА: [нечујни]. 

ЈАСОН HIRSCHORN: Да. Имајќи го предвид ова - Маркус е во право. Ние би можеле да имаат можеби направено нешто различно. Но со оглед дека ние сме го создале, тука ние треба да се ослободи и потоа да се вратат. О момче. Е дека подобро? Како е тоа? OK. Слободни и тогаш што правиме ние врати, [нечујни]? OK. Дали сме недостасува нешто? Па каде сме следење од пред јазол? 

Публика: Јас мислам дека ќе одам по се создаде нов јазол. 

ЈАСОН HIRSCHORN: OK. Значи на почетокот ние ќе веројатно - Да, ние може да се создаде покажувач кон нови јазол, како претходната јазол покажувач и тековната јазол покажувач. Па ајде вметнете тоа овде. Креирај сегашните и претходните покажувачи на јазли. Но, кога ние прилагоди оние совети? Каде го правиме тоа во кодот? Џеф? 

ПУБЛИКАТА: - вредност услови? 

ЈАСОН HIRSCHORN: Кои еден особено? 

Публика: Јас сум само збунет. Ако вредноста е поголема од овој јазол, не тоа значи дека сакате да одите на следниот јазол? 

ЈАСОН Hirschhorn: Значи, ако нашата вредност е поголема од вредноста на овој јазол. 

Публика: Да, тогаш ќе сакате да го одат понатаму одредување на линија, нели? 

ЈАСОН Hirschhorn: Право. Па ние не се вметне тука. Ако вредноста е помала од овој јазол, а потоа ние одиме на следниот јазол - или тогаш ние вметнете порано. 

ПУБЛИКАТА: Чекај, што е ова јазол и кое е вредност? 

ЈАСОН Hirschhorn: Добро прашање. Вредност по оваа функција дефиниција е она што ние го даде. Значи вредност е бројот што се дадени. Значи, ако вредноста е помала од оваа јазол, ни треба време да го внесете. Ако вредноста е поголема од овој јазол, ние одиме на следниот јазол. И назад на оригиналниот прашање, сепак, каде што - 

Публика: Ако вредноста е поголема од овој јазол. 

ЈАСОН Hirschhorn: И така што правиме тука? Слатка. Тоа е точно. Јас сум само ќе напише ажурирање совети. Но да, со сегашната ќе го ажурирате да укажуваат на следниот. Нешто друго ние сме недостасува? Па ќе одам да напишеш овој кодот во gedit. И додека јас го направите ова, ќе може да има уште неколку минути за да работат на кодирање ова во C. 

Па морам внесување на pseudocode. А брз забелешка пред да можеме да започнете. Ние не може да биде во можност целосно да заврши оваа во сите три од овие функции. Таму е точно решенија за нив дека јас ќе мејл до вас момци по дел, и тоа ќе бидат испратени на CS50.net. Па јас не ве охрабруваме да ги се погледнеш во делови. Јас ве охрабруваме да се обидат овие на вашиот поседувате, а потоа го користите практиката проблеми да ги проверите вашите одговори. Овие сите се дизајнирани да се тесно се однесуваат и се придржуваат до она што што треба да направите за проблемот во собата. Па јас ве охрабруваме да ја применува оваа пракса на свој, а потоа користете го кодот за ги проверите вашите одговори. Затоа што сакаш да се движи кон постигнување маси во одреден момент во секција. Па ние не може да се добие преку сето тоа. Но, ние ќе го направиме колку што можеме сега. 

OK. Нека почне. Asam, како ние да се создаде нов јазол? 

Публика: Вие не struct *. 

ЈАСОН Hirschhorn: Значи ние имаат тоа тука. Ох, извинете. Сте биле велејќи дека struct *. 

Публика: И тогаш [? вид?] јазол или c јазол. 

ЈАСОН Hirschhorn: OK. Одам да го наречеме new_node па ние може да остане доследен. 

Публика: А ти сакаш да ја постави таа да се упатат, првиот јазол. 

ЈАСОН Hirschhorn: OK. Па сега ова укажува на - па ова нема креирано нов јазол уште. Ова е само укажува на прв јазол во листата. Како да креирам нов јазол? Ако ми треба простор за да се создаде нов јазол. Примерок. И колку е голема? 

Публика: Големината на struct. 

ЈАСОН Hirschhorn: На големината на struct. И она што е на struct наречен? 

Публика: Јазол? 

ЈАСОН Hirschhorn: Јазол. Па Примерок (sizeof (јазол)); ни дава простор. И е на оваа линија - едно е неправилна на оваа линија. Е new_node покажувач кон struct? Тоа е генеричко име. Што е тоа - јазол, точно. Тоа е еден јазол *. И што ќе правиме веднаш по ние Примерок нешто, Асан? Што е првото нешто што го правиме? Што ако тоа не функционира? 

ПУБЛИКАТА: О, проверете дали тоа укажува на јазол? 

ЈАСОН Hirschhorn: Токму така. Па ако new_node еднаква на еднаквите нула, што ќе правиме? Ова се враќа bool, оваа функција. Токму така. Изгледа добро. Ништо за да додадете таму? Ние ќе додадете работи на крајот. Но дека досега изгледа добро. Креирај сегашните и претходните совети. Мајкл, како можам да го направите ова? 

Публика: Вие ќе треба да се направи јазол *. Ќе треба да се направи не една за new_node но за јазли веќе го имаме. 

ЈАСОН Hirschhorn: OK. Значи тековната јазол ние сме на. Ќе му се јавам дека ВАЛ. Во ред е. Ние одлучивме сакаме да го задржиме две, бидејќи треба да знаеме она што е пред него. Што прават тие да се иницијализира на? 

Публика: Нивната вредност во нашата листа. 

ЈАСОН Hirschhorn: Значи она што е Првото нешто на нашиот список? Или како да знаеме каде почетокот на нашата листа е? 

Публика: Зарем не е донесен во функција? 

ЈАСОН Hirschhorn: Право. Тоа беше донесен во право тука. Па ако е донесен во функција, почетокот на листата, што треба ние постави сегашниот еднаква на? 

ПУБЛИКАТА: Листа. 

ЈАСОН Hirschhorn: Листа. Тоа е точно. Сега, тоа е адресата на почетокот на нашата листа. А што е со претходната? 

ПУБЛИКАТА: Листа минус еден? 

ЈАСОН Hirschhorn: Има ништо пред него. Така што можеме да направиме за да се означи ништо? 

Публика: Нулев. 

ЈАСОН Hirschhorn: Да. Тоа звучи како добра идеја. Совршена. Ви благодарам. Поминат низ листата. Константин, колку долго ќе се дојде да се оди низ листата? 

Публика: додека не ги добиеме нула. 

ЈАСОН Hirschhorn: OK. Значи, ако, додека, за телефонска линија. Што правиме? 

ПУБЛИКАТА: Можеби за телефонска линија? 

ЈАСОН Hirschhorn: Ајде да направиме за телефонска линија. OK. 

ПУБЛИКАТА: И ние се каже за - додека тековната покажувачот не е еднаква на нула. 

ЈАСОН Hirschhorn: Значи, ако знаеме состојба, како можеме да се напише јамка базирана таа состојба. Каков вид на јамка што ние треба да ги користите? 

ПУБЛИКАТА: Додека. 

ЈАСОН Hirschhorn: Да. Што го прави повеќе смисла врз основа надвор од она што го рече. Ако ние само сакаме да одиме во што тоа би само знам дека нешто, тоа ќе го направи смисла да се направи додека јамка. Додека моменталниот не е еднакво на нула, ако вредноста е помала од овој јазол. Akshar, дај ми оваа линија. 

Публика: Ако тековната> n n помалку од вредноста. Или да го поништи тоа. Прекинувач кој заграда. 

ЈАСОН Hirschhorn: Извини. 

ПУБЛИКАТА: Промена на заграда. 

ЈАСОН Hirschhorn: Значи, ако тоа е поголема од вредноста. Затоа што тоа е збунувачки со коментира погоре, јас ќе одам да направите тоа. Но да. Ако нашите вредност е помала од оваа јазол, што ќе правиме? Ох. Го имам токму тука. Вметнете порано. OK. Како го правиме тоа? 

Публика: Дали е сè уште ме? 

ЈАСОН Hirschhorn: Да. 

ПУБЛИКАТА: Вие - new_node-> Next. 

ЈАСОН Hirschhorn: Значи она што е дека ќе се изедначи? 

Публика: Тоа се случува да еднакви струја. 

ЈАСОН Hirschhorn: Токму така. И така од друга - Што уште ни треба да се ажурираат? 

Публика: Проверете дали минатото еднаква на нула. 

ЈАСОН Hirschhorn: Ако prev - па ако prev еднаква на нула. 

Публика: Тоа значи дека ќе да стане главата. 

ЈАСОН Hirschhorn: тоа значи тоа стана главата. Па тогаш што правиме? 

ПУБЛИКАТА: Ние го правиме главата еднаква new_node. 

ЈАСОН Hirschhorn: Раководител еднакво new_node. И зошто се упатат тука, не листа? 

ПУБЛИКАТА: Бидејќи главата е глобален променлива, што е почетна место. 

ЈАСОН Hirschhorn: Слатка. OK. И - 

ПУБЛИКАТА: Тогаш вие друго prev-> Следниот еднаква new_node. А потоа ќе се врати вистина. 

ЈАСОН Hirschhorn: Каде да ние постави new_node крајот? 

Публика: Јас би - Јас во собата што на почетокот. 

ЈАСОН Hirschhorn: Па што линија? 

ПУБЛИКАТА: По ако изјава проверка, ако тоа е познато. 

ЈАСОН Hirschhorn: Право овде? 

Публика: Јас би го сторила new_node-> n еднакво вредност. 

ЈАСОН Hirschhorn: Звучи добро. Веројатно тоа го прави смисла - ние не треба да знаеш што листа ние сме на бидејќи ние сме само се занимаваат со една листа. Па подобро функцијата декларација за ова е само за да се ослободи од овој целосно и само внесете вредност во главата. Ние дури и не треба да знаете она листа ние сме внатре Но јас ќе го задржи за сега и тогаш тоа се промени по ажурирање слајдови и код. Така што изгледа добро за сега. Ако вредноста - кој може да го направи оваа линија? Ако - што ќе правиме тука, Ноа. 

Публика: Ако вредноста е поголема од Мом-> n - 

ЈАСОН Hirschhorn: Како да ние одиме на следниот јазол? 

Публика: Мом-> n е еднаква на new_node. 

ЈАСОН Hirschhorn: Значи n е она што дел од struct? Цел број. И new_node е покажувач кон еден јазол. Па што дел од Мом ние треба да се ажурираат? Ако не е n, тогаш што е другиот дел? Ное, она што е на другата страна. 

ПУБЛИКАТА: О, следната. 

ЈАСОН Hirschhorn: Напред, точно. Токму така. Следна е вистинскиот. И што друго ни треба да се ажурира, Ноа? 

Публика: покажувачи. 

ЈАСОН Hirschhorn: Значи ние нема струја. 

Публика: Претходна-> Next. 

ЈАСОН Hirschhorn: Да. Во ред, ќе се откажеш. Кој може да ни помогне тука? МАНУ, она што ние треба да направам? 

ПУБЛИКАТА: Имаш да го поставите тоа еднаков на Мом-> Next. Но го направи тоа пред претходната линија. 

ЈАСОН Hirschhorn: OK. Нешто друго? Akshar. 

Публика: Јас не мислам дека ти си цел да се променат Мом-> Next. Мислам дека се наменети да се направи Мом еднаквите Мом-> следната да оди на следниот јазол. 

ЈАСОН Hirschhorn: Навистина ми е жал, каде? На она што линија? Оваа линија? 

Публика: Да. Направи Мом еднаква на Мом-> Next. 

ЈАСОН Hirschhorn: Значи тоа е точно бидејќи струјата е Покажувач на јазол. И ние сакаме тоа да укаже на следните јазол на она што се добива во моментов посочи. Мом себе има следната. Но ако ние требаше да се ажурира curr.next, ние ќе биде ажурирање на вистинските белешка сама по себе не, каде што овој покажувачот беше посочувајќи. Она што за оваа линија, иако. Ави? 

Публика: Претходна-> Следниот еднаква ВАЛ. 

ЈАСОН Hirschhorn: Значи повторно, ако prev е покажувач на еден јазол, prev-> Следниот е Крај на покажувачот во јазол. Така што ова ќе биде ажурирање на покажувачот во јазол да ВАЛ. Ние не сакаме да се ажурира покажувач во јазол. Ние сакаме да се ажурира претходниот. Па, како го правиме тоа? 

Публика: Тоа само ќе биде prev. 

ЈАСОН Hirschhorn: Право. Prev е покажувач кон еден јазол. Сега ние сме го менува на нови покажувач на еден јазол. Добро Дозволете ни да се движат надолу. Конечно, последниот услов. Џеф, што ќе правиме тука? 

Публика: Ако вредноста е еднаква на Мом-> n. 

ЈАСОН Hirschhorn: Извини. Ох моја добрина. Што? Вредност == Мом-> n. Што ќе правиме? 

Публика: Ќе ги ослободи нашите new_node, и тогаш ќе се вратат лажни. 

ЈАСОН Hirschhorn: Тоа е она што имаме напишано досега. Дали некој има било за да додадете, пред да се направи? OK. Ајде да ја обидат. Контрола може да стигне до крајот на не-празнина функција. AVI, она што се случува? 

Публика: Дали сте би требало да се стави враќање вистина надвор од додека јамка? 

ЈАСОН Hirschhorn: Не знам. Дали ме сакате во моментов? 

ПУБЛИКАТА Ништо. Бр. 

ЈАСОН Hirschhorn: Akshar? 

ПУБЛИКАТА: Мислам дека со цел да се стави враќање лажни на крајот на додека јамка. 

ЈАСОН Hirschhorn: Значи, каде Дали сакате да одите? 

Публика: Како надвор додека јамка. Па ако излезете, додека јамка тоа значи дека кога сте достигнавме крајот и ништо не се случило. 

ЈАСОН Hirschhorn: OK. Па што ќе правиме тука? 

ПУБЛИКАТА: Вие враќање false така и таму. 

ЈАСОН Hirschhorn: О, ние го прават тоа и во двете места? 

Публика: Да. 

ЈАСОН Hirschhorn: OK. Ние треба да одиме? Ох моја добрина. Жал ми е. Јас се извинувам за екранот. Тоа е вид на freaking надвор од нас. Така избирате опција. Нула, за на код, поднесе оставка на програмата. Еден внесува нешто. Ајде да вметнете три. Вметнете не беше успешна. Одам да испечатите. Јас немам ништо. OK. Можеби тоа беше само среќа. Вметнете еден. Не е успешна. OK. Ајде да ја извршите преку GDB навистина брзо да проверат што се случува. 

Се сеќавам gdb. / Името на вашиот програма ни се впушта во gdb. Е дека многу да се справи? Светлечки? Веројатно. Затвори ги очите и да преземат некои длабоки вдишувања, ако ви се уморни на гледање на него. Јас сум во gdb. Што е првото нешто што го правам во GDB? Ние мора да дознаам она што се случува овде. Ајде да видиме. Имаме шест минути да фигура од она што се случува. Се скрши главната. И тогаш што можам да направам? Carlos? Работи. OK. Ајде да изберете опција. И она што не N направам? Следната. Да. 

Публика: Не да се спомене - не ви каже дека на главата, што беше иницијализиран на нула на почетокот. Но јас мислев, дека ти рече дека е во ред. 

ЈАСОН Hirschhorn: Ајде да одиме - ајде да погледнеме во GDB, а потоа ние ќе се вратиме. Но тоа звучи како имате некои идеи за тоа што се случува. Затоа сакаме да вметнете нешто. OK. Ние сме го внесете. Ве молиме внесете Инт. Ние ќе се вметне три. И тогаш јас сум на оваа линија. Како можам да се обратите на проектот дебагирање вметнете позната функција? Ох моја добрина. Тоа е многу. Е дека freaking надвор многу? 

ПУБЛИКАТА: О, тоа починал. 

ЈАСОН Hirschhorn: Јас само извадив. OK. 

Публика: Можеби тоа е другиот крај на жица. 

ЈАСОН Hirschhorn: Леле. Значи крајна линија - Што велите вие? 

Публика: Јас реков иронијата на технички тешкотии во оваа класа. 

ЈАСОН Hirschhorn: Знам. Ако само имав контрола над тој дел. [Нечујни] Тоа звучи одлично. Зошто не сте момци почнат да размислуваат за што би можеле да имаат направено погрешно, и ние ќе се врати во 90 секунди. 

Avica, јас ќе одам да ве прашам како да се обратите внатре insert_node да го debug. Значи ова е местото каде што минатата останев. Како можам да се обратите во внатрешноста insert_node, Avica, да се испита што се случува? Што GDB команда? Пауза не би ме однесе внатре. Дали Marquise знаеш? 

Публика: Што? 

ЈАСОН Hirschhorn: Што GDB команда Јас го користам за да се влезе внатре оваа функција? 

Публика: чекор? 

ЈАСОН Hirschhorn: Чекор преку С Тоа ме носи внатре. OK. New_node mallocing малку простор. Дека сите изгледа како неговите се случува. Да се ​​испита new_node. Таа доби некои меморија адреса. Ајде проверете - тоа е сите точни. Така што тука се чини дека да се работи правилно. 

Публика: Што е разликата помеѓу P и прикажување? 

ЈАСОН Hirschhorn: P залага за печатење. И така си бара она што е Разликата меѓу кои и ова? Во овој случај, ништо. Но генерално постојат некои разлики. И треба да се погледне во упатството gdb. Но, во овој случај, ништо. Ние тежнееме да го користите печати, иако, бидејќи ние не треба да се направи многу повеќе отколку печати една вредност. 

OK. Па ние сме на линија 80 од нашиот код, поставување јазол * Мом еднаква на листата. Дозволете ни да испечатите ВАЛ. Тоа е еднакво на листата. Слатка. Чекаат. Изнесува нешто. Тоа не изгледа право. Таму ќе одиме. Тоа е затоа што во GDB, десно, ако тоа е линија ти си на неа Сè уште не погубен. Така што треба да всушност тип до извршување на линијата пред да го видат неговите резултати. Значи тука сме. Ние само извршува оваа линија, претходната еднаква на нула. Значи, повторно, ако ние печати претходната ние нема да видите ништо чудно. Но, ако ние всушност се изврши што линија, а потоа ќе видиме дека ресорните работел. 

Па ние имаме ВАЛ. Оние кои се и добри. Нели? Сега ние сме на оваа линија, токму тука. Додека Мом не го прави еднаков нула. Па, она што го прави Мом еднакви? Ние само видов изнесуваше нула. Ние го испечати. Јас ќе го испечатите повторно. Така е дека додека јамка ќе изврши? 

ПУБЛИКАТА: Не 

ЈАСОН Hirschhorn: Значи, кога јас ја внеле дека линија, ќе видите што скокна по целиот пат надолу кон дното, се врати лажни. А потоа ние ќе се врати лажни и се врати на нашата програма и на крајот испечатите, како што видовме, вметнете не беше успешна. Значи, некој има било какви идеи за тоа што ние треба да направите за да го надминете овој? Одам да се почека додека не го видите неколку раце одат нагоре. Ние не се изврши тоа. Имајте на ум, ова е прв нешто правиме. Јас не одам да се направи двојка. Јас ќе одам да направите неколку. Бидејќи неколку значи две. Јас ќе чекам за повеќе од две. 

Првиот вметнување, Мом, стандардно еднаква на нула. И овој циклус само извршува ако Мом не е нула. Па како можам да се добие околу ова? Гледам три раце. Јас ќе чекам за повеќе од три. Маркус, што мислите? 

ПУБЛИКАТА: Па, ако ви треба за да се изврши повеќе од еднаш, вие само измени го на не-додека јамка. 

ЈАСОН Hirschhorn: OK. Што ќе го реши нашиот проблем, иако? 

ПУБЛИКАТА: Во овој случај нема поради фактот дека листата е празна. Па тогаш веројатно само треба да додадете изјава дека доколку јамка излези тогаш ќе мора да биде на крајот на на листата, на која ќе укаже само да го внесете. 

ЈАСОН Hirschhorn: Ми се допаѓа тоа. Кој што има смисла. Ако јамка излегува - затоа што тоа ќе се вратат лажни тука. Значи, ако јамка излези, тогаш ние сме во на крајот на листата, или можеби почетокот на листата, ако нема ништо во , која е иста како и на крајот. Па сега ние сакаме да го вметнете нешто тука. Па како не дека кодот погледне, Маркус? 

Публика: Ако веќе доби јазол malloced, вие само може да се каже new_node-> Следниот еднаква на нула, бидејќи тоа мора да биде на крајот. Или new_node-> Следниот еднаква на нула. 

ЈАСОН Hirschhorn: OK. Жал. New_node-> Следниот еднаква на нула бидејќи ние сме на крајот. Која не ја стави внатре Како ние да го стави во листата? Во право. Тоа е само тоа поставување еднаква на. Не како ние всушност го ставив во листата? Што да се покажува кон крајот на листата? 

Публика: Раководител. 

ЈАСОН Hirschhorn: Молам? 

Публика: Раководител е да се покажува до крајот на листата. 

ЈАСОН Hirschhorn: Ако нема ништо во листата, глава е да се покажува кон крајот на листата. Така што ќе работат за Првиот вметнување. Што ако постојат неколку работи во листата? Отколку што не сакате да го поставите главата еднаква на new_node. Што сакаме да се направи таму? Да? Веројатно претходната. Кои ќе работат? Потсетиме дека претходната е само покажувач на еден јазол. И претходните претставува локална променлива. Па оваа линија ќе се постави локална променлива, претходната, еднаква или укажувајќи на овој нов јазол. Дека не, всушност, ќе го стави во нашата листа, иако. Како ние да го стави во нашиот список? Akchar? 

Публика: Јас мислите направи тековната> Next. 

ЈАСОН Hirschhorn: OK. Мом-> Next. Значи, повторно, единствената причина ние сме долу тука е, она што го прави сегашната еднакви? 

Публика: еднакво нула. 

ЈАСОН Hirschhorn: И така она што се случува ако правиме нула-> следно? Што ќе добиете? Ќе добие сегментација вина. 

Публика: Дали Мом еднаква на нула. 

ЈАСОН Hirschhorn: Тоа е истото како prev, иако, бидејќи има локална променлива ние сме поставување еднаков на овој нов јазол. Да се ​​вратиме на нашата слика на вметнување нешто. Велат ние сме вметнување на крајот на листата, па токму од овде. Имаме тековната покажувачот тоа е укажувајќи на нула и претходната точка тоа е покажувајќи на 8. Значи она што ние треба да се ажурира, Ави? 

Публика: Претходна-> следно? 

ЈАСОН Hirschhorn: Претходна-> следната е она што ние сакаме да се ажурира, бидејќи тоа всушност, ќе го вметнете на на крајот на листата. Ние се уште имаат една грешка, сепак, дека ние сме случува да се кандидира во. Што е тоа баг? Да? 

Публика: Тоа се случува да се вратат лажни во овој случај? 

ЈАСОН Hirschhorn: Ох, е е ќе се врати лажни. Но, има уште еден баг. Па ние ќе треба да се стави во замена вистина. 

Публика: Дали претходната уште еднаков нула на врвот на листата? 

ЈАСОН Hirschhorn: Значи претходната уште еднакво null уште на самиот почеток. Па како може да се добие во текот на тоа? Да? 

Публика: Мислам дека може да се направи проверка пред додека јамка за да видат дали тоа е празна листа. 

ЈАСОН Hirschhorn: OK. Па ајде да одиме тука. Направи проверка. Ако - 

Публика: Значи, ако главата еднакво еднаква на нула. 

ЈАСОН Hirschhorn: Ако главата еднакво еднаква на нула - дека ќе ни каже дали тоа е празна листа. 

Публика: И тогаш ќе направи главата еднаква на нови. 

ЈАСОН Hirschhorn: Раководител еднакво new_node? И што друго не ни треба да направам? 

Публика: И тогаш ќе се вратите точно. 

ЈАСОН Hirschhorn: не сосема. Ние сме недостасува еден чекор. 

Публика: New_node следната мора да се укаже на нула. 

ЈАСОН Hirschhorn: Точно, Alden. А потоа можеме да се вратат точно. OK. Но тоа е уште една добра идеја да се прават работите на крајот на листата, право? Во ред е. Ние се уште всушност може да се добие до крајот на листата. Така е овој код казна ако ние сме на крајот на листата и има некои работи во листата? Нели? Бидејќи ние се уште имаат идеја на Marcus. Ние би можеле да излезете овој циклус, бидејќи ние сме на крајот на листата. Па ние се уште сакаме оваа кодот овде? 

Публика: Да. 

ЈАСОН Hirschhorn: Да. И она што ние треба да го промените ова? Точно. Дали тоа звучи добро за секого досега? Секој имате било какви - AVI, имате нешто да додадете? 

ПУБЛИКАТА: Не 

ЈАСОН Hirschhorn: OK. Па ние направивме неколку промени. Ние сторивме оваа проверка пред да отиде во за празна листа. Па ние сме згрижени празна листа. И тука ние се грижеше за вметнување нешто на крајот на листата. Па ми се чини дека ова додека јамка земање грижат за нешта меѓу нив, некаде во листата ако има се работи во листата. 

OK. Дозволете ни да ја извршите оваа програма повторно. Не е успешна. 

Публика: Вие не го направи. 

ЈАСОН Hirschhorn: О, Јас не го направи. Добра поента, Мајкл. Ајде да додадете шминка поврзани. Линија 87 има грешка. Линија 87. Alden, ова беше линијата ќе ми даде. Што е проблемот? 

Публика: Тоа мора да биде на нула. 

ЈАСОН Hirschhorn: Одлично. Точно во право. Тоа треба да биде нула. Да се ​​направи повторно. Компајлирате. OK. Ајде да вметнете три. Вметнете беше успешна. Ајде да го испечатите. Ох, ако само ние би можеле да се провери. Но, ние не го направиле функција за печатење сеуште. Ајде да внесете нешто друго. Она што ние треба да влезе? 

ПУБЛИКАТА: Седум. 

ЈАСОН Hirschhorn: Седум? 

Публика: Да. 

ЈАСОН Hirschhorn: Имаме сегмент вина. Па добивме една, но ние јасно не може да добие две. Тоа е 05:07. Па ние би можеле debug ова за три минути. Но јас ќе одам да ни остави тука и се движи кон хаш маси. Но, повторно, одговорите за овој код Јас ќе го мејл до вас во малку. Ние сме многу блиску до него. Силно ве охрабруваме да дознаам она што се случува овде и да ја поправите тоа. Затоа јас ќе ви мејл овој код како и плус решение - веројатно решение подоцна. Првиот овој код. 

Од друга работа што сакате да го направите пред да финиш е не сме ослободени ништо. Па сакам да ви покажам што valgrind изгледа. Ако трчаме valgrind граници на нашата програма,. / поврзани. Повторно, според овој слајд, ние треба да се подигне valgrind со некои од типот на опција, во овој случај - Течење-проверка = целост. Па ајде да пишуваме valgrind - Течење-проверка = целост. Па ова ќе се кандидира valgrind на нашата програма. И сега на програмата всушност работи. Па ние ќе да се пушта само како пред, се стави нешто внатре Одам да се стави во три. Која работи. Јас не одам да се обиде да се стави во нешто друго, бидејќи ние се случува да се добие сегмент лажни во тој случај. Па јас сум само ќе се откажам. 

И сега може да се види овде излегуваат во јавноста и грамада резиме. Овие се добри работи што дека сакате да го проверите. Па грамада резиме - се вели, е во употреба на излез - осум бајти во еден блок. Дека еден блок е јазол ние malloced. Мајкл, ти рече пред еден јазол е осум каснувања бидејќи има целобројни и покажувач. Па тоа е нашата јазол. И тогаш тоа вели дека ние се користи Примерок седум пати и ние ослободен нешто шест пати. Но, ние никогаш наречени слободни, па јас немам претстава што ова се зборува. 

Но доволно е да се каже дека кога Вашиот Програмата тече, Примерок се нарекува во некои други места дека ние не треба да се грижите. Па Примерок најверојатно наречена во некои места. Ние не треба да се грижите каде. Но ова е навистина нас. Оваа прва линија е со нас. Го напуштивме тој блок. И можете да видите дека тука во протекувањето резиме. Уште Комуникативен - осум бајти во еден блок. Тоа значи дека меморијата - ние сме протекоа дека меморијата. Дефинитивно изгубени - нешто се губи засекогаш. Општо земено, ќе не гледам ништо таму. Уште Комуникативен е генерално каде ќе видите работи, каде што ќе сакате да се погледне да видите што кодот треба да ви ги ослободија, но сте заборавиле да го ослободи. 

А потоа, ако тоа не е случај, ако ние го сторивме бесплатно сè, може да се провери тоа. Ајде да ја стартувате програмата не пуштање во ништо. Ќе видите овде во употреба на излез - нула бајти во нула блокови. Тоа значи дека ние нема никаква лево кога оваа програма излезено. Значи пред да наполнат во pset6, работи valgrind и бидете сигурни дека немате било меморија протекување во својата програма. Ако имате било какви прашања со valgrind, се чувствуваат слободни да допрат. Но, ова е како ќе го користите. Многу едноставна - да видиме ако имаат во употреба на излез - било бајти во било блокови. 

Па ние се работи на вметнете јазол. Имав две други функции тука - печати јазли и слободни јазли. Повторно, овие се функции кои се ќе биде добро за вас да се практикуваат бидејќи тие ќе ви помогнат не само со овие примерок вежби, но, исто така, на проблемот во собата. Тие сајтот на прилично тесно да работи сте ќе треба да се направи во проблем во собата. Но, јас сакам да бидете сигурни дека ние се смести на сè. И хаш маси се исто така клучна за она што го правиме во делот на овој недела - или во проблемот во собата. 

Па ние ќе се заврши делот зборуваме за хеш табели. Ако забележите сум направил малку хаш табелата. Тоа не е она што ние зборуваме за, сепак. Станува збор за еден поинаков тип на хеш табели. И на неговото јадро, хеш табелата не е ништо повеќе од еден низа плус хеш функција. Ние ќе зборуваме за малку само за да бидете сигурни дека секој го разбира она што е хаш функција е. И јас ви го кажувам сега дека тоа е ништо повеќе од две работи - низа и хаш функција. И тука се чекори преку кои оваа работи. 

Таму е нашата низа. Таму е нашата функција. Особено, хаш функции треба да направи неколку нешта со ова. Одам да се зборува конкретно за овој проблем во собата. Тоа е веројатно нема да земе во низа. И што е тоа ќе се врати? Што тип на податок? Alden? Вашиот хаш функција се врати? Цел број. Значи тоа е она што на хаш маса се состои од - маса во форма на низа и хаш функција. Како тоа функционира? Таа работи во три чекори. Ние го даде клучот. Во овој случај, ние ќе го даде стринг. Ние го нарекуваме хаш функција по чекор еден на клучот и да добиеме вредност. 

Поточно, ние ќе каже добиеме цел број. Дека цел број, постојат многу специфични ограничувања на она што цел број може да биде. Во овој пример, нашите низа е на големината три. Па што броеви кои цел број може да биде. Што е опсегот на валидни вредности за дека цел број, враќање видот на оваа хаш функција? Нула, еден и два. Точка на хаш функција е да дознаам место во низа каде што нашите клучни се случува. Постојат само три можни места тука - нула, еден или два. Па оваа функција подобро враќање нула, еден или два. Некои валидни indice во оваа низа. 

А потоа во зависност од тоа каде тој се враќа, можете да видите има низа отворени заградата вредност. Тоа е каде што ќе стави клуч. Па ние фрли во тиква, ние се излезе нула. На низа заграда 0, ќе стави тиква. Ние фрли во мачки, ќе излеземе еден. Ќе стави мачката во една. Ние се стави во пајак. Ние излезат две. Ние се стави пајакот на низа заграда две. Тоа ќе биде толку убаво ако тој работел како што. Но, за жал, како што ќе видиме, тоа е малку покомплицирано. 

Пред да се влезе таму, било какви прашања за оваа основна поставување на хеш табелата? Ова е слика на точно она што го привлече на табла. Но бидејќи ние го привлече на табла, јас не сум случува да одам во неа понатаму. Во суштина клучеви, магијата црна кутија - или во овој случај, ТЕАЛ кутија - на хаш функција ги става во кофи. И во овој пример ние сме не ставање на името. Ние сме ставање на поврзани телефон Бројот на име во кофа. Но вие можете да многу добро само стави името во кофа. 

Ова е само слика на она што ние привлече на табла. Имаме потенцијални стапици, иако. И постојат две особено слајдови дека сакам да одам повеќе. Првиот е за хеш функција. Па јас го поставил прашањето, што што го прави добар hash функција? Давам два одговори. Првата е дека тоа е детерминистички. Во контекст на хаш функции, што значи ова? Да? 

Публика: Тоа може да се најде на индекс во постојан време? 

ЈАСОН Hirschhorn: Тоа не е она што тоа значи. Но тоа е добар се погоди. Некој друг има претпоставка на она што значи ова? Дека добар hash функција е детерминистички? Annie? 

Публика: дека клучниот само може да биде одбележан на едно место во хеш табелата. 

ЈАСОН Hirschhorn: Тоа е точно во право. Секој пат кога ќе се стави во тиква, таа секогаш се враќа на нула. Ако се стави во тиква и вашиот хаш функцијата враќа нула, но има веројатноста за враќање нешто друго поголема од нула - па можеби тоа може да се врати еден понекогаш или две други времиња - дека не е добар hash функција. Ти си точно во право. Вашиот hash функција треба да се врати исто точно цел број, во овој случај, за исто точно стринг. 

Можеби тоа се враќа со иста точната цел број за истата точната низа без оглед на капитализација. Но, во тој случај тоа е уште детерминистички бидејќи повеќе работи се мапирани со иста вредност. Тоа е во ред. Додека постои само една излез за даден влез. 

OK. Втората работа е дека тоа се враќа валидна индекси. Ние донесе до тоа порано. Овој хаш функција - О момче - хеш функција треба врати валидна индекси. Така да се каже - ајде да се вратиме на овој пример. Мојата хаш функција Брои до букви во зборот. Тоа е хеш функција. И се враќа дека цел број. Па ако имам зборот А, тоа е ќе се врати еден. И тоа се случува да се стави во право тука. Што ако јас се стави во зборот лилјак? Тоа се случува да се врати три. Каде лилјак одиме? 

Тоа не се вклопува. Но, таа треба да оди некаде. Ова е мојот хеш табелата по сите, и сè треба да оди некаде. Па каде лилјак треба да одат? Било кој мисли? Нагаѓања? Добра нагаѓања? 

ПУБЛИКАТА: Нулта. 

ЈАСОН Hirschhorn: Зошто нула? 

ПУБЛИКАТА: Поради три modulo три е нула? 

ЈАСОН Hirschhorn: Три modulo три е нула. Тоа е голема претпоставка, и тоа е точно. Така што во овој случај треба да веројатно одат на нула. Па добар начин да се осигура дека оваа хаш функција враќа само валидни индексите е за да го modulo од големината на маса. Ако modulo што овој се враќа од три, ти си секогаш ќе добие нешто помеѓу нула, еден, и два. И ако тоа секогаш се враќа седум, а секогаш modulo од три, ти си секогаш ќе го добиете истото. 

Па тоа е уште детерминистички ако modulo. Но, тоа ќе се осигури дека ќе никогаш не се добие нешто - неправилен индустрија. Општо земено, тоа modulo треба да се случи во внатрешноста на вашиот хеш функција. Значи, вие не треба да се грижите за тоа. Можете само да се осигура дека ова е валидна indice. Било какви прашања на овој потенцијал замка? 

OK. И таму ќе одиме. Следниот потенцијален замка, и ова е голем. Што ако две копчиња сајтот со иста вредност? Па така постојат два начини да се справи со ова. Првиот се нарекува линеарно љубопитство, за што јас сум нема да одат над. Но треба да бидете запознаени со тоа како кој работи и што е тоа. 

Вториот идам да одат над бидејќи тоа е она што многу луѓе веројатно ќе заврши одлучувањето да ги користат во својот проблем во собата. Се разбира, вие не мора да. Но, за проблемот во собата, многу луѓе имаат тенденција да изберете да се создаде хеш табелата со посебен врзувањето за спроведување на нивниот речник. Па ние ќе да се премине што значи тоа да се создаде хеш табелата со посебна врзувањето. 

Па да го ставам во тиква. Тој се враќа на нула. И јас се стави тиква тука. Потоа ја ставив во - што е уште еден Ноќта на вештерките-тематските нешто? 

ПУБЛИКАТА: Кенди. 

ЈАСОН Hirschhorn: Кенди! Тоа е одлично. Ја ставив во бонбони, и бонбони Исто така ми дава нула. Што да правам? Сите идеи? Бидејќи сите што вид на знаете она што одделни врзувањето е. Па било какви идеи што да правам? Да. 

Публика: Ставањето на низа всушност, во хеш табелата. 

ЈАСОН Hirschhorn: Значи ние ќе исцртување на добра идеја овде. OK. 

Публика: Имаат hashtable [Нечујни] на покажувачот што укажува на на почетокот на листата. А потоа се тиква биде првиот вредност во таа поврзана листа и бонбони биде втората вредност во кои се поврзани листата. 

ЈАСОН Hirschhorn: OK. Marcus, тоа беше извонредна. Одам да се скрши дека долу. Маркус вели не пребришете тиква. Тоа би било лошо. Не ставајте бонбони некаде на друго место. Ние ќе ги стави двете на нула. Но ние ќе се справи со ставајќи ги на нула од создавање на листа на нула. И ние ќе се создаде листа на сè што одбележан на нула. И на најдобар начин научивме да се создаде листата што може да расте и се намалува динамички не е во рамките на уште низа. Па не е мулти-димензионална низа. Но само да се создаде поврзана листа. 

Така што тој предлага - Одам да се добие нов - е да се создаде низа со покажувачи, низа на совети. OK. Секоја идеја или сугестија што тип на овој совети треба да биде? Маркус? 

Публика: покажувачи да - 

ЈАСОН Hirschhorn: Затоа што изјави поврзана листа, па - 

Публика: Јазол совети? 

ЈАСОН Hirschhorn: Јазол совети. Ако работите во нашата поврзани листа се јазли, тогаш тие треба да биде јазол совети. И она што тие се изедначи првично? 

Публика: Нулев. 

ЈАСОН Hirschhorn: Нулев. Така што нашите празни работа. Тиква враќа нула. Што ќе правиме? Прошетка мене преку неа? Всушност, Маркус веќе ми го дадоа. Некој друг ме прошетка низ него. Што правиме кога сме - ова изгледа многу слични на она што бевме само прави. AVI. 

ПУБЛИКАТА: Одам да се погоди. Па кога ќе добие слатки. 

ЈАСОН Hirschhorn: Да. Па, добивме тиква. Ајде да се нашите првиот. Добивме тиква. 

Публика: OK. Тиква враќа нула. Па ќе го стави во тоа. Или, всушност, ќе го стави во поврзана листа. 

ЈАСОН Hirschhorn: Како да ја го ставив во поврзаните листа? 

ПУБЛИКАТА: О, вистинските синтакса? 

ЈАСОН Hirschhorn: Само прошетка - кажам повеќе. Што ќе правиме? 

Публика: Вие само внесете како на првиот јазол. 

ЈАСОН Hirschhorn: OK. Па ние имаме јазол, тиква. И сега како можам да го внесете? 

ПУБЛИКАТА: Вие додели до покажувач. 

ЈАСОН Hirschhorn: Кој покажувачот? 

Публика: покажувачот на нула. 

ЈАСОН Hirschhorn: Значи, каде Дали оваа точка? 

Публика: на нула во моментов. 

ЈАСОН Hirschhorn: Па, тоа е покажувајќи на нула. Но јас сум ставање во тиква. Па каде што треба да се истакне? 

Публика: Да тиква. 

ЈАСОН Hirschhorn: Да тиква. Токму така. Значи ова укажува на тиква. И каде го прави ова покажувачот во тиква точка? Да 

Публика: Нулев. 

ЈАСОН Hirschhorn: на нула. Токму така. Па ние само вметнува нешто во поврзаните листа. Ние само напишав овој код за да го направите тоа. Речиси ние речиси ја доби целосно разбиена. Сега ние вметнете слатки. Нашите бонбони исто така, оди до нула. Па што ќе правиме со бонбони? 

ПУБЛИКАТА: Тоа зависи од тоа дали или не се обидуваме да го средиме. 

ЈАСОН Hirschhorn: Тоа е точно во право. Тоа зависи од тоа дали или не ние се обидуваме да го средиме. Ајде да се претпостави ние не сме ќе го решите. 

Публика: Па тогаш, како што зборувавме пред, тоа е најобично само да го стави правото на почетокот, така покажувачот од нула поени за слатки. 

ЈАСОН Hirschhorn: OK. Држи се. Дозволете ми да се создаде бонбони во право тука. Значи ова покажувачот - 

Публика: Да, сега треба се укажува на слатки. Тогаш имаат покажувачот од бонбони точка за тиква. 

ЈАСОН Hirschhorn: Како тоа? И да каже добивме уште нешто да се на сајтот на нула? 

ПУБЛИКАТА: Па, ти само го прават истото? 

ЈАСОН Hirschhorn: Дали истото. Значи во овој случај, ако ние не сакате да го задржите тоа тоа сортирани звучи прилично едноставна. Земаме покажувачот во indice дадена од страна на нашите хеш функција. Имаме таа точка на нашиот нов јазол. А потоа што и да беше посочувајќи претходно - во овој случај нула, во Вториот случај тиква - дека, што и да се покажува кон претходно, ние го додадете во следната на нашиот нов јазол. Ние сме вметнување нешто на почетокот. Всушност, тоа е многу поедноставно отколку обидувајќи се да се задржи на списокот подредени. Но, повторно, пребарување ќе биде повеќе комплицирано тука. Ние секогаш ќе мора да одат до крај. 

OK. Какви прашања во врска одделни врзувањето? Како тоа функционира? Ве молиме прашајте ги сега. Јас навистина сакате да бидете сигурни дека сите се разбере ова, пред да главата. 

ПУБЛИКАТА: Зошто ви стават тиква и бонбони во иста дел од хеш табелата? 

ЈАСОН Hirschhorn: Добро прашање. Зошто ние ги стави во иста дел од хеш табелата? Па, во овој случај нашата hash функција враќа нула за двете од нив. Па тие треба да одат на indice нула бидејќи тоа е местото каде што ние ќе треба да изгледа за нив, ако ние некогаш сакате да ги гледам нагоре. Повторно, со линеарна љубопитство пристап ние не ќе ги стави двете на нула. Но во одделни синџир пристап, ние ќе ги стави двете на нула а потоа се создаде листа исклучување на нула. 

И ние не сакаме да ја пребришете тиква едноставно за тоа, бидејќи тогаш ние ќе претпостави дека тиква беше никогаш не е вметната. Ако ние само задржи едно нешто во локација која ќе биде лошо. Тогаш нема да има Можност за нас некогаш - ако ние некогаш сте имале дупликат, тогаш ние само ќе ги избрише нашата почетна вредност. Па тоа е зошто тоа го правиме овој пристап. Или тоа е причината зошто сме го одбрале - но повторно, ние избра посебен врзувањето пристап, кои има многу други пристапи би можело да одберете. Дали тоа одговори на вашето прашање? 

OK. Карлос. Линеарни љубопитство би вклучиле - ако најдеме судир на нула, а ние ќе изгледа во следните самото место да се види дали беше отворен и го стави таму. А потоа ние со нетрпение во текот на следните спорт и види дали тоа беше отворен и го стави таму. Па ние се најдат на следниот достапни отворена на самото место и го стави таму. Било какви други прашања? Да, Ави. 

Публика: Како се надоврзе на тоа, што сакаш да кажеш со следната точка? Во хеш табелата или во поврзана листа. 

ЈАСОН Hirschhorn: За линеарни програмирање, нема поврзани листи. Следниот место на хаш табелата. 

Публика: OK. Па хеш табелата ќе биде иницијализиран на големината - како на бројот на жици дека сте биле вметнувањето? 

ЈАСОН Hirschhorn: Дали си сакате да биде навистина голема. Да. Тука е слика на она што ние само привлече на табла. Повторно, имаме судир во право тука. на 152. И ќе видите ние направивме поврзан листа надвор од неа. Повторно, хеш табелата посебен врзувањето пристап не е оној што го треба да ги преземат за проблемите во собата шест, но е оној кој многу Учениците имаат тенденција да се земе. Па за тоа белешка, нека зборуваат кратко пред ние главата надвор за проблемот шест, а потоа јас ќе го споделам една приказна со вас. Имаме три минути. 

Проблемот постави шест. Ќе има четири функции - оптоварување, проверете, големина, и бриши. Оптоварување - Па, ние сме се случува над оптоварување само сега. Ние привлече оптоварување на табла. А ние дури и почна кодирање многу вметнување во поврзана листа. Значи оптоварување не е многу повеќе од она што ние само се прави. 

Проверете е еднаш имате нешто вчитан. Тоа е истиот процес како овој. Исто првите два дела, каде што ќе фрли нешто во hash функција и да добијат својата вредност. Но сега ние не сме го вметнување. Сега сме во потрага по него. Имам примерок код напишан за изнаоѓање нешто во поврзана листа. Јас ве охрабруваме да се практикуваат тоа. Но интуитивно наоѓање на нешто е прилично слична на вметнување нешто. Всушност, ние нацртал цртеж од изнаоѓање нешто во поврзана листа, движејќи се преку додека не стигнав до крај. И ако стигнав до крај и не може да најде тоа, тогаш тоа не е таму. Па тоа е чек, во суштина. 

Следна е големината. Ајде да го прескокнете големина. Конечно ќе се исклучи. Бриши е една не сме подготвени на табла или кодиран уште. Но јас ве охрабруваме да се обидат кодирање тоа во нашиот примерок поврзана листа пример. Но бриши интуитивно е слична на бесплатно - или сакам да кажам е сличен да се провери. Освен за сега секој пат кога ќе си оди преку, вие не сте едноставно проверка за да види, ако имате вашата вредност таму. Но ти си земајќи тој јазол и ослободувајќи го, во суштина. Тоа е она што бриши ве прашува да се направи. Слободен сè што сте malloced. Па ти си минува низ цела листа повторно, да оди преку целиот хаш маса повторно. Овој пат не се провери за да го видиш она што е таму. Само бесплатно она што е таму. 

И конечно големина. Големина треба да се спроведува. Ако не се имплементира големина - Јас ќе го кажам вака. Ако не се имплементира големина во точно една линија на код вклучувајќи врати изјава, вие сте прави големина погрешно. Така осигурајте се дека големината, за целосна дизајн поени, сте го прави тоа во точно една линија код, вклучувајќи враќање изјава. 

И не се спакуваат сепак, Akchar. Желни брада. Сакав да ви кажам благодарам момци за доаѓање до секција. Имаат среќен Ноќта на вештерките. Ова е мојот костимот. Јас ќе се носи оваа во четвртокот ако ти се види на работното време. И ако сте љубопитни за некои повеќе позадина како на оваа носија, се чувствуваат слободно да се провери од 2011 секција за една приказна за тоа зошто јас сум облечен тиква костимот. И тоа е една тажна приказна. Така бидете сигурни дека имате некои ткива во близина. Но на тоа, ако имате било какви прашања јас ќе се држи околу надвор по секција. Со среќа на проблемот постави шест. И како и секогаш, ако имате било какви прашања, дозволете ми да знам.