[Powered by Google Translate] [6 недеља, наставак] [Давид Ј. Малан] [Универзитет Харвард] [Ово је ЦС50.] [ЦС50.ТВ] Ово је ЦС50 и то је крај недеље 6. Дакле ЦС50к, један од првих курсева Харварда укључених у ЕДКС иницијативи Заиста је дебитовао прошле понедељак. Уколико желите да добијете увид у оно што други на Интернету сада следи заједно са, можете кренути за к.цс50.нет. То ће вас преусмерити на одговарајуће место на едк.орг, која је била где је овај и други предмети из МИТ и Беркли сада живе. Мораћете да се пријавите на налог, видећете да је материјал углавном иста као што сте имали овог семестра, иако само неколико недеља касни, јер смо добили све спремно. Али оно што студенти у ЦС50к ће сада видети је интерфејс баш као овај. То је, на пример, Замила води са описом проблема на сету 0. Након логовања на едк.орг, ЦС50к ученик види свашта можете очекивати да видите у току: предавање за понедељак, предавање за среду, разни шортс, проблем сетови су сцреенсхотс, ПДФ. Поред тога, као што видите овде, машински преводи енглеских транскрипата у кинески, јапански, шпански, италијански, и гомила других језика који ће свакако бити несавршен како смо их избаце програмски користи нешто што се зове АПИ или програмски интерфејс апликације, из Гоогле-а који нам омогућава да конвертујете енглеском овим другим језицима. Али захваљујући предивном духу неких стотину волонтера плус, рандом људи на Интернету који су љубазно понудили да се укључе У овом пројекту, постепено ће бити побољшање квалитета тих превода тако што људи исправи грешке које су наши компјутери направили. 

Тако испада да смо још неколико ученика појавили у понедељак него што смо првобитно очекивало. У ствари, сада има 100.000 људи ЦС50к следеће заједно код куће. Дакле, схватите да смо сви део ове Конститутивна класе израде овог курса у рачунарству образовања уопште, шире доступним. А реалност је сада, са неким од ових масивних онлајн курсева, сви они почињу са овим веома високим бројевима, као што изгледа да смо овде урадили. Али циљ, на крају крајева, за ЦС50к је заиста да се што више људи до циља могуће. По дизајну, ЦС50к ће бити понуђен у протекле понедељка па све до 15. априла 2013, тако да људи који имају другде школских обавеза, рад, породицу, други сукоби и слично, имају мало већу флексибилност са којима се зароне у овом курсу, што довољно је рећи, је прилично амбициозно ради ако само током само три месеца током уобичајеног семестру. Али ови студенти ће бити решавање истог проблема сетове, приказивање истог садржаја, имају приступ истим шорцеве и слично. Дакле, схватите да смо сви стварно у овоме заједно. А један од крајњих циљева ЦС50к није само да се што многи људи до циља и да им ту новостечену разумевање рачунарске науке и програмирање, али и да их имају ову заједничку искуство. Једна од дефинисања карактеристика 50 на кампусу, надамо се, је ова врста комуналног искуства, за боље или на горе, понекад, али има ови људи да се окрену лево и десно, и канцеларијски сати и хацкатхон и фер. То је мало теже да се то уради у лице са људима на мрежи, али ЦС50к ће се завршити у априлу са првом икада ЦС50 Сајма која ће бити онлајн адаптације наше идеје сајма где ће ове хиљаде студената сви бити позвани да поднесу 1 - да 2-минута видео, било Сцреенцаст њиховог коначног пројекта или видео њих машући здраво и говори о свом пројекту и демоинг га, слично својим претходницима урадили овде на кампусу на сајму, тако да је до краја семестар, нада је да има глобалну изложбу коначних пројеката ЦС50к ученика, баш као што вас чека ову децембра овде на кампусу. Тако више о томе у наредним месецима. 

Са 100.000 ученика, међутим, долази потребу за још неколико цас. С обзиром да ви горући траг овде и узимање ЦС50 неколико недеља унапред ослобађања овог материјала да о народу на ЕДКС, схвате да бисмо волели да се укључе што више наших студената је могуће у овој иницијативи, како током семестра, као и ове зиме и то долази пролеће. Дакле, ако желите да се укључе у ЦС50к, посебно придружио у на ЦС50к Дискутујте је ЕДКС верзија ЦС50 расправљати, што многи од вас су користили у кампусу, онлине билтен боард, урадите главу на тај УРЛ, јавите нам ко си, зато што бих волео да се изгради подједнако тим студената и особља и факултета у кампусу, који су једноставно играју заједно и помаже. А када виде једно питање који је упознат са њима, чујете студента извештај неку грешку негде тамо у некој земљи на Интернету, и да прстење звоно јер сте превише имао тај исти проблем у д-сали пре извесног времена, надамо се онда можете придружити се и деле своје искуство. Зато вас молим да учествују, ако желите. 

Цомпутер Сциенце курсеви на Харварду имају мало традиције, ЦС50 међу њима, има неке одеће, одећу, да можете поносно носити на крају семестар, рекавши сасвим поносно да сте завршили ЦС50 и узео ЦС50 и слично, и увек се трудимо да укључи студенте у овом процесу колико год је то могуће, чиме ћемо позвати, око овог времена семестра, студенти да поднесу дизајна користите Пхотосхоп, или шта год алат избора желите да користите ако сте дизајнер, да поднесу дизајна за мајице и дуксеви и сунцобрани и мало банданас за псе сада имамо и слично. И све је онда - Победници сваке године се затим излаже на сајту наравно на адреси сторе.цс50.нет. Све се продаје по цени коштања тамо, али сајт само себе ради и омогућава људима да бирају боје и дизајна које им се допадају. Па сам мислио да смо само бих подијелити неке од пројеката прошлогодишњих који су били на сајту, поред ове овде, што је годишња традиција. "Сваки дан сам Сец Фаултн" је био један од поднесака прошле године, који је још увек доступан за ту полазника. Имали смо једно ", ЦС50, основана 1989." Један од наших Бовденс, Роб је био веома популаран прошле године. "Тим Боуден" рођен, овај дизајн је достављен, међу продавцима. Као што је овај овде. Многи људи су имали "Бовден грозница" према продаје трупаца. Схватите да је то сада могао бити ваш дизајн тамо, горе на Интернету. Више детаља о овоме у следећем проблему поставља доћи. 

Још једно средство: да сте имали неке изложености и надам се сада неке руке на искуство са ГДБ, што је, наравно, дебагер и омогућава вам да манипулише ваш програм на прилично ниском нивоу, ради оно што врсте ствари? Шта ГДБ да радите? Да? Дај ми нешто. [Студентски одговор, неразумљив] Добро. Корак у функцију, тако да не само да откуцате покрене и имају ударац програма кроз целини, штампање ствари на стандардни излаз. Уместо тога, можете да прођете кроз га линију по линију, било куцање следећи ићи линију по линију по линију или корак да зароне у функцију, обично онај који си написао. Шта још ГДБ да радите? Да? [Студентски одговор, неразумљив] Штампање променљивих. Дакле, ако желите да урадите мало интроспекцију унутар вашег програма без прибегавања писању принтф изјаве свуда, само да одштампате променљиву или приказати променљиву. Шта још можете да урадите са отклањање грешака као ГДБ? [Студентски одговор, неразумљив] Управо тако. Можете да подесите тачке прекида, ви можете рећи извршење пауза на главном функцијом или фоо функције. Можете рећи извршење пауза на линији 123. А тачке прекида су заиста моћна техника јер ако имате општи осећај где је твој проблем Вероватно је, не морате да губите време стајања кроз целину програма. Ви у суштини могу да скачу тамо, а онда почните да куцате - корачање кроз њега са корак или следећи или слично. Али цака са нечим као ГДБ је да помаже, људски, пронађу своје проблеме и пронађе своје грешке. То не значи нужно да им је много за вас. 

Зато смо увели неки дан стиле50, што је кратак командне линије алат који покушава да стилизовати код мало више од тебе чисто, људско, можда има урађено. Али то, такође, је заиста само естетски ствар. Али испоставило се да је ово друго средство зове Валгринд да је мало више тајанствени за коришћење. Његов излаз је атроциоусли криптичан на први поглед. Али то чудесно корисно, поготово сада када смо на делу мандата где сте почели да користе маллоц и динамичан додела меморије. Ствари могу да иду стварно у реду брзо. Јер, ако сте заборавили да ослободите меморију, или сте дереференце неке НУЛЛ показивач, или сте неки дереференце смеће показивач, што је обично симптом који су резултати? Сец грешку. А ти се овај основни фајл неког броја килобајта или мегабајта који представља стање меморије програма када се срушио, али ваш програм на крају сег грешке, сегментирања грешку, што значи да се нешто лоше догодило скоро увек повезани до меморије везане грешке које сте негде направили. Дакле Валгринд помаже вам овакве ствари. То је алат који наиђете, као ГДБ, након што сте саставили свој програм, али уместо да покрене свој програм директно, можете покренути Валгринд и прође на њега свој програм, баш као и ви са ГДБ. Сада, коришћење, да би добили најбољу врсту производње, је мало дуго, па тамо на врху стране екрана видећете Валгринд-В. "-В" скоро универзално значи вербосе када користите програме на Линук рачунару. Значи испљунути више података него што би по дефаулту. "- Цурења провери = пуна." Ово је само кажем чек за свим могућим меморијских цурења, Грешке које би сам направио. Ово је, такође, заједнички парадигма са Линук програма. Генерално, ако имате командне линије аргумент да је "прекидач", који је требало да се промени понашање програма, и то је једно слово, то-в, али ако је то укључен, само дизајном програмеру је пуну реч или низ речи, командна линија аргумент почиње са -. Ово су само људске конвенције, али ћете их видети све. И онда, коначно, "а.оут" је произвољан назив за програм у овом конкретном примеру. А ево неких представника излаз. 

Пре него што погледамо шта то може да значи, да одем до једног фрагмента кода овамо. И дозволите ми да померим ово је начин, ускоро, и хајде да погледамо мемори.ц, што је овај кратак пример овде. Дакле, у овом програму, дозволите ми да увећате о функцијама и питања. Имамо функцију главног која позива функцију, Ф, и шта онда ф наставите да радите, у нешто техничком енглеском? Шта ф наставити да радим? Како би било да ћу почети са линије 20, а звезде локација није битна, али ја ћу само бити у складу овде са последњег предавања. Шта је линија 20 до за нас? На левој страни. Ми ћемо га разбити даље. Инт * к: шта то радиш? Ок. То је декларисање показивач, а сада будимо још технички. Шта то значи, врло конкретно, да прогласи показивач? Неко други? Да? [Студентски одговор, неразумљив] предалеко. Дакле, ви читате на десној страни знака једнакости. Хајде да се фокусирамо само на лево, само на инт * к. То значи "прогласи" показивач, али сада хајде да зароните у дубље тој дефиницији. Шта то конкретно, технички значи? Да? [Студентски одговор, неразумљив] Ок. То је припрема да сачувате адресу у меморији. Добро. И хајде да и даље овај један корак, то је проглашење променљиву к, то је 32 бита. И знам да је 32 бита јер -? То није зато што је инт, јер је показивач у овом случају. Случајност да је то један и исти са инт, али чињеница да је звезда тамо значи да је показивач и апарата, као и са многим рачунарима, али не све, показивачи су 32 бита. На више модерног хардвера као што најновијим Мац, најновији рачунари, можда имате 64-битне показиваче, али у апарату, ове ствари су 32 бита. Тако ћемо стандардизовати на то. Конкретније, прича гласи: Ми "прогласи" показивач, шта то значи? Ми припремамо за складиштење меморијску адресу. Шта то значи? Ми стварамо променљиву зове к који заузима 32 бита који ће ускоро складиште адресу цео број. И то је вероватно око што прецизнији можемо добити. Добро је напредовање да поједноставе свет и само да кажем прогласи показивач зове к. Објавите показивач, али схвати шта се заправо дешава чак у само тих неколико ликова. 

Дакле, ово је један скоро мало лакше, иако је више израз. Па шта је ово радите, то је сада истакнута: "маллоц (10 * сизеоф (инт));" Да? [Студентски одговор, неразумљив] Добро. И ја ћу га одвести тамо. То је доделом комад меморије за десет целих бројева. А сада хајде да зароните у нешто дубље, то је издвајање комад меморије за десет бројева. Шта се онда враћа маллоц? Адреса тог комад, или, још конкретније, адресу првог бајта тог комад. Како онда сам, програмер, да знају где да комад меморијских заврши? Знам да је то заразне. Маллоц, по дефиницији, ће вам дати гранични комад меморије. Нема празнине у њој. Имате приступ сваком бајту у том скупином, бацк то бацк то бацк, али како ја да знам где је крај овог комад меморије? Када користите маллоц? [Студентски одговор, неразумљив] Добро. Ти не. Мораш да се сетим. Морам да се сетим да сам користио вредност 10, а ја не знам ни изгледа да су то урадили овде. Али терет је у потпуности на мене. Стрлен, који смо постали мало ослања на за гудаче, ради само због овог конвенцији има \ 0 или ова посебна нул карактер, НУЛ, на крају стринга. То не важи само за произвољне делове меморије. То је до вас. Дакле линије 20, онда издваја комад меморије који може да складишти десет бројеве, и смешта адресу првог бајта тог комад меморије у променљивом зове к. Ерго, што је показивач. Дакле линији 21, на жалост, била грешка. Али прво, шта се ради? Он каже продавницу на локацији 10, 0 индексиране, на комад меморије зове к вредност 0. 

Дакле, приметите пар ствари се дешава. Иако је к показивач, сећам од пре пар недеља да још увек можете да користите низ стилу нотацију заграда. Јер то је у ствари кратак руке нотација за више гробни-изгледа показивача аритметике. где би нешто овако: Узмите к адресе, померите 10 места изнад, онда иду тамо да шта год адреса се чува на тој локацији. Али искрено, ово је само ужасна да чита и да се пријатно. Дакле, свет обично користи угласте заграде само зато што је много више људског лак за читање. Али то је оно што се заиста дешава испод хаубе; к адреса, а не низ, по себи. Дакле, ово је чување 0 на локацији 10 у к. Зашто је то лоше? Да? [Студентски одговор, неразумљив] Управо тако. Ми само издвојила десет Интс, али ми рачунамо од 0 када програмирања у Ц, тако да имате приступ 0 1 2 3 4 5 6 7 8 9, али не 10 година. Дакле, ни програм ће сегменту кривицом или није. Али ми заиста не знам, то је нека врста нондетерминистиц понашања. То стварно зависи од тога да ли ћемо имати среће. Ако се испостави да је оперативни систем не смета ако користим тај додатни бајт, иако га није дао мени, мој програм можда неће срушити. То је сирово, то је луд, али можда нећете видети тај симптом, или можда видети само једном у неко време. Али реалност је да је буг је, у ствари, тамо. И то је заиста проблематично ако сте написали програм који желите да буде исправна, да ли сте продали програм који људи користе да сваки једном у неко време пада јер, наравно, то није добро. У ствари, ако имате Андроид телефон или иПхоне а ви преузмете апликације ових дана, ако сте икада имали апликација само отказ, све изненада нестане, то је скоро увек последица неких меморија у вези питања, при чему програмер забрљали и дереференцед показивач да он или она не би требало да имају, а резултат иОС или Андроид је само да убије потпуно програм уместо ризика недефинисаног понашања или неку безбедности компромиса. 

Постоји још једна грешка у овом програму поред овог једног. Шта друго сам забрљао у овом програму? Не сам практиковао оно што сам проповедао. Да? [Студентски одговор, неразумљив] Добро. Нисам ослободио меморију. Дакле, правило сада мора да буде било што позовете маллоц, морате позвати бесплатан када завршите коришћење тог меморије. Сада, када бих желео да ослободи ову меморију? Вероватно, претпостављајући ово прва линија је тачно, ја бих желео да то урадим овде. Јер ја не могу, на пример, то овде доле. Зашто? Само од обима. Дакле, иако говоримо о показивача, ово је недеља 2 или 3 питање, где је к само у обиму унутар заграда, где је проглашен то. Тако да дефинитивно не може да га ослободи тамо. Моја једина шанса да се ослободимо је отприлике после линији 21. То је прилично једноставан програм, било је прилично лако када сте некако увијено предомислите око чега се програм ради, где су грешке биле. А чак и ако то не види на први поглед, надамо се да је то мало очигледно сада да ове грешке су прилично лако решити лако и направио. Али када програм дужи од 12 линија, то је 50 линија дуга је 100 линија дуга, шетњу кроз кода линију по линију, мислећи кроз њу, логично, је могуће, али није нарочито забавно да радим, стално у потрази за бубама, а такође је тешко да уради, и зато алата као Валгринд постоји. Пусти ме само напред и урадите ово: пусти ме да отворим прозор терминала, и пусти ме само не покрене памћење, јер памћење може да буде у реду. Идем среће. Одлазак на том додатном бајт на крају низа не изгледа да буде превише проблематично. Али дозволите ми да, ипак, не чек разум, што само значи да провери да ли је или није то је заправо тачно. 

Дакле, хајде да урадимо Валгринд-В - цурења провери = пун, а онда име програма у овом случају је меморија, није а.оут. Зато ме пусти да идем напред и урадите то. Хит Ентер. Драги Боже. Ово је његов излаз, а то је оно што сам алудирао раније. Али, ако научите да читате све глупости овде, већина ово је само дијагностичка излаз који није толико занимљиво. Шта ваш очи заиста жели да буде у потрази за је било помена о грешци или неважеће. Речи које сугеришу проблеме. И заиста, да видимо шта се дешава у реду овде. Имам резиме некакве ", који је у употреби на излазу:. 40 бајтова у 1 блокова" Нисам баш сигуран шта блок је још, али 40 бајтова стварно осећа као да сам могао да схватим где се то долази. 40 бајтова. Зашто су 40 бајта у употреби на излазу? И још прецизније, ако помицати овде доле, Зато сам дефинитивно изгубио 40 бајтова? Да? [Студентски одговор, неразумљив] Савршено. Да, баш тако. Било је десет целих бројева, и сваки од њих је величина 4, или 32 бита, па сам изгубио управо 40 бајтова, јер, као што сте предложили, нисам звао бесплатно. То је један од буба, а сада хајде да погледамо доле мало даље и видети поред тога, "Неисправан писање величине 4". Ста је ово? Ова адреса је изразио шта базу нотацију, очигледно? Ово је хексадецимални, и сваки пут када видите број који почиње са 0к, то значи хексадецимално, што смо и урадили давне, мислим делу псет 0 за питања, што је само да урадите вежбу загревања, претварање децимална да хек у бинарни и тако даље. Хексадецимални, само људском конвенцијом, обично се користи за представљање показиваче или, уопште, говори. То је само конвенција, јер је мало лакше за читање, то је мало компактнији од нечега као децимални, и бинарна је бескорисна за већину људи да користе. И шта сад ово значи? Па, изгледа као да је инвалид врите величине 4 на линији 21 од мемори.ц. Дакле, хајде да се вратимо на линији 21, и заиста, овде је то неважећи писања. Дакле Валгринд неће у потпуности држи за руку и реци ми шта поправити је, али се детектује да радим неважећи упис. Ја додиривање 4 бајта да не би требало да буде, и очигледно да је због тога, као што сте истакли, ја радим [10] уместо [9] максимално или [0] или нешто између. Са валгринд, схватити сваки пут ви сада пишете програм који користи показиваче и користи меморију, а маллоц тачније, дефинитивно ући у навику ради то дуго али врло лако копирали и налепили команду Валгринд да видим да ли има неких грешака у тамо. И то ће бити огромна сваки пут када видите излаз, али само рашчланити кроз визуелно све излаза и видети ако видите помиње грешака или упозорења или неважећи или изгубљена. Било која реч која звучи као ти зезнуо негде. Дакле, схватите да је нова алатка у вашем алата. 

Сада у понедељак, имали смо гомилу људи долазе овде и представља појам повезану листу. И увели смо повезани листу као решење за оно проблем? Да? [Студентски одговор, неразумљив] Добро. Низови не могу имати меморију додати на њих. Ако доделити низ величине 10, то је све што ћеш добити. Можете позвати функцију као реаллоц ако сте у почетку звао маллоц, и да покуша да расте низ ако постоји простор крајем њега да нико други не користи, а ако не постоји, то је само ће вам наћи већи комад негде другде. Али онда ће ископирати све оне бајтова у новом низу. Ово звучи као веома коректан решење. Зашто је ово непривлачан? Мислим ради, људи су решили овај проблем. Зашто морамо да га решимо у понедељак са повезаним листама? Да? [Студентски одговор, неразумљив] То може потрајати дуго. У ствари, сваки пут кад зовеш маллоц или реаллоц или цаллоц, што је још један човек, сваки пут када, програм је у разговору са оперативним системом, Ви имају тенденцију да успори програм доле. А ако радиш овакве ствари у петљи, ти стварно успорава ствари доле. Нећеш приметити ово најједноставније "Хелло Ворлд" програме типа, али у много већим програмима, тражећи оперативни систем поново и поново за меморију или давање га поново и поново тежи да не буде добра ствар. Плус, то је само врста интелектуално - то је потпуно губљење времена. Зашто издвојити више и више меморије, ризик копирања све у новом низу, ако имате неку алтернативу која вам омогућава да издвоји само онолико меморије као што сте заиста потребно? Дакле, ту је плусева и минусева у овде. Један од плусева сада је да имамо динамику. Није битно где су комади меморије су да су слободни, Ја само могу некако да креирају ове мрвице хлеба преко показивача заједно обесити цео повезане листе. Али ја плати барем једну цену. 

Оно што морам да одустанем у стицању повезаних листа? Да? [Студентски одговор, неразумљив] Добро. Треба више меморије. Сада ми је потребан простор за ове тројке, и у случају овог супер једноставног повезану листу који се само покушава да складишти бројеве, који су 4 бајта, чувамо рекавши добро, показивач је 4 бајта, тако да сада буквално сам удвостручио количина меморије је потребно само да сачувате ову листу. Али опет, ово је константа компромис за компјутерске науке између времена и простора и развој, труда и других ресурса. Шта је још мана коришћења повезану листу? Да? [Студентски одговор, неразумљив] Добро. Није тако лако да приступите. Ми више не могу да искористе Недеља 0 принципе као завади па владај. И још конкретније, бинарни претрагу. Јер иако ми људи могу грубо видимо где средином ове листе је, рачунар зна само да је ово повезано списак почиње на адреси зове први. И то је 0к123 или нешто слично томе. А једини начин на који програм може да пронађе средњи елемент је да се заправо тражи цео списак. Па чак и тада, буквално мора да претражите целу листу, јер чак и када достигне средњи елемент следећи показиваче, ти, програм, немају појма колико је ова листа је, потенцијално, док си ударио крај ње, и како ти знаш програмски да си на крају повезане листе? Постоји посебна НУЛЛ показивач, па опет, конвенција. Уместо да користите овај показивач, дефинитивно не желим да то буде нека смеће вредност указујући негде фазу, а ми желимо да то буде рука доле, НУЛЛ, тако да имамо тај терминус у овој структури података, тако да знамо где се завршава. 

Шта ако желимо да манипулишемо ово? Урадили смо већи део овог визуелно, као и са људима, али шта ако желимо да урадимо убацивање? Дакле, првобитна листа била 9, 17, 20, 22, 29, 34. Шта ако смо тада хтели да маллоц простор за број 55, чвор за њега, и онда желимо да убаците 55 у листу баш као што смо урадили у понедељак? Како да радимо ово? Па, Анита је пришао и она је у суштини ходао листу. Она је почела у првом елементу, онда следећи, следећи, следећи, следећи, следећи. Коначно погодио леви скроз доле и схватио ох, ово је НУЛЛ. Па шта показивач манипулација треба да се уради? Особа која је на крају, број 34, потребна му је лева рука подигнута да укаже на 55, 55 потребна њихова леву руку указује на доле да буде нови НУЛЛ терминатор. Готово. Прилично лако да убаците 55 у сортиране листе. И како би то могло изгледати? 

Дозволите ми да иде напред и отворити овде неки пример кода. Ја ћу отворити гедит, и пусти ме да отворим прва два датотека. Један је лист1.х, и дозволите ми да подсетим да је ово комад кода да се користи за представљање чвор. Чвор има и инт н зове и зове показивач нект то само указује на следећу ствар на листи. То је сада у датотеци х.. Зашто? Ту је ова конвенција, а нисмо искористили ово огроман сами износ, али особа која је написала принтф и друге функције дао као поклон на свету свих тих функција писањем фајл под називом стдио.х. А онда ту је стринг.х, а онда је мап.х, а ту је и сва ова х фајлови да сте можда видели или користили за време трајања писменог од стране других људи. Типично за оне х фајлови су само ствари као типедефс. или изјава прилагођених типовима или декларације константи. Ви не стави имплементације функције "у заглављу датотеке. Ставиш, уместо тога, само своје прототипове. Ставиш ствари које желите да поделите са светом шта им је потребно како да састави свој код. Дакле, само да уђу у ову навику, одлучили смо да урадимо исто. Нема много у лист1.х, али смо ставили нешто што може бити од интереса за људе у свету који желе да користе наше повезану имплементацију листе. Сада, у лист1.ц, нећу проћи кроз целу ову ствар јер је мало дужи, овај програм, али будимо реални то покренути брзо у промпту. Дозволите ми да састави Лист1, пусти ме онда покренути Лист1, а оно што ћете видети је ми смо симулирану једноставан програм мало овде то ће ми дозволити да додате и уклоните бројеве на листи. Зато ме пусти да иде напред и тип 3 за 3 ставком. Желим да убаците број - хајде да урадимо први број, који је био 9, и сада сам рекла листа је сада 9. Пусти ме само напред и урадите још једну уметање, па сам ударио менија опцију 3. Који број желим да убаците? 17. Ентер. А ја ћу учинити само још један. Дозволите ми да убаците број 22. Дакле, имамо почетке повезаног списку који смо имали у виду пројекције пре тренутак. Како је ово убацивање заправо дешава? Заиста, 22 је сада на крају листе. Дакле, прича нам рекли на бини у понедељак и рецаппед сад мора стварно да се дешава у коду. Хајде да погледамо. Дозволите ми да се померите надоле у ​​овом фајлу. Ми ћемо загладити неке од функција, али ћемо ићи на, рецимо, убаците функција. 

Хајде да видимо како иде о убацивању новог чвора у овом повезане листе. Где је списак објавио? Па, хајде да помицати скроз горе на врху, и приметио да мој повезана листа је суштински проглашен као један показивач која је првобитно НУЛЛ. Па ја користим ту глобалну променљиву, која у принципу смо проповедао против јер чини ваш код мало наопако да се одржи, то је некако лењо, обично, али није лењ и није у реду и није лоше ако је сврха вашег програма у животу је да симулира један повезану листу. Што је управо оно што ми радимо. Дакле, уместо да прогласи ово главни и онда морају да га усвоји до сваке функције смо написали у овом програму, ми смо уместо схватити ох, хајде само да се глобална јер је цела сврха овог програма је да се покаже једну и само једну повезану листу. Тако да се осећа добро. Овде су моји прототипови, и нећемо ићи кроз све ово, али сам написао брисање функцију, а наћи функцију, један инсерт функцију, и Траверсе функцију. Али хајде да се вратимо доле на Инсерт Фунцтион и видите како овај ради овде. Убаци је на линији - идемо. Инсерт. Тако да не предузима никакве аргументе, јер ћемо питати корисник унутар ове функције за број желе да убаците. Али прво, морамо припремити да им дају мало простора. То је нека врста копије и пасте са друге пример. У том случају, били смо додељивања инт, овај пут смо доделом чвор. Ја стварно не сећам колико бајтова чвор је, али то је у реду. Сизеоф могу да схватим да се за мене. И зашто сам проверу за НУЛЛ у складу 120? Шта може да крене наопако, у складу 119? Да? [Студентски одговор, неразумљив] Добро. Само би могао да буде случај да сам тражио превише меморије или нешто није у реду, а оперативни систем нема довољно бајта да ми дају, тако да сигнализира колико враћањем НУЛЛ, и ако ја не проверава да и ја само слепо наставите да користите адресу вратио, то би могао да буде НУЛЛ. То може бити неки непознати вредност; није добра ствар ако не - заправо неће бити непозната вредност. То може бити НУЛЛ, тако да не желим злоупотреби га и ризиковати дереференцинг га. Ако се то деси, само се врати и ми ћемо се претварати као да нисам добио назад ниједан сећање на све. 

Иначе, ја кажем корисник дајте ми број за уметање, зовем наш стари пријатељ ГетИнт, и онда је ово нова синтакса смо увели у понедељак. 'Невптр-> н' значи узети адресу коју сте добили од маллоц што представља први бајт новог чвора објекта, и онда идите на поље под називом Н. Мало тривиа Питање: Ово је еквивалент ономе што више најстрозије линију кода? Како другачије да сам написао ово? Желите да се убод? [Студентски одговор, неразумљив] Добро. Користећи Н., Али то није баш тако једноставно као ово. Шта ми прво треба да урадим? [Студентски одговор, неразумљив] Добро. Морам да урадим * невптр.н. Дакле, ово говори нови показивач очигледно адреса. Зашто? Пошто је вратио маллоц. Тхе * рекавши невптр "иди тамо" и онда кад си тамо, онда можете да користите више познати, Н. али ово само изгледа мало ружно, посебно ако су ми људи ће извући показиваче са стрелицама све време, свет има стандардизовани на овој нотацији стрелице, који ради потпуно исту ствар. Дакле, ви само користите -> нотацију када је ствар на лево је показивач. У супротном, ако је стварни струцт, користите Н.. А онда ово: Зашто покрене невптр-> поред НУЛЛ? Ми не желимо висећи леву руку на крају фазе. Желимо да показује право доле, што значи крај ове листе би потенцијално могли бити у том чвору, тако да је боље да проверите да ли је НУЛЛ. И, уопште, иницијализација променљивих или ваше податке чланове и Структуре нешто је само добра пракса. Само пустити смеће постоји и наставиће да постоји генерално вас добија у невољи ако сте заборавили да урадите нешто касније. 

Ево неколико случајева. То је, опет, уметак функција, и прва ствар коју сам проверите је да ако је променљива зове први, да је глобална променљива је НУЛЛ, то значи да не постоји повезана листа. Нисмо ставили никакве бројеве, тако да је тривијално да убаците овај тренутни број на листи, јер је то само припада на почетку листе. Дакле, то је било када Анита је само стајао овде сам, правећи нико други није овде на бини док се додељује чвор, онда би могла да подигне своју руку по први пут, ако сви други дошао на бини после ње у понедељак. Ево, ово је мало провера у којој ја морам да кажем да ли новог чвора вредност н је <вредност н у садашњем првом чвору, то значи да је повезана листа која је почела. Постоји најмање један чвор у листи, али овај нови момак припада пре него што је тако, морамо да се крећу ствари. Другим речима, ако је листа почела са само, рецимо, само број 17, то је - у ствари, можемо да урадимо ово јасније. Ако почнемо нашу причу са показивачем овде зове први, и првобитно је НУЛЛ, а ми убаците број 9, број 9 јасно припада на почетку листе. Дакле, хајде да се претварамо да смо само маллоцед адресу или број 9 и ставио га овде. Ако прво је 9 подразумевано, први сценарио смо разговарали само значи овде пусти поенту овог момка, оставите ово као НУЛЛ, сада имамо број 9. Следећи број желимо да убаците је 17. 17 припада овде, тако да ћемо морати да урадите неке логичке корак и кроз ово. Па хајде, уместо да, пре него што то урадимо, хајде да се претварамо да смо хтели да убаците број 8. 

Дакле, само ради практичности, ја ћу овде нацртати. Али запамтите, маллоц да га стави највише било где. Али ради цртежу, ја ћу га ставити овде. Зато се претварам Управо сам издвојила чвор за број 8, то је НУЛЛ по дефаулту. Шта сада треба да се деси? Пар ствари. Направили смо ову грешку на бини у понедељак где смо ажурира показивач овако, онда је то урадио, а онда смо тврдили - ми смо сирочад све друго на сцени. Зато што сте Зар не - редослед операција овде је важно, јер сада смо изгубили тај чвор 9 То је само нека врста лебди у простору. Дакле, то није био прави приступ у понедељак. Ми прво морамо да урадимо нешто друго. Стање на свету изгледа овако. У почетку, 8 је додељен. Шта ће бити бољи начин убацивања 8? Уместо ажурирања прво од показивача, само ажурира уместо ово овде. Зато нам је потребна линија кода који се дешава да се овај НУЛЛ карактер у стварном показивача која се показује на чвор 9, а онда са сигурношћу можемо променити прво да укажем на овог момка овде. Сада имамо листу, повезана листа, два елемента. И шта ово заправо изгледају као овде? Ако погледамо код, приметићете да сам урадио управо то. Ја сам рекао невптр, иу овој причи, невптр је показујући на овог момка. 

Дакле, дозволите ми да скренем још једну ствар, а ја сам требао оставио мало више простора за то. Дакле опрости малецно цртеж. Овај момак се зове невптр. То је променљива смо прогласили неколико редова раније, у линији - изнад 25 година. И то показује да 8. Дакле, када кажем невптр-> следеци, то значи ићи на струцт а која се указује и невптр, тако да смо овде, иди тамо. Онда стрелица говори се следеће поље, а затим је рекао: = стави чему је вредност? Вредност која је била у првом, каква је вредност била прва? Прво је показујући на овај чвор, па то значи да ово треба да се одмах укаже на овом чвору. Другим речима, оно што изгледа иако је смешан неред са мојим рукописом, шта је једноставна идеја само креће око ове стрелице преводи на коду са само том једном броду. Чувајте оно што је у први у следећем пољу, а затим ажурирате оно прво заправо јесте. Идемо напред и брзо напред кроз неке од овога, и погледајте само на овом репа уметања за сада. Претпоставимо да дођем до тачке где сам наћи да ће следећи поље неког чвора је НУЛЛ. И у овом тренутку у причи, детаљ који сам прећуткивања је да сам увео још један показивач овде у складу 142, претходник показивача. У суштини, у овом тренутку у причи, када листа добија дуго, Некако треба да га шетам са два прста, јер ако одем предалеко, Сећам се једним дужине листи, не можете ићи уназад. Дакле, ова идеја предптр је моја лева прст, а невптр - не невптр. Други показивач да је овде је мој други прст, а ја сам само мало ходања листу. Зато што постоји. Али, хајде да разматрамо само један од једноставнијих случајева овде. Ако идуће поље које је показивач НУЛЛ, шта је логично импликација? Ако сте попречно ову листу, а ви погодите НУЛЛ показивач? Ви сте на крају листе, па код онда додати овај један додатни елемент је врста интуитивног ће тај чвор чији нект показивач НУЛЛ тако да је ово тренутно НУЛЛ, и промените је, међутим, да буде адреса новог чвора. Дакле, само смо цртања у коду на стрелицу која се нацртао на сцени подизањем левом руком нечију. 

А случај да ћу махати моје руке на за сада, Управо зато мислим да је лако изгубити када то радимо у овој врсти средине, проверава за убацивање у средини листи је. Али само интуитивно, шта треба да се деси, ако желите да схватите где неки број припада у средини је што не морам да ходам са више од једног прста, више од једног показивач, схватим где припада по проверавању је елемент <тренутна, > Тренутни један, и када вам је то место, онда морате да урадите ову врсту љуске игри у којој се померите тројке око веома пажљиво. И тај одговор, ако желите да се схвата кроз ово код куће, на сопствени, своди само на ове две линије кода, али је редослед тих линија је супер важно. Јер ако падне нечију руку и подигне неко други је у погрешним редоследом, опет, могао би завршити орпханинг листу. Да резимирамо више концептуално, инсталирање на репу је релативно једноставно. Уметање на глави је релативно једноставан, али морате да ажурирате додатни показивач овај пут да постигнемо број 5 у листу овде, и онда убацивање у средини подразумева још више труда, веома пажљиво убаците број 20 у исправном месту, која је између 17 и 22. Дакле, морате да урадите нешто да нови чвор 20 тачку на 22, а онда, који чвора показивач треба да буде ажуриран последњи пут? То је 17, да се заиста га убаците. Па опет, ја ћу одложити стварни код за ту реализацију. 

На први поглед, то је мало претерано, али то је заиста само бесконачна петља који је петље, петље, петље, петље и разбијање чим притиснете НУЛЛ показивач, на којој тачки можете да урадите потребну уметање. То је, дакле, заступник повезана листа убацивање кода. То је нека врста парцеле, и то се осећа као да смо решили један проблем, али смо увели целу другу. Искрено, ми смо потрошили све ово време на великом О и Ω и трчање време, покушавајући да реши проблеме брже, и овде узимамо велики корак уназад, он осећа. А ипак, ако је циљ чување података, она се осећа као Свети грал, као што смо рекли у понедељак, да ли би заиста било за чување ствари одмах. 

У ствари, претпоставимо да смо ставили на страну повезану листу за тренутак и ми смо уместо тога увео појам табеле. И да само мислим на табели за тренутак као низа. Овај низ и овај случај овде има неких 26 елемената, 0 до 25, и претпоставимо да је потребно мало парче простора за имена: Алиса и Боб и Чарли и слично. А ти треба структуру података за чување тих имена. Па, можете да користите нешто као повезану листу а ти би могао ходати листу убацивање Алис пре Боб и Чарли после Боба и тако даље. И, у ствари, ако желите да видите код таквог као страни, Знам да је у лист2.х, радимо управо то. Нећемо ићи преко овог кода, али ово је варијанта први пример која уводи још једну струцт смо видели раније тзв студента, а онда шта је то заправо чува у повезаној листи је показивач на структуру студентског него једноставно мало цео број, н. Дакле, схвати да је код тамо да обухвата стварне везе, али ако је циљ на дохват руке заиста сада да реши проблем ефикасности, Зар не би било лепо да смо дали објекат зове Алиса, желимо да јој стави на праву локацију у структури података, се осећа као да би било стварно лепо да само стави Алице, чије име почиње са, на првом месту. И Боб, чије име почиње са Б, у другом месту. Уз низ или почнимо називајући га табелу, хеш табеле у томе, можемо да урадимо управо то. Ако смо дали такво име Алице, стринг као Алиса, где сте ставили А-л-и-ц-е? Треба нам хуеристиц. Морамо функцију да преузме неки улаз као Алиса и врати одговор, "Пут Алиса на овој локацији." И ова функција, ова црна кутија, ће бити позвани хасх функција. 

Хасх функција је нешто што траје улаз, као што је "Алиса", и враћа се вама, обично, нумерички локација у некој структури података у којој Алиса припада. У том случају, наша хеш функција треба да буде релативно једноставан. Наш хеш функција треба да кажем, ако вам се "Алице", који лик би требало да бринете о? Прво. Тако ја гледам на [0], а онда сам рекао ако [0] карактер, вратите број 0. Ако је Б, повратак 1. Ако је Ц, вратите 2, и тако даље. Све 0 индекс, као и да ће омогућити да убаците Алису и онда Боба и онда Цхарлие и тако даље у ову структуру података. Али постоји проблем. Шта ако Анита долази заједно поново? Где смо ставили Анита? Њено име, такође, почиње са словом А, и то се осећа као да смо направили још већи неред овог проблема. Ми сада имамо одмах убацивање, константно време уметања, у структури података него горе-слуцају линеарно, али шта можемо урадити са Аниту у овом случају? Које су две опције, стварно? Да? [Студентски одговор, неразумљив] Ок, тако да смо могли имати још једну димензију. То је добро. Дакле, можемо изградити ствари у 3Д као што смо причали вербално у понедељак. Могли бисмо додати још један приступ, али претпостављам да не, ја покушавам да ово једноставно. Цео циљ је да се одмах константна времена приступа, тако да је додавање превише комплексност. Које су друге опције када покушавају да убаците Анита у овој структури података? Да? [Студентски одговор, неразумљив] Добро. Тако смо могли доле померити све друго, као Чарли додире доле Боб и Алис, а затим смо ставили Анита где она заиста жели да буде. 

Наравно, сад, ту је споредни ефекат овога. Ова структура података је вероватно корисно не зато што желимо да убаците људе једном већ зато што желимо да провери да ли су они тамо касније ако желимо да одштампате сва имена у структури података. Ми ћемо да урадимо нешто са тим подацима на крају. Дакле, сада имамо какву зезнуо над Алисом, који је не где би требало да буде. Нити је Боб, нити је Чарли. Можда ово и није тако добра идеја. Али заиста, ово је једна од опција. Могли смо да смени све доле, или бога, Анита дошла касно у игри, зашто не бисмо ставили Анита не овде, не овде, не овде, хајде да јој стави мало ниже на листи. Али онда се овај проблем почне поново да пренесе. Можда ћете моћи да пронађете Алиса одмах, на основу њеног имена. И Боб одмах, и Чарли. Али онда тражити Анита, а ви видите, хмм, Алице је на путу. Па, дозволите ми да проверите доле Алисе. Боб није Анита. Чарли није Анита. Ох, има Анита. А ако наставите том возу логике скроз, шта је најгори случај покренут време проналажења или уметања Анита у овој новој структури података? То је О (н), зар не? Јер, у најгорем случају, ту је Алиса, Боб, Чарли. . . све скроз доле на некога под називом "И", тако да је само једна тачка лево. Срећом, ми немамо један под називом "З", па смо ставили Анита на самом дну. 

Нисмо баш решио тај проблем. Можда ми треба да уведу овај трећу димензију. И испоставило се да, ако не уведу ову трећу димензију, не можемо учинити савршено, али Свети Грал ће бити добијање константна времена уметање и динамичне уметања, тако да не морамо да се тешко код низ величине 26. Можемо убацити онолико имена као што смо желели, али хајде да овде 5-минута паузе и онда то исправно. У реду. Поставио сам причу горе прилично вештачки тамо бирајући Алис и онда Боба и онда Чарли и затим Анита, чије име је очигледно да ће се сударају са Алице. Али питање које смо завршили у понедељак је само колико је вероватно да би добили ове врсте судара? Другим речима, ако почнемо да користимо овај табеларни структуру, што је заиста само низ, у овом случају од 26 локација, шта ако су наши улази уместо равномерно распоређени? То није вештачки Алиса и Боб и Чарли и Давид и тако даље по азбучном реду, је равномерно дистрибуира преко преко З. 

Можда ћемо само посрећи, па нећемо имати две-а или два Б је са веома високом вероватноћом, али као што је неко истакао, ако генерализује овај проблем, а не од 0 до 25 али, рецимо, 0 до 364 или 65, често број дана у типичној години, и поставио питање: "Шта је вероватноћа да нас двојица у овој соби има исту рођендан?" Ставите га на други начин, у чему је вероватноћа да нас двојица имамо име почиње са? Овакав питању је исти, али ова адреса простор, ово претраживање простор је већи у случају рођендана, јер имамо много више дана у години него слова у алфабету. Шта је вероватноћа судара? Па, можемо мислити ово схватите математику на супротан начин. Шта је вероватноћа судара не? Па, овај израз овде каже да оно што је вероватноћа ако постоји само једна особа у овој соби, да имају јединствену рођендан? То је 100%. Јер, ако постоји само једна особа у просторији, његов или њен рођендан може да буде било који од 365 дана у години. Дакле, 365/365 опција ми даје вредност 1. Дакле, вероватноћа је у питању у овом тренутку је само 1. Али ако постоји друга особа у просторији, шта је вероватноћа да је њихов рођендан другачије? Има само 364 могућих дана, игноришући преступних година, за њихов рођендан не сударају са другим особама. Дакле, 364/365. Ако треће лице долази, то је 363/365, и тако даље. Зато држимо заједно множењем ове разломке, који су све мањи и мањи, да схватим шта је вероватноћа да сви ми имамо јединствене рођендане? Али онда можемо, наравно, само узми тај одговор и преокренути га око и до 1 минус свега тога, израз на крају смо Добићете ако се сећате леђа својих математичких књига, изгледа мало овако, што је много лакше тумачити графички. А овај графички овде има на к оси број рођендане, или број људи са рођендана, а на и оси је вероватноћа меча. А шта је ово да кажем је да ако имате, рецимо, чак, хајде да изаберу нешто 22, 23. Ако постоји 22 или 23 људи у просторији, вероватноћа да су два од тих малобројних људи ће имати исти рођендан је заправо супер висока, цомбинаториалли. 50% шансе да у класи од само 22 људи, семинара, практично, 2 од тих људи ће имати исти рођендан. Зато што постоји толико много начина на које можете имати исту рођендан. Још горе, ако се осврнемо на десној страни графикона, у време имате класу са 58 ученика у њему, вероватноћа од 2 људи који имају рођендан је супер, супер висока, скоро 100%. Дакле, то је нека врста забаве чињенице о стварном животу. 

Али импликације, сада, за структуре података и складиштења информација значи да је само под претпоставком да имате леп, чист, равномјерно података и имате довољно велики да се уклопи низ гомилу ствари не значи да ћеш да се људи у јединственим локацијама. Ти ћеш имати судара. Дакле, ово појам уситњавања, како се зове, узимајући улаз као "Алиса" и масирањем га на неки начин и онда се вратим одговор као 0 или 1 или 2. Враћање неки излаз из те функције се муче ове вероватноће судара. Па како да се носимо те сударе? Па, на једном случају, можемо узети идеју да је предложени. Ми само можемо пребацити све доле, или можда, мало више једноставно, него потез и сви остали, идемо само померите Анита на дно расположивог места. Дакле, ако Алице је у 0, Боб је у 1, Чарли је у 2, само ћемо ставити Анита на локацији 3. А ово је техника у структурама података назива линеарни прескок. Јер Пуни сте тек ходање ову линију, а ти си некако сондирање расположиве места у структури података. Наравно, ово преноси у О (н). Ако структура података је заиста пуна, већ има 25 људи у њему, и онда Анита долази заједно, она завршава на оно што ће бити локација З и то је у реду. Она још увек одговара, а можемо је наћи касније. 

Али ово је била у супротности са циљем убрзања ствари. Па шта ако смо уместо тога увео ову трећу димензију? Та техника се обично назива одвојено уланчање, или имају ланце. А шта хеш табела је сада, овај табеларни структура, Ваш сто је само низ показивача. Али оно што они показивачи указују да је погодите шта? Повезана листа. Па шта ако узмемо најбоље од оба света? Ми користимо низове за првих индекса у структури података тако да можемо одмах да пређемо на [0] [1], [30] или тако даље, али тако да имамо одређену флексибилност и да може да стане Анита и Алис и Адам и било које друге име, уместо тога нека друга оса расте произвољно. И коначно, од понедељка, имају ту способност изражајан са повезаном листом. Можемо произвољно расте структуру података. Алтернативно, можемо само да направимо велики 2-димензионални низ, али то ће бити страшно ситуација ако је један од редова у 2-димензионални низ није довољно велика за додатну особу чије име се дешава да се почне са А. Боже сачувај морамо да прерасподели велики 2-димензионалну структуру само зато што има толико људи по имену, посебно када постоји тако мало људи названи З нешто. То ће бити веома ретки структура података. Дакле, то није савршена на било који начин, али сада барем имамо могућност да одмах пронађете где Алис или Анита припада, барем у погледу вертикалне осе, и онда ми је само да одлучите где да стави Анита или Алиса у овој повезаној листи. Ако ми не бринемо о сортирању ствари, колико брзо можемо убацити Алиса у структуру као што је овај? То је константа време. Ми индекса у [0], а ако постоји ничија, Алиса одлази на почетку тог повезане листе. Али то није велика ствар. Јер, ако Анита онда долази заједно Касније одређени број корака, где се Анита припада? Па, [0]. ООП. Алице је већ у тој повезаној листи. 

Али ако ми не бринемо о сортирању ова имена, ми само да пређемо преко, Алис убаци Анита, али чак и то је константа време. Чак и ако постоји Алиса и Адам и сви ови остали А имена, то није стварно их мења физички. Зашто? Зато смо управо урадили овде са повезану листу, ко зна су ови чворови су уопште? Све што треба да урадите је да померите мрвице хлеба. Премештање стрелице около, ви не морате физички да се крећу било какве податке. Дакле, можемо убацити Анита, у том случају, одмах. Константна време. Дакле, имамо константан времена проналажење и константна времена убацивањем неког као Анита. Али некако упрошћена свет. Шта ако ћемо касније да нађемо Алице? Шта ако ћемо касније да нађемо Алице? Колико корака је да ће то трајати? [Студентски одговор, неразумљив] Управо тако. Број људи пре Алиса у повезаној листи. Дакле, то није савршена, јер је наша структура података, опет, има ту вертикалну приступ и онда има ове повезане листе вешање - заправо, хајде да не скрене га низа. Она је ове повезане листе висиле на томе да изгледа мало овако. Али проблем је ако Алиса и Адам и сви ови остали А имена завршити све више и више тамо, проналажењу би неко могао завршити узимање гомилу корака, бцаусе морате да пролазе повезану листу, што је линеарна операција. Па стварно, онда је убацивање времена коначно је О (н), где је н број елемената у листи. Подељени по, да самовољно називају м, где је м број повезаних листи да смо у овој вертикалној оси. Другим речима, ако смо заиста преузме равномерну расподелу имена, тотално нереално. Постоји очигледно још неких писама од других. 

Али ако претпоставимо за тренутак униформне расподеле, и ми смо н укупне људи, а М укупни ланаца доступни нама, онда дужина сваког од ових ланаца прилично једноставно ће бити укупно н подељен бројем ланаца. Дакле, Н / м. Али ево где можемо бити све математички паметан. м је константна, јер има фиксни број њих. Ти ћеш да прогласи своју низ на почетку, а ми нисмо преформатирање вертикалну осу. По дефиницији, то остаје фиксиран. То је само хоризонтална оса, тако да кажем, да се мења. Дакле технички, то је константа. Тако сада, убацивање време је прилично О (н). Тако да не сматрам да се много боље. Али шта је ту истина? Па, све ово време, недељама, смо говорили О (н ²). О (н), 2 к н ², - н, подељено са 2. . . ецх. То је само н ². Али сада, у овом делу семестра, можемо почети говоримо о стварном свету поново. И н / м је апсолутно брже него само н сама. Ако имате хиљаду имена, а ви их разбити на више сегмената тако да имате само десет имена у сваком од ових ланаца, апсолутно тражи десет ствари ће бити бржи од хиљаду ствари. И тако је један од предстојећих проблема сетова ће да те изазове да размишљају о томе да, иако је тачно да, асимптотски и математички, ово је још увек само линеарно, која сиса у целини, када покушавају да пронађу ствари. У стварности, то ће бити брже него што због овог делиоца. И тако опет ће бити ова траде-офф а овај сукоб између теорије и реалности, и један од дугмади ће почети окретање у овом тренутку у току семестра је више од једне стварности као што смо некако припремити за крај семстер а, као што смо увести у свет веб програмирање, где заиста, перформансе ће да рачунају, јер ваши корисници ће почињу да се осећају и ценимо лоше одлуке дизајна. 

Дакле, како идете о спровођењу повезани - хасх табелу са 31 елемената? И претходни пример је самовољно око рођендана. Ако неко има рођендан 1. јануара или 1. фебруара, ми ћемо их у овом канту. Ако је 2. јануар, фебруар 2, 2. марта, ми ћемо их у овом канту. Зато је било 31. Како објавити хеш табелу? То може бити прилично једноставан, чвор * сто је моје име произвољна за њу, [31]. То ми даје 31 тројки на чворова, и да ми дозвољава да имају 31 тројки на повезаним листама чак и ако су ти ланци су првобитно НУЛЛ. Шта хоћу да ставим ако желите да сачувате "Алиса", "Боб", "Чарли"? Па, морамо да завршимо те ствари у структури јер морамо да укажемо на Алис Боба, да укаже на Чарли, и тако даље. Не можемо само да говоримо о именима, тако да сам могао да створи нову структуру назива чвор овде. 

Шта је стварни чвор? Шта је чвор у овом новом повезаној листи? Прва ствар, зове реч је за име особе. ДУЖИНА, вероватно, односи на максималну дужину имена хуману, шта год да је, 20, 30, 40 знакова у лудим угаоним случајевима, и +1 је за шта? То је само екстра НУЛЛ карактер, \ 0. Дакле, ово је чвор завијање "нешто" у себи од, али такође изјављује показивач зове следећа тако да можемо ланац Алице Бобану са Цхарлие и тако даље. Може бити НУЛЛ, али не мора да буде. Сва питања о овим хеш табела? Да? [Студентски пита питање, неразумљиво] низ - добро питање. Зашто је ово знак реч у низу, него само цхар *? У овом донекле произвољног пример, ја нисам хтела да прибегне да маллоц за сваки од оригиналних имена. Желео сам да прогласи максималну количину меморије за стринг тако да сам могао да копирате у структури Алиса \ 0, а не морају да се баве маллоц и слободном и слично. Али ја могу да урадим ако желим да будем више свесни коришћења простора. Добро питање. Дакле, хајде да покушамо да генерализујемо далеко од тога и фокусирати се остатак данас у структурама података генерално и други проблеми које можемо решити коришћењем исте основе иако су структуре података и сами могу да се разликују у својим појединостима. 

Тако испада у компјутерске науке, стабла су веома честе. И можете мислити стабла врсте попут породичног стабла, где има неке корене, неки Матријарх или патријарх, бака или деда или раније вратити, испод које су мама и тата или разних браћа и сестре или слично. Дакле, стабла структура има чворове и има децу, обично 0 или више деце за сваки чвор. А неки од жаргону коју видите на овој слици овде је било од мале деце или унуци на ивицама који немају стрелице које произилазе из њих, То су такозвани лишће, и свако на унутрашњој је унутрашњи чвор, можете га позвати све дуж тих линија. Али ова структура је прилично уобичајено. Ова је мало произвољна. Имамо једно дете на левој страни, имамо троје деце на десној страни, двоје деце на дну лево. Тако можемо имати различите величине стабала, али ако почнемо да стандардизује ствари, и можда сећате из видео Патрика у бинарном претраге од претходна кратка Онлине, бинарни тражи не мора да се спроведе са низом или комада папира на табли. Претпоставимо да сте желели да сачувате своје бројеве у више софистицираних структура података. Ти би могао да створи дрво овако. Могли сте чвор декларисан у Ц, и да чвор може имати најмање два елемента унутар ње. Један је број који желите да сачувате, а друга је - добро, морамо још један. Други је његова деца. Дакле, овде је још једна структура података. Овај пут, чвор се дефинише као чување број н а онда два показивачи, лево и десно дете дете. А они нису произвољне. Оно што је занимљиво у вези овог дрвета? 

Шта је образац у томе смо положили ово напоље или како Патрик га изнео у свом видеу? То је врста очигледно да постоји неки сортирање дешава овде, али оно што је једноставно правило? Да? [Студентски одговор, неразумљив] Савршено. Ако погледаш у овоме, видећете мале бројеве на лево, велики бројеви са леве стране, али то је истина за сваког чвора. За сваки чвор, њена лева дете мање од њега, и његово право дете веће од њега. Шта ово значи да је сада, ако желим да тражи ову структуру података, рецимо, број 44, Морам да почне у корену, јер као и код свих ових сложенијих структура података сада, имамо само показивач на једну ствар, почетак. И у овом случају, почетак је корен. То није крај леве, то је корен ове структуре. Видим овде 55, а ја тражим 44. У ком правцу желим да идем? Па, ја желим да идем на лево, јер очигледно, десно ће бити превелика. Дакле приметити овде, ти си некако концептуално сецкања дрво на пола јер никад не спушта на десној страни. Па сад идем од 55 до 33. То је сувише мали броја. Ја тражим 44, али сада знам да ли 44 је у овом дрвету, могу очигледно иду у десно. Па опет, ја сам орезивање стабла на пола. То је прилично идентичан концептуално у телефонском именику. То је идентично ономе што смо урадили са папирима на табли, али то је више софистициран структура која омогућава нам заиста да урадимо ово завади па владај по дизајну алгоритма, и, у ствари, попречно структуру овако - Упс. Преласком структуру као што је овај, где се само "иде овако или идите на тај начин", значи сав тај код који савијеним лактовима свој ум први пут када га реализује у одељку или ходања кроз њега код куће, на бинарном претрагу, користећи рекурзија или итерације, то је бол у врату. Пронађите средњи елемент, онда сте заокруживање горе или доле. 

Има лепоту јер сада можемо да користимо рекурзија опет, али много чисто. Заиста, ако сте на броју 55 и желите да пронађете 44, иди лево у овом случају, шта онда радите? Можете покренути исти алгоритам. Можете проверити вредност чвора, онда идите лево или десно. Затим проверите вредност чвора, идите лево или десно. Ово је савршено погодна за рекурзије. Дакле, иако је у прошлости смо урадили неке прилично произвољне примере које укључују рекурзија да не треба да буде рекурзивна, са подацима стуцтурес, посебно дрвеће, то је савршена примена ове идеје узимања проблем, смањује га, а затим решавање исти тип, али мањи, програм. 

Дакле, постоји још једна структура података да можемо увести. Ово је дизајниран на први поглед изгледа криптично, али ово је невероватно. Дакле, ово је структура података зове трие, трие, који је наследио од речи преузимања, која се не изговара поново покушајте-Вал, али то је оно што свет назива ове ствари. Покушава. Т-р-и-е. То је структуру стабла неке врсте, али сваки од чворова у трие Чини се да је шта? А ово је мало заблуду, јер је то некако скраћен. Али изгледа као да сваки чвор у овом трие је заправо низ. И чак иако је аутор овог дијаграма га није приказан, У овом случају, то је трие структура података чија је сврха у животу је да сачувате речи као А-л-и-Ц-е или Б-о-Б. А начин на који се ти подаци продавнице Алиса и Боб и Чарли и Анита, и тако даље се користи низ тако да се складишти Алиса у трие, почнемо на основном чвору који личи низа, и то је било написано у најкраћем нотацији. Аутор изостављен АБЦДЕФГ јер није било имена са тим. Они су само показали М и П и Т, али у овом случају, идемо даље од Алисе и Боб и Чарли неким именима која су овде. Маквелл је заправо у овом дијаграму. Па како је урадио аутор продавницу М--к-в-е-л-ја? Он или она је почела у основном чвору, и отишао на [М], па отприлике 13, 13. место у низу. Затим одатле, ту је показивач. Показивач доводи до другог низа. Одатле аутор индексиран у тој низу на локацији А, као што је представљено тамо у горњем левом углу, и онда он или она прати тај показивач на другом низу, и отишао на показивачу на локацији Кс. Затим у следећем низа локације В, Е, Л, Л, и тако даље, и коначно, да заправо покушавају да стави слику на ово. Шта чвор изгледа у коду? Чвор у трие садржи низ показивача на више чворова. Али ту мора да постоји нека врста Боолеан вредности, бар у овој примени. Ја се десити да га зову ис_ворд. Зашто? Јер, када сте уметања Маквелл, нисте уметања ишта у овој структури података. Ниси писао М. Ти не пишеш Кс. Све што радиш је после тројке. Показивач који представља М, онда показивач који представља, онда показивач који представља Кс, онда В, Е, Л, Л, али оно што треба да уради на крају је некако иде, проверите, ја достигао ову локацију. Постојала је реч која се завршава овде у структури података. 

Дакле, шта се заиста трие испуњен и аутор је изабрао да заступа ови терминусес са малим троугловима. То само значи да је чињеница овај троугао је овде, ово Боолеан вредност истина значи да ако уназад ићи у дрвету, то значи реч по имену Максвел је у овоме. Али реч трла, на пример, није у стаблу, јер ако почнем на основном чвору овде на врху, Нема ф показивач, не о показивач, не о показивач. Фоо није име у овом речнику. Али са друге стране, туринг, Т-у-р-и-н-г. Опет, нисам складиште или у Т или Р или ја или Н или г. Али сам продавницу у овој структури података вредност правог пута овде у овом чвору - на дрвету постављањем овог боолеан вредност ис_ворд на истина. Дакле трие је врста овог веома занимљивог мета структуре, где ти ниси стварно складиштење Саме речи за ову врсту речника. Да буде јасно, ти само складиштење да или не, постоји реч која се завршава овде. 

Шта је сад импликација? Ако имате 150.000 речи у речнику да покушавате да сачувате у меморији користите нешто као повезаној листи, ћете имати 150.000 чворова у својој повезаној листи. И проналажење један од тих речи абецеди могао да О (н) време. Линеарно време. Али, у случају овде на трие, Шта је време рада у проналажењу речи? Испоставило се овде лепоту јесте да чак и ако имате 149.999 речи већ у овом речнику, спроведено са овом структуром података, Колико времена је потребно да се пронађе или убаците још једну особу у то, као Алиса, Алис? Па, то је само 5, можда 6 корака за излазне карактера. Јер пресенсе других имена у структури не добија на путу убацивања Алице. Штавише, проналажење Алице када постоји 150.000 речи у овом речнику не добија на путу проналажења Алиса уопште, јер Алице. . . . . овде, јер сам пронашао боолеан вредност. А ако не постоји боолеан истина, онда Алиса није у овом података структури речи. Другим речима, време рада у проналажењу ствари и убацивање ствари у овај нови Подаци структура трие је О од - то није н. Јер пресенсе од 150.000 људи нема никакав утицај на Алице, изгледа. Дакле, назовимо га к, где је к максимална дужина речи у енглеском језику која је обично не више од 20-нешто карактера. Дакле, к је константа. Тако је Свети Грал изгледа да смо сада може наћи је да је од трие, константном времену за уметке за лоокупс, за брисање. Пошто је број ствари које су већ у структури, који нису ни физички тамо. Опет, они само некако проверили, да или не, нема утицаја на њен будући истеклог времена. 

Али ту мора да буде улов, иначе не бисмо изгубљено много времена на свим тим другим структурама података само да коначно доћи до тајног оне која је невероватна. Па шта цену плаћамо овде постигли овај величину? Простор. Ова ствар је масивна. А разлог што аутор није га представи овде, приметићете да су све ове ствари које изгледају као низове, није извући остатак стабла, остатак од трие, јер једноставно ниси релевантан за причу. Али све ове чворова су супер широка, а сваки чвор у стаблу заузима 26 или заправо, може да буде 27 знакова, јер је у овом случају био сам, укључујући простор за апострофом тако да смо могли да апостропхизед речи. У овом случају, то су широке низови. Дакле, иако они нису пицутуред, ово заузима огромну количину меморије. Што је можда добро, еспецилли у савременом хардвер, али то је компромис. Ми смо добили мање времена проводе по више простора. Па где се све ово дешава? Па, хајде да урадимо - да видите овде. Хајде да направимо скок на овог момка овде. 

Веровали или не, колико забавно као Ц је већ неко време, смо до тачке у току семестра где је време да се преласком на стварима модерним. Ствари на вишем нивоу. И иако је за наредних неколико недеља ипак ћемо наставити да уронимо у свету тројке и управљање меморијом да тај комфор са којима онда можемо градити, Крај игре је коначно увести, иронично, не овај језик. Ми ћемо потрошити, као 10 минута говоре о ХТМЛ-у. Све је ХТМЛ је језик за означавање, и шта маркуп језик је ово серија отворених и затворених заграда заграда које кажу "да овај храбри ' "Учини овај курзивом '' чине ову центриран." Није све то интелектуално интересантно, али то је супер корисно. И сигурно је свеприсутна ових дана. Али шта је моћан о свету ХТМЛ и веб програмирање генерално, гради динамичне ствари, писање кода у језицима као што су ПХП или Питхон или Руби или Јава или Ц #. Стварно, шта год ваш језик избора је и генерисање ХТМЛ динамички. Генерисање нешто што се зове ЦСС динамично. Цасцадинг Стиле Схеетс, што је такође о естетици. И тако, иако је, данас, ако одем у неки сајт попут познатог Гоогле.цом, и ја одем, да видите, програмера, поглед извор, који можда сте урадили раније, али ће да видите извор, ова ствар изгледа прилично вероватно криптичан. Али ово је основни код који имплементира Гоогле.цом. На предњем крају. И све ово је паперјаст естетика ствари. Ово је ЦСС овде. Ако сам се померају наниже ћемо добити неки колор-кодиране ствари. Ово је ХТМЛ. Гоогле-ов код изгледа као хаос, али ако стварно отворим прозор другачији, можемо да видимо неку структуру за то. Ако отворим ово, приметите овде, то је мало више читљив. Ми ћемо видети пре дуго ту ознаку, [реч] је ознака, ХТМЛ, глава, тело, див, сценарио, текст област, спан, центрирано, див. И то је такође некако криптичан изгледа на први поглед, али све ове збрке прати одређене обрасце и поновљиве обрасце, тако да када смо добили основе доле, моћи ћете да напишете код овако и онда манипулишу код овако користи још један језик, под називом ЈаваСцрипт. А ЈаваСцрипт је језик који покреће унутар бровсер данас да користимо на Харвард курсева за алат курса тржног да Гоогле мапе користи да вам дају гомилу динамичности, Фејсбук даје вам показати најновије статуса, Твиттер га користи да вам покажем твитове одмах. Све ово ћемо почети да уронимо унутра Али да тамо, морамо да схватимо понешто о Интернету. Овај снимак је овде само минут дуго, и претпоставимо за сада је то, у ствари, како интернет функционише као тизер за оно што је требало да дође. Дајем ти "Ратници мреже." 

[♫ ♫ музика Споро Цхорус] [Мушко приповедач] Он је дошао са поруком. Са протоколом цео свој сопствени. [♫ ♫ Брже електронска музика] Он је дошао у свет хладних зидова, унцаринг рутера, и опасности много гори од смрти. Он је брз. Он је јак. Он је ТЦП / ИП, и он има своју адресу. Ратници мреже. [Малан] Следеће недеље, онда. Интернет. Веб програмирање. Ово је ЦС50. [ЦС50.ТВ]