[Powered by Google Translate] [Дел 6: Помалку Комфорни]
[Нејт Hardison] [Универзитетот Харвард]
[Ова е CS50.] [CS50.TV]
Во ред. Добредојдовте во делот 6.
Оваа недела, ние ќе се зборува за структури на податоци во делот,
првенствено затоа проблем оваа недела поставени на spellr
прави еден куп на различни податоци структура истражување.
Постојат еден куп на различни начини можете да отидете со проблемот во собата,
и повеќе структури на податоци знаете за, толку повеќе кул работи што можете да направите.
>> Па ајде да започнете. Прво ние ќе зборуваме за Купишта,
на магацинот и задачата структури на податоци кои ние ќе се зборува.
Купишта и редици се навистина корисни кога ќе почнам да зборувам за графикони,
која ние нема да направи толку многу за право сега.
Но тие се навистина добри за да се разбере една од големите основните структури на податоци за CS.
Описот во проблемот сет спецификација,
ако го повлече нагоре, зборува за Купишта како слично на
купот на јадење коцки кои ги имате во кафетеријата на јадење сали
каде што кога јадење персонал доаѓа и го става на јадење пепелниците откако тие ги чистат,
тие ги магацинот еден на врвот на другите.
И тогаш кога децата доаѓаат во да добијат храна,
тие се повлече на коцки исклучување, првиот на врвот, а потоа тој под него, тогаш еден под тоа.
Така, всушност, првиот послужавник дека јадење на персоналот спушти е последниот кој добива соблече.
За последен пат дека јадење на персоналот стави на е првиот кој добива соблече за вечера.
Во спец проблемот сет, што може да го симнете, ако веќе не сте,
зборуваме за моделирање оџак податоци stucture со користење на овој вид на struct.
>> Значи она што ние го добивме тука, ова е слично на она што беше презентиран во предавањето,
освен во предавање го презентиравме со ints наспроти char * s.
Ова ќе биде конзола која продавници што?
Даниел? Што сме ние чување во оваа оџакот?
[Даниел] Стрингови? >> Ние сме чување низи во оваа магацинот, точно.
Сите треба да имате со цел да се создаде магацинот е низа
на одреден капацитет, кој во овој случај,
капацитет ќе биде во сите капи, бидејќи тоа е константа.
А потоа и во прилог на низа, сите ние треба да се следи е сегашната големина на низата.
Една работа е да се напомене тука дека е вид на кул
е дека ние сме создавање на рангирани податоци структура на врвот на друга структура податоци, на низата.
Постојат различни начини да се спроведе Купишта.
Ние нема да го направи тоа уште доста, но се надевам дека откако ќе го направите на поврзани листа на проблеми,
ќе видите како можете лесно може да се спроведе оџак на врвот на поврзани листа, како и.
Но, за сега, ние ќе се држиме до низи.
Значи, повторно, сите ние треба е низа а ние само треба да ги пратите на големината на низата.
[Сем] За жал, зошто е тоа што ти рече дека магацинот е на врвот на жици?
За мене ми се чини дека конците се во рамките на магацинот.
[Hardison] Да. Ние сме создавање, ние сме преземање на нашите низа податоци структура -
тоа е големо прашање. Значи, прашањето е зошто, за луѓето кои се гледаат оваа онлајн,
зошто сме велејќи дека магацинот е на врвот на стрингови,
бидејќи тука личи на жици се во внатрешноста на оџакот?
Кој е целосно случајот.
Она што го мислеше е дека имаме низа податоци структура.
Имаме низа на char * s, оваа низа на стрингови,
и ние се случува да додадете на тоа, со цел да се создаде рангирани податоци структура.
>> Значи оџак е малку покомплексно отколку низа.
Можеме да го користиме низа за изградба на магацинот.
Значи тоа е каде што ние велиме дека магацинот е изграден на врвот на низа.
Исто така, како што реков претходно, ние може да се изгради оџак на врвот на поврзани листа.
Наместо да се користи низа да ја одржиме нашата елементи,
ние може да се користи поврзани со листата за да ја одржиме нашата елементи и да се изгради на магацинот околу тоа.
Ајде да одиме преку неколку примери, гледајќи некои код,
да видиме што навистина се случува овде.
На лево, јас сум фрлени она што магацинот struct ќе изгледа во меморијата
ако капацитет беа # дефиниран да биде четири.
Имаме нашите четири елемент char * низа.
Имаме стрингови [0], стрингови [1], стрингови [2], стрингови [3],
а потоа дека минатата простор за нашата големина број.
Дали ова има смисла? Во ред.
Тоа е она што се случува ако тоа што го правам на десната страна,
кој ќе биде мојот код, е само да се изјасни за struct, а рангирани struct наречен s.
Ова е она што го добиваме. Таа утврдува оваа стапало во меморијата.
Првото прашање тука е она што се содржините на овој магацинот struct?
Токму сега тие се ништо, но тие не се сосема ништо.
Тие се на овој вид на отпад. Немаме поим што е во нив.
Кога ќе се изјасни оџакот е, ние сме само фрлање дека надолу на врвот на меморија.
Тоа е вид на како прогласување int i, а не тоа иницијализацијата.
Вие не знаете што е таму. Можете да го прочитате она што е таму,
но тоа не може да биде супер корисни.
Една работа што сакам да се сеќавам да направите е да се иницијализира она што треба да биде иницијализиран.
Во овој случај, ние ќе треба да се иницијализира со големина да биде нула,
затоа што тоа се случува да испаднат да биде многу важно за нас.
Ние би можеле да одат напред и се иницијализира сите покажувачи, сите char * s,
да бидат некои разбирливо вредност, веројатно нула.
Но тоа не е сосема неопходно што правиме тоа.
>> Сега, двете главни операции на Купишта се?
Секој се сеќавам од предавање она што го правите со Купишта? Да?
[Стела] Туркање и пукање? >> Токму така.
Туркање и пукање, се двете главни операции на Купишта.
И она што не притисни направам? >> Таа го става нешто кон врвот
на магацинот, а потоа пукање го соблекува.
[Hardison] Токму така. Значи туркање турка нешто на врвот на магацинот.
Тоа е како јадење на персоналот ставање на јадење лента надолу на шанкот.
И пукање е со земање на јадење лента исклучување на магацинот.
Ајде да одиме преку неколку примери на она што се случува
кога ќе им помогнам на работите во магацинот.
Ако бевме да им помогнам на стринг "hello" врз нашата оџакот,
тоа е она што нашите дијаграм ќе изгледа сега.
Погледнете што се случува?
Ние се наметнува на првиот елемент на нашата жици низа
и ние покренато нашата големина брои да биде 1.
Значи, ако ние се погледне на разликата помеѓу двете слајдови, тука е 0, еве пред притисок.
Тука е по притисок.
Пред бута, по притискање.
И сега имаме еден елемент во нашата оџак.
Тоа е стринг "hello", и тоа е тоа.
Сè друго во низа, во нашата жици низа, се уште е ѓубре.
Ние не го иницијализира.
Да речеме дека ние им помогнам на некој стринг врз нашата оџак.
Ние ќе им помогнам на "светот" на ова време.
Така можете да видите "светот" тука се на врвот на "здраво",
и големината брои оди до 2.
Сега можеме да им помогнам на "CS50", и дека ќе одиме на врвот повторно.
Ако се вратиме, можете да видите како ние сме туркање работи на врвот на магацинот.
И сега ние да се појави.
Кога ќе се појави нешто надвор од магацинот, што се случило?
Секој видите разликата? Тоа е прилично суптилна.
[Студентски] Големината. >> Да, големината промени.
>> Што друго би се очекува да се промени?
[Студентски] На жици, исто така. >> Право. Конците премногу.
Излегува дека кога ќе си го прави тоа на овој начин,
бидејќи ние не сме копирање на елементи во нашата оџакот,
ние всушност не треба да правите ништо, ние само може да се користи големина
да ги пратите на бројот на нештата во нашата низа
така што кога ќе се појави повторно, повторно ние само декриминирачките нашата големина до 1.
Нема потреба да се всушност оди во и пребришете ништо.
Вид на фанки.
Излегува дека ние обично само остави работите сами, бидејќи тоа е помалку работа за нас да се направи.
Ако ние не треба да се вратиш назад и замени нешто, тогаш зошто го прави тоа?
Па кога ќе се појави двапати надвор од магацинот, сето тоа не е некоја вредност за големината неколку пати.
И повторно, ова е само затоа што не сте копирање нешта во нашиот оџак.
Да? Оди напред.
[Студент, неразбирливо] >> И тогаш што се случува кога ќе им помогнам нешто повторно?
Кога ќе се притисне нешто повторно, каде се оди?
Каде се оди, Василиј? >> Во стрингови [1]? >> Право.
Зошто не се оди во низи [3]?
[Василиј] Поради тоа што заборавил дека има нешто во низи [1] и [2]?
[Hardison] Токму така. Нашите магацинот, во суштина, "заборавил" дека тој, за да ништо
во низи [1] или жици [2], па кога ќе им помогнам на "woot"
тоа само го става тоа во елемент на стрингови [1].
Дали постојат било какви прашања за тоа како тоа функционира, на основно ниво?
[Сем] Значи ова не е динамичен во било кој начин, во однос на износот
или во однос на големината на оџакот?
[Hardison] Токму така. Ова е - поентата е дека ова не е динамички growning оџак.
Ова е конзола која може да се одржи, најмногу, четири char * а, најмногу четири нешта.
Ако бевме да се обиде и да се поттикнат една петтина нешто, што мислите треба да се случи?
[Студентите, неразбирливо]
[Hardison] Токму така. Постојат голем број на нешта што може да се случи.
Тоа би можело евентуално секунда грешка, во зависност од она што сме биле -
како точно бевме спроведување на back-end.
Тоа би можело да запишете врз неа. Тоа може да го имаат тоа buffer overflow кои ние разговаравме за во класата.
Што ќе биде на повеќето очигледно нешто што може да бидат препишани
ако се обидовме да им помогнам на дополнителна работа за нашите оџакот?
Така што ги спомна на buffer overflow.
Што би можело да биде нешто што ќе се напишани во текот или изгазил
ако ние преплави случајно од страна се обидуваат да им помогнам на екстра нешто?
[Даниел, неразбирливо] >> можно.
Но на почетокот, што може да се случи? Што ако ние се обидовме да им помогнам на четвртата работа?
Тоа би можело да ја пребришете големина, барем со оваа меморија дијаграм кој ние го добивме.
>> Во проблемот сет спецификација, што е она што ние ќе треба да се спроведува и денес,
она што сакам да направите е само да се врати лажни.
Нашите притисни метод ќе се врати логичка вредност,
и дека логичка вредност ќе биде вистина ако притисни успева
и лажни ако не можеме да помогнам нешто повеќе, бидејќи на магацинот е полна.
Ајде да одиме преку малку на тој код во моментов.
Тука е нашата притисни функција.
Нашите притисни функција за магацинот се случува да се земе во низа да се стави на магацинот.
Тоа се случува да се вратат вистина ако стрингот беше успешно се наметнува
на магацинот и лажни поинаку.
Било какви предлози за тоа што може да биде добра првото нешто да направите овде?
[Сем] Ако големина е еднаква на капацитетот потоа се врати лажни?
[Hardison] Бинго. Ница работа.
Ако големината е капацитетот, ние ќе се врати лажни.
Ние не можеме да се стави нешто повеќе во нашите оџак.
Инаку, ние сакаме да се стави нешто на врвот на магацинот.
Што е "на врвот на магацинот", првично?
[Даниел] Големина на 0? >> Големина на 0.
Што е на врвот на магацинот по има едно нешто во магацинот? Ма, знаеш?
[Ма] Еден. >> Големина е еден, точно. Можете да ја задржите додавањето на големината,
и секој пат кога ќе се стави во нов елемент на индекс големина во низа.
Ние можеме да го направи тоа со таква една лагер, ако тоа го прави смисла.
Па ние го добивме нашиот жици низа, ние ќе го пристап во големината индекс,
и ние сме само ќе да ја запази нашите char * таму.
Забележи како нема стринг копирање случува овде,
Нема динамична алокација на меморија?
А потоа Missy израснати она што ние сега треба да направите,
бидејќи ние се чуваат на стрингот во соодветно место во низа,
и таа ми рече дека имавме за зголемување на големината на еден така што ние сме подготвени за следниот притисок.
Значи можеме да го направите тоа со s.size + +.
Во овој момент, ние сме турна во нашата низа. Што е последното нешто што треба да направите?
[Студентски] Врати се вистина. >> Врати вистина.
Така, тоа е прилично едноставна, прилично едноставен код. Не премногу.
Откако ќе заврши вашата глава околу тоа како оџакот работи,
ова е прилично едноставно да се имплементира.
>> Сега, следниот дел од ова е пукање низа исклучување на магацинот.
Одам да ви даде момци некои време да работат на ова малку.
Тоа е речиси суштина обратна од она што ние го направивме тука притисок.
Она што го направив е всушност - Упс.
Сум стартува апаратот овде, и во апаратот,
Сум застана на проблемот постави 5 спецификација.
Ако ние зумирате тука, можеме да видиме сум во cdn.cs50.net/2012/fall/psets/pset5.pdf.
Дали сте момци преземале оваа код кој се наоѓа тука, section6.zip?
Во ред. Ако не сте го направиле тоа, го направи тоа право сега, навистина брзо.
Јас ќе го направи тоа во мојот терминален прозорец.
Јас всушност тоа го правеше до тука. Да.
Да, Сем? >> Имам едно прашање за тоа зошто рековте s.string ги загради на големината = ул?
Што е ул? Е тоа што се дефинира некаде пред, или - ох, во char * ул?
[Hardison] Да, точно. Тоа беше аргумент. >> О, во ред. Жал ми е.
[Hardison] Ние сме специфицирање на стринг за да им помогнам внатре
На друго прашање што може да дојде до што ние навистина не зборуваме за тука беше
ние зеде здраво за готово дека имавме оваа променлива наречена ги
тоа беше во обем и достапни за нас.
Ние зеде здраво за готово дека е беше ова магацинот структурата.
Така гледајќи назад во оваа притисни код,
можете да видите дека ние сме прави работи со овој стринг кој доби помина во
но потоа одеднаш, ние сме пристап s.size, како, каде и да доаѓаат од?
Во код кој ние ќе го разгледаме во делот архива
а потоа работи што ќе се прави во вашиот проблем поставува,
ние направивме нашиот магацинот struct глобалната променлива
така што можеме да имаме пристап до него, во сите наши различни функции
без рачно да го помине околу и да го со упатување,
направи сето она што вид на работи на него.
Ние сме само мамење малку, ако сакате, да се направат работите поубаво.
И тоа е нешто што го правиме тука, бидејќи тоа е за забава, тоа е полесно.
Често, ќе видите луѓе го направите ова, ако тие имаат една голема податочна структура
тоа е се работи на во рамките на нивната програма.
>> Да се ​​вратиме во текот на апаратот.
Дали сите успешно го добиете section6.zip?
Сите го отпакувате користење отпакувате section6.zip?
Ако одите во делот 6 директориум -
Aah, насекаде -
и листата што е тука, ќе видите дека имате различни три. в датотеки.
Имаш дното, на SLL, што е одделно поврзана листа, и оџак.
Ако се отвори stack.c,
можете да видите дека ние го добивме ова struct дефинирани за нас,
точната struct дека ние едноставно зборуваше за во слајдовите.
Имаме нашата глобална променлива за оџакот,
ние го добивме нашиот притисни функција,
а потоа ние го добивме нашата поп функција.
Ќе стави код за притисни назад на слајд тука,
но она што јас би сакал вие момци треба да направите е, на најдоброто од вашата способност,
одат и спроведување на поп функција.
Откако ќе го спроведува, може да ги собере со направи оџакот,
а потоа извршете ја произлегуваат магацинот извршна,
и дека ќе работи на сите на овој тест код овде долу тоа е во главниот.
И главните грижи на всушност правејќи го притисни и поп повици
и што си сигурен дека сето тоа оди преку ред.
Таа, исто така иницијализира на магацинот големина тука
така да не мора да се грижите за иницијализирање на тоа.
Може да се претпостави дека тоа е правилно иницијализиран
од страна на време дека пристап до неа во pop функција.
Дали тоа има смисла?
Значи тука ќе одиме. Има притискање код.
Јас ќе ви даде момци 5 или 10 минути.
И ако имате било какви прашања во меѓувреме додека сте кодирање,
обратете се кај нив гласно.
Значи, ако дојде до камен на сопнување, само побарајте.
Дозволете ми да знам, нека секој друг знаат.
Работи со вашиот сосед премногу.
[Даниел] Ние сме само спроведување поп во моментов? >> Само поп.
Иако можете да копирате спроведувањето на притисни ако сакате
така што на тестирањето ќе работат.
Затоа што тоа е тешко да се тестираат работи навлегува во -
или, тешко е да се тестира пукање работи надвор од магацинот ако не постои ништо во магацинот за да започнете со.
>> Што е поп би требало да се врати? На елементот од врвот на магацинот.
Тоа би требало да добие елемент исклучување на врвот на магацинот
а потоа декриминирачките големината на магацинот,
и сега сте изгубиле на елемент на врвот.
И тогаш ќе се вратите на елементот на врвот.
[Студент, неразбирливо]
[Hardison] Значи она што се случува ако го правиш тоа? [Студент, неразбирливо]
Што завршува случува е најверојатно пристап или
елемент кој не е иницијализиран уште, па вашиот пресметка
од каде на последниот елемент е е исклучено.
Па еве, ако забележите, во бута, ние сме пристап до жиците на s.size елемент
бидејќи тоа е нов индекс.
Тоа е новиот врвот на магацинот.
Додека во поп, s.size ќе биде следниот простор,
просторот што е на врвот на сите елементи во вашиот оџак.
Значи топ-повеќето елемент не е во s.size,
туку тоа е под него.
>> Од друга работа да направите кога ќе - во поп,
ви треба да декриминирачките големина.
Ако се сеќавате назад кон нашата мала дијаграм токму тука,
навистина, единственото нешто што сме го виделе случува кога вика поп-
беше дека оваа големина падна, прво до 2, потоа на 1.
Тогаш кога се наметнува нов елемент, тоа ќе оди на на соодветна самото место.
[Василиј] Ако s.size е 2, тогаш тоа не ќе оди во елемент 2,
и тогаш ќе сакате да pop тој елемент надвор?
Значи, ако отидовме - >> Па ајде да погледнеме повторно.
Ако ова е нашата магацинот во овој момент
и ние го нарекуваме поп,
на која индекс е топ-повеќето елемент?
[Василиј] На 2, но тоа се случува да pop-3. >> Право.
Значи тоа е каде што нашата големина е 3, но ние сакаме да pop-елемент на индексот 2.
Тоа е толку типичен вид на надвор од оној што го имаме со нулто индексирање на низи.
Значи вие не сакате да pop третиот елемент, но третиот елемент не е во индекс 3.
И причина ние не треба да го направите тоа минус 1, кога сме туркање
е затоа што токму сега, ќе забележите дека топ-повеќето елемент,
ако ние требаше да им помогнам на нешто друго врз оџакот во овој момент,
ние би сакале да им помогнам на индекс 3.
И тоа само така се случува, дека големината и индексите се редат кога сте туркање.
>> Кој доби работна магацинот имплементација?
Имаш работа магацинот еден. Дали имате поп работат уште?
[Даниел] Да. Јас мислам така.
>> Програмата работи и не секунда Разлом, тоа е печатење?
Дали го испечатите "успех", кога ќе го стартувате?
Да. Направете магацинот, работи, ако тоа отпечатоци од "успехот" и не оди бум,
тогаш сите е добро.
Во ред. Ајде да одиме во текот на апаратот навистина брзо,
и ние ќе одиме преку ова.
Ако ги погледнеме во она што се случува тука со поп,
Даниел, што е првото нешто што си направил?
[Даниел] Ако s.size е поголем од 0.
[Hardison] Во ред. И зошто го правите тоа?
[Даниел] За да бидете сигурни дека има нешто во внатрешноста на оџакот.
[Hardison] Десен. Сакате да пробате да бидете сигурни дека s.size е поголема од 0;
Инаку, она што сакаш да се случи?
[Даниел] Врати нула? >> Врати нула, точно.
Значи, ако s.size е поголем од 0. Тогаш што ќе правиме?
Што ќе правиме ако магацинот не е празен?
[Стела] Вие декриминирачките големината? >> Можете декриминирачките големината, во ред.
Па, како го правиш тоа? >> S.size--.
[Hardison] Велики. А потоа она што го правиш?
[Стела] И тогаш реков враќање s.string [s.size].
[Hardison] Велики.
Инаку ќе се врати нула. Да, Сем?
[Сем] Зошто не треба да биде s.size + 1?
[Hardison] Плус 1? >> Да. >> Го зедов тоа.
[Сем] Мислев дека затоа сте земање 1 надвор,
тогаш ќе треба да се врати не е оној дека тие побарале.
[Hardison] И ова е само она што се зборува со целата оваа прашање од 0 индекси.
Значи, ако ние враќање овде.
Ако ги погледнеме во овој човек овде, што можете да видите дека кога ќе поп,
ние сме пукање на елемент на индекс 2.
>> Значи ние се намали нашата големина, а потоа нашата големина одговара на нашиот индекс.
Ако ние не декриминирачките големината, а потоа ние треба да направите големина -1, а потоа декриминирачките.
Велики. Сите добри?
Било какви прашања за тоа?
Постојат голем број на различни начини да се напише тоа како добро.
Всушност, можеме да сториме и нешто - можеме да направиме една лагер.
Ние може да направи една линија враќање.
Значи ние всушност може да декриминирачките пред да се врати со тоа.
Значи ставање на - пред s.size.
Тоа го прави на линијата навистина густ.
Каде што разликата помеѓу -. Големината и s.size--
е дека ова postfix - тие го нарекуваат тоа postfix бидејќи - доаѓа по s.size--
значи дека s.size се оценува за целите на изнаоѓање на индексот
како што е во моментов кога оваа линија се извршува,
и тогаш ова - се случува по линија добива извршува.
По елемент на индекс s.size се пристапува.
И тоа не е она што го сакаме, затоа што ние сакаме некоја вредност за да се случи прво.
Othewise, ние ќе треба да се пристапува на низа, ефикасно, надвор од границите.
Ние ќе се пристапува на елемент над оној што ние всушност сакате да пристапите.
Да, Сем? >> Е тоа побрзо или користи помалку меморија да се направи во една линија или не?
[Hardison] Искрено, тоа навистина зависи.
[Сем, неразбирливо] >> Да, тоа зависи. Можете да го направите компајлерот трикови
за да го добиете компајлерот да се признае дека, вообичаено, се замисли.
>> Значи ние сме споменати малку за оваа компајлерот оптимизација работи
што можете да направите во составувањето,
и тоа е вид на нешто што компајлерот може да биде во можност да дознаам,
како ох, еј, можеби можам да направам сето ова во една операција,
што е спротивно на вчитување на големината променлива во од RAM меморија,
намалување за тоа, чување на тоа назад, а потоа вчитување назад во повторно
за обработка на остатокот од оваа операција.
Но, обично, не, ова не е вид на нешто
што се случува да се направи вашата програма значително побрзо.
Повеќе прашања во врска со Купишта?
>> Значи туркање и пукање. Ако вие момци сакате да пробате хакер издание,
она што ние го направивме во хакер издание е всушност помина
и направи овој магацинот расте динамично.
Предизвикот не е првенствено се тука во притисни функција,
да дознаам како да се направи таа низа расте
како што се задржи туркање повеќе и повеќе елементи за да магацинот.
Тоа е, всушност, не премногу дополнителен код.
Само повик до - мора да се сеќавам да се добие повици кон Примерок таму правилно,
а потоа дознаам кога ќе одиш да се јавите realloc.
Тоа е забавно предизвик ако сте заинтересирани.
>> Но, засега, да се движи, и ајде да разговараме за редици.
Движете се низ овде.
На дното е близок роднина на магацинот.
Значи во магацинот, она што се стави во последните
беа првите работи кои треба да потоа биде откриена.
Имаме оваа последна во прво надвор, или LIFO, нарачување.
Додека во редот, како што би очекувале од кога си стојат во ред,
првиот човек да се во согласност, првото нешто да се влезе во редот,
е првото нешто што добива извадени од дното.
Редици се исто така често се користи кога ние сме се занимаваат со графикони,
како што зборуваше за кратко со Купишта,
и редици се исто така корисна за еден куп други работи.
Едно нешто што доаѓа до често се обидуваат да се одржи, на пример,
сортирани листа на елементи.
И можете да го направите ова со низа. Можете да одржите подредени листа на работи во низа,
но каде што станува незгодно е тогаш вие секогаш треба да се најде
соодветно место за да вметнете следниот нешто.
Значи, ако имате низа од броеви, од 1 до 10,
а потоа ќе сакаат да го прошират дека до сите броеви од 1 до 100,
а ти си добивање на овие броеви по случаен редослед и се обидува да се задржи сето
подредени како да одиш преку, ќе се заокружи има да се направи многу на менувањето.
Со одредени видови на редици и одредени видови на основните структури на податоци,
вие всушност може да го задржи тоа прилично едноставна.
Вие не треба да додадете нешто, а потоа реконструкција на целата работа секој пат.
Ниту, пак, ќе мора да направи многу на менувањето на внатрешната елементи наоколу.
Кога ќе се погледне во ред, ќе го видите тоа - исто така и во queue.c во делот код -
на struct дека ние сме ви даде е навистина слични на struct кој ние ќе ви даде за оџак.
>> Има еден исклучок од ова, и дека еден исклучок
е дека имаме овој дополнителен број нарекува глава,
и шефот тука е за следење на главата на дното,
или првиот елемент во редот.
Со магацинот, бевме во можност да ги пратите на елементот што бевме за да се добие,
или на врвот на магацинот, користејќи само големината,
а со задача, ние мора да се справи со спротивните краеви.
Ние се обидуваме да тактика работите на крајот, но потоа се врати работите од напред.
Толку ефектно, со главата, имаме индексот на почетокот на редот,
и големината ни дава индексот на крајот од редот
така што можеме да добијам работите од главата и додадете нешта за да на опашката.
Додека кај магацинот, бевме само некогаш се занимаваат со врвот на магацинот.
Ние никогаш не мораше да пристапите до дното на магацинот.
Ние само додаде работи на врвот и ги зедоа работите надвор од врвните
па ние не треба дополнителна дека областа во нашите struct.
Дали тоа воопшто има смисла?
Во ред. Да, Шарлот? [Шарлот, неразбирливо]
[Hardison] Тоа е големо прашање, а тоа беше оној кој дојде во предавање.
Можеби прошетка низ неколку примери ќе ги илустрираат зошто
ние не сакаме да ги користат стрингови [0] како шеф на задачата.
>> Значи замислете дека ние имаме задача, ние ќе го наречеме задача.
На почетокот, кога ние сме само тоа instantiated,
кога сте само да го прогласи, не сме иницијализира ништо.
Сето тоа е ѓубре. Па се разбира, ние сакаме да се осигураме дека можеме иницијализирам
и големината и шефот полиња да биде 0, нешто разумно.
Ние, исто така може да оди напред и нула на елементите во нашата задача.
И да се направи овој дијаграм се вклопуваат, забележите дека сега нашата задача само може да се одржи три елементи;
додека нашата магацинот би можеле да одржат четири, нашата задача само може да се одржи три.
И тоа е само да се направи дијаграм одговара.
Првото нешто што се случува овде е дека ние Стави во ред стринг "Здраво".
И исто како што направивме со магацинот, ништо страшно различни тука,
ние фрли стринг за на стрингови [0] и зголемување нашата големина од 1.
Ние Стави во ред "збогум", станува облечете.
Значи ова личи на магацинот во најголем дел.
Ние започна тука, нов елемент, нов елемент, големината држи случува до.
Што се случува во овој момент, кога сакаме да dequeue нешто?
Кога сакаме да dequeue, која е елемент кој сакаме да dequeue?
[Василиј] Стрингови [0]. >> Нула. Точно во право, Василиј.
Ние сакаме да се ослободиме од првата низа, овој, "Здраво".
Значи она што е друга работа што се промени?
Забележите кога ние појави нешто надвор од оџакот, ние едноставно се промени големината,
но тука, имаме неколку работи таа промена.
Не само што големина промени, но главата промени.
Ова е да се вратам на поентата на Charlotte порано:
зошто имаме оваа глава, како?
Дали има смисла сега, Шарлот? >> Вид.
[Hardison] Вид на? Значи она што се случи кога ќе dequeued?
Што главата направи тоа сега е интересно?
[Шарлот] О, бидејќи тоа се промени - во ред. Гледам.
Бидејќи глава - каде главата е да се покажува промени во однос на локацијата.
Тоа веќе не е секогаш нула индекс на еден. >> Да, точно.
Она што се случи е ако dequeueing висок елемент
беше направено и ние не ја имаат оваа глава поле
затоа што ние секогаш се повикува овој стринг во 0 индексот на чело на нашата листа на чекање,
тогаш ќе треба да се префрлат на остатокот од дното надолу.
Ние ќе мора да се префрлат "збогум" од од стрингови [1] на стрингови [0].
И стрингови [2] до стрингови [1].
И ние ќе мора да го стори тоа за целата листа на елементи,
целата низа на елементи.
И кога ние го правиме ова со низа, која добива навистина скапи.
Па еве, тоа не е голема работа. Ние само треба три елементи во нашата низа.
Но, ако имавме задача од илјада елементи или еден милион елементи,
а потоа одеднаш, ние почнат да прават еден куп на dequeue повикува сите во еден циклус,
работите се навистина се случува да го успори како што се менува се надолу постојано.
Знаете, се префрлат од 1, промена од 1, промена од 1, промена од 1.
Наместо тоа, ние ги користиме оваа глава, ние ја нарекуваме "покажувач", иако тоа не е навистина покажувач
во строга смисла на зборот, тоа не е покажувачот тип.
Тоа не е int * или char * или нешто слично.
Но тоа е посочувајќи или укажува на чело на нашата задача. Да?
>> [Студентски] Како dequeue знаат само убивам она што е на чело?
[Hardison] Како dequeue знаат како да убивам она што е на чело? >> Право, да.
>> Што е во потрага по е само што главата поле е наместено да.
Така што во овој првиот случај, ако гледаме тука,
нашата глава е 0, индексот на 0. >> Право.
[Hardison] Па тоа само вели во ред, добро, елемент на индекс 0, стрингот "Здраво",
е елемент на чело на нашата задача.
Па ние ќе dequeue тоа момче.
И дека ќе биде елемент кој добива се врати на повикувачот.
Да, Saad? >> Значи главата основа поставува - каде што ви се случува да индексира тоа?
Тоа е почеток на тоа? >> Да. >> Океј.
[Hardison] Тоа е да стане нов почеток за нашата низа.
Па кога ќе dequeue нешто, сите што треба да направите е да пристапите на елемент во индекс q.head,
и дека ќе биде елемент кој сакате да го dequeue.
Можете исто така треба да декриминирачките големина.
Ќе видиме во малку каде што нештата се малку слабо со ова.
Ние dequeue, и сега, ако ние Стави во ред, повторно,
каде сме ние Стави во ред?
Каде следниот елемент одат во нашата задача?
Велат сакаме да Стави во ред на стрингот "CS".
Во која индекс ќе одиме? [Студентите] Стрингови [2]. >> Два.
Зошто 2 и не 0?
[Василиј] Бидејќи сега главата е 1, па тоа е како на почетокот на листата?
[Hardison] Десен. И она што го означува крајот на листата?
Што бевме користење за да се означи крајот на нашите дното?
Главата е на чело на нашата листа на чекање, на почетокот на нашата задача.
Што е крајот на нашата задача? [Студентите] Големина. >> Големина, точно.
Па нашите нови елементи одат во во големина, и елементите кои ние ги тргнеме падне на глава.
Кога ќе Стави во ред следниот елемент, ние го стави во во големина.
[Студентски] Пред да се стави дека во сепак, големината е 1, нели?
[Hardison] Десен. Па не е сосема во големина. Големина + не, 1, но + главата.
Бидејќи ние се префрли што од страна на шефот износ.
Па еве, сега ние го добивме задача на големина 1, која почнува на индекс 1.
Опашката е индекс 2. Да?
>> [Студентски] Што се случува кога ќе dequeue стрингови [0], и стрингови 'слотови во меморијата
само да се испразни, во основа, или само заборавен?
[Hardison] Да. Во оваа смисла, ние сме само ги забораваат.
Ако бевме чување на копии од нив за -
многу структури на податоци често ќе ги чувате своите сопствени копии на елементите
така што лицето кое раководи со податочна структура не мора да се грижите
за тоа каде сите тие совети се случува.
Податочна структура има за да сè, има за да сите копии,
да бидете сигурни дека сè продолжува соодветно.
Меѓутоа, во овој случај, овие структури на податоци само за едноставност,
не се прават копии на нешто што ние сме чување во нив.
[Студентски] Значи ова е континуирана низа на - >> Да.
Ако ги погледнеме назад во она што дефиницијата беше на оваа структура, тоа е.
Тоа е само стандарден низа како сте виделе,
низа на char * s.
Дали тоа - >> Да, јас бев само се прашувам
ако сте на крајот ќе снема меморија, до одреден степен,
ако имате сите овие празни места во вашиот низа?
[Hardison] Да, тоа е добра точка.
>> Ако ги погледнеме во она што се случи сега во овој момент,
ние сме полни нашата задача, изгледа.
Но, ние не се навистина полни нашата задача
бидејќи имаме задача која е со големина од 2, но тоа започнува на индекс 1,
бидејќи тоа е местото каде нашата глава покажувач.
Како што велеа, тој елемент на стрингови [0], на индекс 0, не е навистина таму.
Тоа не е во нашата задача веќе.
Ние само не се мачат да одат во и пребришете го кога ќе го dequeued.
Па дури и покрај тоа што изгледа како ние сме снема меморија, ние навистина не треба.
Тоа место е достапен за нас да го користите.
На соодветно однесување, ако ние требаше да се обиде и првиот dequeue нешто
како "збогум", која ќе pop-bye исклучени.
Сега нашата задача започнува во индекс 2 и е со големина од 1.
И сега, ако ние се обидуваме и Стави во ред нешто повторно, да речеме 50,
50 треба да одат во ова место на индекс 0
затоа што тоа е се уште на располагање за нас. Да, Saad?
[Саад] Дали тоа се случи автоматски?
[Hardison] Тоа не се случи сосема автоматски. Мора да го направите математика
да го направите да работи, но во суштина она што ние го направивме е што сме само обвиткана околу.
[Saad] И тоа е во ред, ако тоа има дупка во средината од него?
[Hardison] Тоа е ако можеме да се направи математика работат надвор правилно.
>> И излегува дека тоа е всушност и не е толку тешко да се направи со современи оператор.
Значи исто како што направивме со Цезар и работи крипто,
користење на современи, ние може да се работи за да заврши околу и продолжувам да одам
околу и наоколу и околу со нашите дното,
имајќи дека главата покажувачот се движи наоколу.
Забележете дека големината е секогаш почитувајќи го бројот на елементи всушност во рамките на редот.
И тоа е само главата покажувач што ги држи возење велосипед низ.
Ако ги погледнеме во она што се случи тука, ако ние се вратиме на почетокот,
и ти само се види она што се случува во главата
кога Стави во ред нешто, ништо не се случи во главата.
Кога ќе enqueued нешто друго, ништо не се случи во главата.
Штом ќе dequeued нешто, шефот оди по еден.
Ние enqueued нешто, ништо не се случува во главата.
Кога ќе dequeue нешто, одеднаш главата добива зголемува.
Кога ќе Стави во ред нешто, ништо не се случува во главата.
>> Што ќе се случи во овој момент, ако ние требаше да dequeue нешто повторно?
Секој мисли? Што ќе се случи на главата?
Што треба да се случи на главата
ако ние требаше да dequeue нешто друго?
Главата во моментов е во индекс 2,
што значи дека на чело на листа на чекање е стрингови [2].
[Студентски] Кои се враќа 0? >> Тоа треба да се врати на 0. Тоа треба да заврши назад наоколу, точно.
Досега, секој пат кога ние се нарекува dequeue, ние сме додавање на една на главата,
додадете една до главата, додадете една до главата, додадете една до главата.
Штом дека главата покажувачот добива до последниот индекс во нашата низа,
тогаш ние треба да ја заврши назад околу на почетокот, врати се назад на 0.
[Шарлот] Што го одредува капацитетот на дното во оџак?
[Hardison] Во овој случај, ние само се користи # дефинирана константа. >> Океј.
[Hardison] Во вистински. В датотека, можете да одат во и секрети со неа малку
и да ја направат толку голема или малку, како сакате.
[Шарлот] Значи, кога сте го прави задача, како да се направи на компјутерот знае
колку е голема дека сакате оџакот да биде?
[Hardison] Тоа е големо прашање.
Постојат неколку начини. Една од нив е само да го дефинираат однапред
и велат дека ова ќе биде задача која има 4 елементи или 50 елементи или 10.000.
Другиот начин е да го направи она што на хакерите издание луѓе се прави
и да се создаде функции да имате задача да расте динамички како повеќе работи се додаде внатре
>> [Шарлот] Па да одам со првата опција, што синтакса го користите
да му кажете на програмата што е големината на задачата?
[Hardison] Ах. Значи, да излезе од ова.
Јас сум уште во stack.c тука, па јас сум само ќе дојдете до врвот тука.
Можете да видите ова право тука? Ова е # define капацитет 10.
И ова е речиси иста синтакса која ја имаме за задача.
Освен во ред, ние го добивме дека екстра struct областа тука.
[Шарлот] О, јас мислев на капацитетот значеше капацитет за стринг.
[Hardison] Ах. >> Тоа е максималната должина на зборот. >> Го зедов тоа.
Да. Капацитетот тука - тоа е голема точка.
И ова е нешто што е незгодно
затоа што она што ние го прогласи тука е низа од char * s.
Низа на совети.
Ова е низа од знаци.
Ова е веројатно она што го виделе кога сте биле прогласување вашиот амортизери за датотеката I / O,
кога сте биле создавање жици рачно на магацинот.
Сепак, она што ние го добивме тука е низа од char * s.
Така, тоа е низа на совети.
Всушност, ако зумирате назад и гледаме што се случува тука
во презентацијата, ќе видите дека вистинските елементи, ликот на податоци
не се чуваат во низа себе.
Што се чуваат во нашата низа тука се совети за карактерот на податоци.
Во ред. Така видовме како големината на задачата е исто како со оџакот,
големината секогаш почитува бројот на елементи во моментов на листа на чекање.
По правењето 2 enqueues, големината е 2.
По донесување на dequeue големината е сега 1.
По што друго Стави во ред големината е назад до 2.
Па големината дефинитивно почитува бројот на елементи во редот,
а потоа на главата само чува велосипед.
Тоа оди од 0-1-2, 0-1-2, 0-1-2.
И секој пат кога ние го нарекуваме dequeue, шеф покажувачот добива зголемува на наредниот индекс.
И ако главата е за да поминат, тоа петелки назад околу да се 0.
Така да со тоа, ние може да напише на dequeue функција.
И ние ќе го напушти Стави во ред функција за вас момци да се спроведе наместо тоа.
>> Кога ќе dequeue елемент надвор од нашата задача,
она што беше првото нешто што Даниел направи кога почнавме пишување на поп функција за Купишта?
Дозволете ми да се слушне од некој кој не зборува уште.
Ајде да видиме, Саад, се сеќаваш ли што Даниел направив како првото нешто кога тој напиша поп?
[Саад] Имаше, тоа беше - >> Тој тестиран за нешто.
[Саад] Ако големина е поголема од 0. >> Токму така.
И што беше тоа тестирање за?
[Саад] Тоа беше тестирање за да се види дали има нешто внатре во низа.
[Hardison] Да. Точно. Така да не може да pop-ништо надвор од магацинот ако е празна.
Исто така, не можете да dequeue ништо од редот ако е празна.
Што е првото нешто што треба да правиме во dequeue функцијата тука, мислите?
[Саад] Ако големина е поголема од 0? >> Да.
Во овој случај, јас сум всушност само се тестираат за да видат дали тоа е 0.
Ако е 0, ние може да се врати нула.
Но иста логика.
И нека продолжи со ова.
Ако големината не е 0, каде што е елемент кој сакаме да dequeue?
[Саад] На чело? >> Токму така.
Ние само може да се повлече од првиот елемент во нашата задача
со пристап на елемент во главата.
Ништо луд.
После тоа, она што треба да направам? Што треба да се случи?
Што е друга работа што ние разговаравме за во dequeue?
Две работи треба да се случи, бидејќи нашата задача е променет.
[Даниел] Намалување на големина. >> Мораме да ја намали големината, и да се зголеми на главата? Точно.
Да се ​​зголеми на главата, не можеме само слепо се зголеми на главата, се сеќавам.
Ние не само може да го направи queue.head + +.
Имаме исто така да вклучуваат овој мод со капацитет.
И зошто МО од капацитетот, Стела?
[Стела] Поради тоа треба да заврши околу. >> Токму така.
Ние МО со капацитет бидејќи мора да заврши назад околу да се 0.
Па сега, во овој момент, ние може да го направи она што Даниел рече.
Ние можеме да декриминирачките големина.
А потоа ние едноставно може да се врати на елемент, кој беше на врвот на задачата.
Тоа изгледа вид на чепат во прв план. Можете да имате прашање. Жал ми е?
>> [Сем] Зошто е прв на врвот на редот? Каде што одат?
[Hardison] Таа доаѓа од четвртиот ред од дното.
Откако ќе тестира за да бидете сигурни дека нашата задача не е празна,
ние се повлече char * Прво, ние се повлече елемент кој седи на чело индекс
на нашата низа, на нашите жици низа, >> и повик дека првиот?
[Hardison] И ние го нарекуваме прв план. Да.
Само да се надоврзе на тоа, зошто мислите моравме да го направите тоа?
[Сем] Секоја првиот е само враќање q.strings [q.head]? >> Да.
>> Бидејќи ние го правиме ова менување на q.head со современи функција,
и не постои начин да го направите тоа во рамките враќање линија, исто така.
[Hardison] Токму така. Ти си место на. Сем целосно самото место на.
Причината поради која мораше да се повлече од првиот елемент во нашата задача и чувајте го во променлива
е затоа што оваа линија, каде што имавме само q.head,
има МО оператор таму не е нешто што можеме да направиме
и да го имаат во сила на глава без - во една линија.
Значи ние всушност треба да се повлече од првиот елемент, потоа се приспособат на главата,
прилагодите големина, а потоа се врати на елементот што ќе се извади.
И ова е нешто што ќе видиме излезе подоцна со
поврзани листи, како што се позанимавам со нив.
Често кога ќе се ослободи или отстранување на поврзани листи
што треба да се сеќавам на следниот елемент, следниот покажувачот на поврзани листа
пред отстранување на тековната.
Затоа што во спротивно фрлаат на информации за тоа што е оставена во листата.
Сега, ако одите во Вашиот уред ќе се отвори queue.c--x надвор од ова.
Значи, ако јас се отвори queue.c, дозволете ми да зумирате тука,
ќе видите дека имате слични изглед на датотека.
Слични изглед на датотека, за да она што го имавме порано со stack.c.
Имаме нашите struct за задача дефинирани само како што видовме на слајдови.
>> Ние имаме Стави во ред функција која е за вас да се направи.
И ние имаме dequeue функција овде.
На dequeue функција во датотеката е имплементиран,
но јас ќе ја ставам врати на PowerPoint, така што можете да го напишете, ако сакате.
Значи за следните 5 минути или така, вие момци работат на Стави во ред
што е речиси токму спротивното од dequeue.
Вие не треба да се прилагоди главата кога сте enqueueing, но она што мора да се приспособат?
Големина. Па кога ќе Стави во ред, шеф останува недопрена, големината се пресоблекува.
Но тоа не се малку - ќе мора да се позанимавам со тоа МО
да дознаам што точно индекс новиот елемент треба да се вметнат во.
Затоа јас ќе ви даде момци малку, стави dequeue врати на слајд,
и како вие момци имате прашања, да им викне надвор, така што можеме да
сите зборуваат за нив како група.
Исто така, со големина don't - кога ќе се приспособи на големината, можете да секогаш само -
имаш да МО на големината некогаш? [Даниел] бр >> Вие не треба да МО на големината, нели.
Поради големината ќе и секогаш, ако Ти си - претпоставувајќи сте управување со работи соодветно,
големината секогаш ќе биде помеѓу 0 и 3.
Каде што треба да МО кога правиш Стави во ред?
[Студентски] Само за главата. >> Само за глава, точно.
И зошто треба да МО на сите во Стави во ред?
Кога е ситуација во која ќе треба да МО?
[Студентски] Ако имаш нешто во простори, како на простори 1 и 2,
а потоа ви се потребни за да додадете нешто на 0.
[Hardison] Да, точно. Значи, ако вашиот шеф покажувачот е на самиот крај,
или ако вашата големина плус вашата глава е поголема, или подобро кажано, се случува да се заврши околу задача.
>> Значи во оваа ситуација дека ние го добивме се тука на слајд токму сега,
ако сакам да Стави во ред нешто во право сега,
ние сакаме да Стави во ред нешто во индекс 0.
Значи, ако се погледне каде што 50 оди, и јас го нарекувам Стави во ред 50,
оди таму долу на дното. Тоа оди во индекс 0.
Тоа ја заменува "hi", која веќе беше dequeued.
[Даниел] Не се грижи за тоа во dequeue веќе?
Зошто го направи тоа нешто со главата во Стави во ред?
[Hardison] О, па вие не сте промената на главата, жалам.
Но вие мора да ја користи современи оператор кога ќе се пристапува
елементот што сакате да Стави во ред кога ќе бидете пристап
следниот елемент во вашата задача.
[Василиј] Јас не го стори тоа, и јас добив "успех" таму.
[Даниел] О, јас се разбере она што си ти што зборуваш.
[Hardison] Значи ти didn't - вие само не во q.size?
[Василиј] Да. Јас само смени страни, јас не направив ништо со глава.
[Hardison] Вие не всушност треба да го ресетирате главата да биде ништо,
но кога ќе индекс во низи низа,
вие всушност треба да оди напред и да се пресмета каде следниот елемент е,
бидејќи withe на магацинот, следниот елемент во вашиот магацинот секогаш беше
на индекс одговара на големината.
Ако ги погледнеме назад во нашата магацинот притисни функција,
ние секогаш може долар во нашиот нов елемент право на индекс големина.
А со задача, не можеме да го направи тоа
затоа што ако ние сме во оваа ситуација,
ако ние enqueued 50 нашиот нов стринг ќе одат право во низи [1]
што ние не сакаме да се направи.
Ние сакаме да имаме нов стринг одат во индекс 0.
>> Дали некој - да? [Студентски] Имам едно прашање, но тоа не е навистина поврзани.
Што значи тоа кога некој само го нарекува нешто како pred покажувачот?
Што е тоа име краток за? Знам дека е само името.
[Hardison] pred покажувачот? Ајде да видиме. Во она контекст?
[Студентски] Тоа беше за внесување. Можам да ве прашам подоцна ако сакате
бидејќи тоа не е навистина поврзани, но јас само -
[Hardison] Од вметнете код Давид од лекција?
Ние можеме да се повлече дека и зборува за тоа.
Ќе зборуваме за тоа следниот, штом ќе стигнете до поврзани листи.
>> Па ајде навистина брзо погледнеме во она што Стави во ред функција изгледа.
Што беше првото нешто што луѓето се обиделе да направите во вашиот Стави во ред линија? Во оваа задача?
Слични на она што го направи за магацинот туркање.
Што и да правите, Стела?
[Стела, неразбирливо]
[Hardison] Токму така. Ако (q.size == Капацитет) -
Јас треба да ставам протези на право место - се врати лажни.
Зум во малку. Во ред.
Сега она што е следното нешто што моравме да направам?
Исто како и со магацинот, и додава на вистинското место.
И така она што беше на право место да вметнете тоа?
Со оџакот беше индекс големина, со ова не е сосема тоа.
[Даниел] Имам q.head--или - >> q.strings? >> Да.
q.strings [q.head + q.size современи КАПАЦИТЕТ]?
[Hardison] Ние веројатно сакате да се стави загради околу ова
така што ние сме добивање на соодветен приоритет и така тоа е cleart за сите.
И го постави тоа еднакви? >> Да ул? >> Да ул. Велики.
И сега што е последното нешто што ние треба да направите?
Исто како што направивме во магацинот. >> Наголемува големината? >> Наголемува големина.
Бум. А потоа, откако стартер код само што се врати лажни по дифолт,
сакаме да ја промените оваа да важи ако се оди преку и се оди добро.
Во ред. Тоа е многу информации за секција.
Ние не сме сосема завршена. Ние сакаме да се зборува навистина брзо за одделно поврзани листи.
Јас ќе се стави ова горе за да можеме да се вратиме на тоа подоцна.
Но, да се вратиме на нашата презентација за само неколку слајдови.
Значи Стави во ред е TODO, сега ние сме го направиле.
>> Сега ајде да ги разгледаме во одделно поврзани листи.
Ние разговаравме за овие малку повеќе во предавање.
Како и многумина од вас момци видов демо каде што имаше луѓе
чудно што укажува на едни со други и одржување броеви? >> Бев во тоа.
>> Што ви момци мислите? Сторив тоа, се надевам демистифицира овие малку?
Со листа, излегува дека ние се справи со овој вид дека ние ќе треба да се јавите на јазол.
А со дното и на магацинот имавме structs дека ние би ја нарекол задача во магацинот,
имавме овие нови дното во магацинот видови,
тука список е навистина само составена од еден куп на јазли.
Во истиот начин на кој стрингови се само еден куп на карактери сите наредени една до друга.
А поврзани листа е само еден јазол и друг јазол и друг јазол и друг јазол.
И наместо кршејќи сите јазли заедно и складирање на нив contiguously
сите веднаш до едни со други во меморијата,
има следниот покажувачот ни овозможува да ги чувате јазли каде, по случаен избор.
А потоа вид на жица сите нив заедно за да се укаже од една до друга.
>> И она што беше голема предност што овој има над низа?
Над чување се contiguously само се држат до друг?
Се сеќаваш? Да? >> Динамички алокација на меморија?
>> Динамички алокација на меморија во која смисла?
[Студентски] Во таа може да се задржи што го прави поголеми и не треба да се движи вашата целата низа?
[Hardison] Токму така. Значи со низа, кога сакате да се стави нов елемент во средината на неа,
ќе треба да се сврти се за да се направи простор.
И како ние разговаравме за со задача,
тоа е причината зошто ние се задржи таа глава покажувач,
така што ние не сме постојано менување на нештата.
Затоа што тоа добива скапи ако имаш голема низа
и вие ќе бидете постојано прави овие случајни инсерции.
А со листа, сите што треба да направите е да се фрли на нов јазол,
прилагодување на покажувачи, и ќе завршиш.
Што смрди врска со ова?
Настрана од фактот дека тоа не е толку лесно да се работи со како низа? Да?
[Даниел] Па, претпоставувам дека тоа е многу потешко да пристапите специфичен елемент во поврзани листа?
[Hardison] Вие не може само да скокне до произволна елемент во средината на вашата поврзани листа.
Како ви треба да го направи тоа наместо неа? >> Мора да влезете низ целата работа.
[Hardison] Да. Треба да се оди преку едно по едно време, еден по еден.
Тоа е огромен - тоа е болката.
Што е другата - има уште една пропаст на ова.
[Василиј] Вие не може да оди напред и назад? Треба да се оди во една насока?
[Hardison] Да. Така како ние да се реши тоа, понекогаш?
[Василиј] двојно-поврзани листи? >> Токму така. Постојат двојно-поврзани листи.
Постојат, исто така, - е жал?
>> [Сем] Дали е тоа исто како употребувајќи го pred нешто што -
Јас само се сети, не е дека она што pred нешто е за?
Зарем тоа не е меѓу двојно и одделно?
[Hardison] Ајде да погледнеме во она што точно прави.
Значи тука ќе одиме. Тука е листа код.
Тука имаме predptr, тука. Дали е ова она што го зборуваш?
Значи ова беше - тој е ослободување на листа и тој се обидува да ја запази покажувач кон неа.
Ова не е двојно, поединечно поврзани листи.
Ние можеме да разговараме повеќе за ова подоцна, бидејќи ова се зборува за ослободување на листата
и сакам да покажам некои други нешта во прв план.
но тоа е само - тоа е сеќавајќи се на вредноста на кон меморија
[Студентски] О, тоа е preceeding покажувачот? >> Да.
Така што ние тогаш може прираст кон меморија себе пред да тогаш слободно она што predptr е.
Затоа што не е слободен кон меморија, а потоа може да се јавите кон меморија = кон меморија следната, нели?
Тоа би било лошо.
Да видиме, да се вратиме овој човек.
>> Од друга лоша работа за листи е дека додека со низа
ние само ги имаат сите елементи се наредени еден до друг,
тука ние исто така имаат воведено овој покажувач.
Значи има дополнителни парче на меморија, дека ние сме морале да користите
за секој елемент, дека ние сме чување во нашата листа.
Ние се флексибилност, но тоа доаѓа во цена.
Тоа доаѓа со овој пат цена,
и што доаѓа со оваа меморија цена е премногу.
Време во смисла дека ние сега треба да поминат низ секој елемент во низата
да се најде еден на индекс 10, или дека би биле индекс 10 во низа.
>> Само навистина брзо, кога ќе дијаграм на овие листи,
обично ние се одржи на чело на листата или прв покажувачот на листата
и напомене дека ова е вистински покажувач.
Тоа е само 4 бајти. Тоа не е вистински јазол себе.
Така што гледате дека нема int вредност во него, не следната покажувачот во него.
Тоа е буквално само покажувач.
Тоа се случува да се укаже на нешто што е вистински јазол struct.
[Сем] А покажувач кој се нарекува јазол? >> Ова е - не. Ова е покажувач кон нешто од типот јазол.
Тоа е покажувач кон еден јазол struct. >> О, во ред.
Дијаграмот на лево, кодот на правото.
Ние можеме да го поставите на нула, што е добар начин да се започне.
Кога ќе го дијаграм, можете или пишуваат како нула или ќе се стави линија преку тоа така.
>> Еден од најлесните начини да работат со списоци,
и ние ќе побара од вас да и ставете пред и додаваат за да ја видите разликите помеѓу двете,
но prepending е дефинитивно полесно.
Кога ќе ставете пред, ова е местото каде што - кога ќе ставете пред (7),
да одите и да се создаде јазол struct
и ќе се постави првиот да се укаже на тоа, бидејќи сега, бидејќи ние тоа prepended,
тоа ќе биде на почетокот на листата.
Ако ние ставете пред (3), кој создава друг јазол, но сега 3 доаѓа пред 7.
Па ние сме во суштина туркање работи кон нашата листа.
Сега, може да се види дека ставете пред, понекогаш луѓето го нарекуваат помогнам,
затоа што ти си туркаат нов елемент на вашиот список.
Тоа е исто така лесно да ја избришете на напред на листата.
Па луѓето често ќе се јавите дека поп.
И на тој начин, можете да емулира оџак користење на поврзани листа.
Whoops. За жал, сега ние сме добивање на додавај. Па овде prepended (7), сега ние ставете пред (3).
Ако ние prepended нешто друго врз оваа листа, ако ние prepended (4),
Тогаш би имале 4, а потоа 3 и потоа 7.
Па тогаш ние би можеле да pop и отстранете 4, отстранете 3, извадете 7.
Често повеќе интуитивен начин да се размислува за ова е со додавај.
Па јас diagrammed од она што ќе изгледа како со припојување тука.
Еве, дополнети (7) не изгледа поинаку
бидејќи има само еден елемент во листата.
И МЕНУВАЊЕ (3) го става на крајот.
Можеби може да се види токму сега трик со додавај
е дека, бидејќи ние знаеме само каде на почетокот на листата е,
да се додаде на листата мора да одат по целиот пат низ листата
да се дојде до крајот, да застане, а потоа се изгради на вашата јазол и бухвам се надолу.
Жица сите работи до.
Значи со ставете пред, како што само искинале преку ова навистина брзо,
кога ќе ставете пред да листа, тоа е прилично едноставна.
>> Вие направете ја вашата нова јазол, вклучуваат некои динамична алокација на меморија.
Значи тука правиме еден јазол struct користење Примерок.
Значи Примерок ние користиме затоа што тоа ќе издвои меморија за нас, за подоцна
бидејќи ние не сакаме тоа - ние сакаме оваа меморија да се истрае за долго време.
И ние се добие покажувачот на простор во меморијата дека ние само распределени.
Ние ги користиме големината на јазол, ние не сумира полиња.
Ние не рачно да генерира бројот на бајти,
наместо ние ги користиме sizeof, така што знаеме ние сме добивање на соодветен број на бајти.
Ние бидете сигурни дека за да го тестирате дека нашите Примерок повик успеа.
Ова е нешто што сакате да го направите во целина.
На современи машини, истекува на меморија не е нешто што е лесно
освен ако не сте распределба еден тон работи и прави огромна листа,
но ако сте градење нешто за, да речеме, како на iPhone или Андроид,
имате ограничен меморија ресурси, особено ако правиш нешто интензивна.
Така, тоа е добро да се добие во пракса.
>> Забележете дека јас сум користел неколку различни функции тука
дека сте виделе кои се вид на нов.
Значи fprintf е исто како printf
освен првиот аргумент е поток на кој сакате да се печати.
Во овој случај, ние сакаме да се печати стандардна грешка стринг
кој е различен од стандардниот outstream.
По дифолт тоа што се појавува на истото место.
Исто така, отпечатоци излез на терминал, но можете да -
користење на овие команди што го научиле за, редирекција техники
го научиле за во видео Tommy за проблемот сет 4, можете да го насочи
во различни области, а потоа излезете, токму тука, излегува вашата програма.
Тоа е суштински како се враќаат од главните,
освен ние ги користиме излез бидејќи тука се врати ќе не направи ништо.
Ние не сме во главната, па враќање не излезете од програмата како што сакаме.
Па ние ги користиме на излез функција и го даде грешка во кодот.
Потоа тука се постави вредност областа на новиот јазол, нејзините i поле, за да биде еднаква на i, а потоа го жица до.
Ние во собата следната покажувачот новиот јазол да се укаже прва,
а потоа првата сега ќе укажуваат на нов јазол.
Овие првите линии на код, ние сме всушност градењето на новиот јазол.
Не на последните две линии на оваа функција, но првите.
Ти всушност може да се повлече во функција, во помошна функција.
Тоа е често она што го правам е, јас го повлече во функција,
Јас го наречеме нешто како да се изгради јазол,
и дека го задржува ставете пред функција прилично мал, тоа е само 3 линии тогаш.
Јас се јавам на моите гради јазол функција, а потоа жица сè што.
>> Конечниот нешто што сакам да ти покажам,
и јас ќе ви овозможи да направите додавај и сето тоа на свој,
е како да iterate во текот на листата.
Постојат еден куп на различни начини да iterate во текот на листата.
Во овој случај, ние ќе треба да се најде должината на листата.
Значи ние започнуваме со должина = 0.
Ова е многу сличен на пишување strlen за низа.
Ова е она што сакам да ти покажам, ова за јамка овде.
Тоа изгледа kinda фанки, тоа не е вообичаениот int i = 0, I <што, i + +.
Наместо тоа иницијализацијата нашите променлива n да биде на почетокот на листата.
А потоа, додека нашите iterator променлива не е нула, ние продолжувам да одам.
Тоа е затоа што, од конвенцијата, на крајот на нашата листа ќе биде нула.
А потоа за зголемување, наместо да прави + +,
на поврзани листа еквивалент на + + е n = n-> следната.
>> Јас ќе те оставам да се пополнат празнините тука, бидејќи ние сме надвор од времето.
Но, имајте го ова на ум како што работат на вашиот spellr psets.
Поврзани листи, ако сте спроведување на хаш табелата,
дефинитивно ќе дојде во многу корисна.
И со тоа идиом за looping врз нештата ќе го направи животот многу полесно, се надевам.
Било какви прашања, брзо?
[Сем] Ќе испратиме заврши SLL и АД?
[Hardison] Да. Јас ќе испрати завршени слајдови и заврши SLL магацинот и queue.cs.
[CS50.TV]