[Musika nagpe-play]
David J. MALAN: Lahat ng karapatan.
Ito ay CS50.
Ito ay linggo limang nagpatuloy, at kami may ilang mga mabuting balita at ilang masamang balita.
Kaya mabuting balita ay na CS50 Ilulunsad ito Biyernes.
Kung nais mong sumali sa amin, magtungo sa karaniwan URL dito.
Kahit na mas mahusay na balita, walang mga panayam ito darating na Lunes ang ika-13.
Bahagyang mas mas mahusay na balita, pagsusulit zero ay sa susunod na Miyerkules.
Higit pang mga detalye ay maaaring maging makikita sa URL na ito dito.
At sa ibabaw ng susunod na dalawang araw ipapakita namin ma-pagpuno sa blangko
patungkol sa mga kuwarto na na nakalaan namin.
Mas mahusay na balita ay na mayroong idedetalye maging isang pagsusuri kurso-wide
session na ito darating Lunes sa gabi.
Manatiling nakatutok sa kurso ng website para sa lokasyon at mga detalye.
Mga seksyon, kahit na ito ay isang holiday, ay magkakaroon din ng matugunan pati na rin.
Pinakamahusay na mga balita, panayam sa tabi Biyernes.
Kaya ito ay isang tradisyon namin mayroon, tulad ng bawat ang syllabus.
Just-- ito ay magiging kahanga-hangang.
Makakakita ka ng mga bagay tulad ng pare-pareho ang panahon mga istraktura ng data
at hash table at mga puno at pagsusubok.
At kami makipag-usap tungkol sa mga problema sa kaarawan.
Ang isang buong bungkos ng mga bagay-bagay Naghihintay sa susunod na Biyernes.
OK.
Anyhow.
>> Kaya isipin na naging kami tumututok sa ang larawang ito ng kung ano ang
sa loob ng memorya ng aming computer.
Kaya memory o RAM ay kung saan programa umiiral habang nagpapatakbo ka ng mga ito.
Kung nag-double-click ang isang icon upang tumakbo ang ilang mga programa
o i-double-click ang isang na icon upang buksan ang ilang mga file,
ito ay load mula sa iyong hard humimok o solid estado biyahe
sa RAM, Random Access Memory, kung saan ito ay nabubuhay hanggang napupunta off ang kapangyarihan,
ang laptop panakip nagsasara, o lumabas ka sa program.
>> Ngayon na memorya, ng na marahil mayroon kang
1 gigabyte mga araw na ito, 2 gigabytes, o kahit na higit pa,
ay karaniwang inilatag out para sa isang naibigay na programa
sa ganitong uri ng hugis-parihaba pangkonseptong modelo
kung saan mayroon kaming ng stack sa ibaba at isang bungkos ng iba pang mga bagay-bagay sa itaas.
Ang mga bagay sa tuktok napaka nasaksihan namin sa larawan na ito
bago ngunit hindi usapan tungkol sa ay ang tinatawag na segment ng teksto.
Segment ng Teksto lamang ang magarbong paraan ng sinasabi ng mga zero at mga na
sumulat ng iyong aktwal na pinagsama-sama program.
>> Kaya kapag nag-double-click Microsoft Word sa iyong Mac o PC,
o kapag nagpatakbo ka ng tuldok iwa Mario sa isang Linux computer sa iyong terminal na window,
ang mga zero at mga na gumawa ng sulat Word o Mario ay pansamantalang naka-imbak
sa RAM ng iyong computer sa gayon tinatawag na segment ng teksto para sa isang partikular na programa.
Sa ibaba na napupunta nasimulan at uninitialized data.
Ito ay mga bagay-bagay tulad ng mga pangkalahatang variable, na hindi na namin ginagamit ang marami sa,
ngunit sa okasyon hindi namin Nagkaroon mga pangkalahatang variable
o statically tinukoy na string mahirap ay naka-code na mga salita gaya ng "kumusta"
na hindi na kinunan sa mula sa gumagamit na ang na hard-code sa iyong programa.
>> Ngayon, down sa ibaba namin mayroon ng tinatawag na stack.
At ng stack, kaya sa ngayon, naging kami gamit para sa kung ano ang mga uri ng mga layunin?
Ano ang mga stack na ginagamit para sa?
Oo?
>> Madla: Mga Pag-andar.
>> David J. MALAN: Para sa mga pag-andar?
Sa anong mga kahulugan para sa mga pag-andar?
>> Madla: Kapag tumawag ka ng isang function, ang mga argument ay kinopya papunta sa stack.
>> David J. MALAN: Eksaktong.
Kapag tumawag ka ng isang function, nito mga argument ay kinopya papunta sa stack.
Kaya ang anumang mga X o Y o A o B na kayo ay pagpasa sa isang function
Pansamantalang ilagay sa ng tinatawag na stack,
tulad lamang ng isa sa mga Annenberg dining hall trays, at din bagay
tulad ng mga lokal na variable.
Kung ang iyong foo function na o ang iyong swap May mga lokal na variable function,
tulad ng Temp, ang dalawang napupunta sa stack.
Ngayon, hindi namin makipag-usap ng masyadong maraming tungkol sa ang mga ito, ngunit ang mga variable na kapaligiran
sa ilalim Nakita namin ang isang habang ang nakalipas kapag Ako ay futzing sa keyboard ng isang araw
at sinimulan ko pag-access sa mga bagay tulad ng argv 100 o argv 1,000,
lamang elements-- ko makalimutan ang numbers-- ngunit na
ay hindi dapat na ma-access sa pamamagitan ng akin.
Sinimulan na naming nakikita ang ilang mga funky mga simbolo sa screen.
Yaong ay tinatawag na kapaligiran variable
tulad ng mga setting ng global para sa aking programa o para sa aking computer, hindi
hindi nauugnay sa kamakailang bug na namin tinalakay,
Shellshock, na naging plaguing lubos ng ilang mga computer.
>> Ngayon Panghuli, sa focus ngayong araw magpapadala kami sa huli nasa heap.
Ito ay isa pang chunk ng memorya.
At fundamentally ang lahat ng ito memorya ay pareho bagay-bagay.
Ito ay ang parehong hardware.
Humihingi kami lamang ang uri ng pagpapagamot ng iba't ibang mga kumpol
ng mga byte na para sa iba't ibang mga layunin.
Heap Ang Pupunta rin upang maging kung saan variable at memory na hiniling mo
mula sa operating system Pansamantalang naka-imbak.
>> Ngunit mayroong uri ng problema dito, pati na nagpapahiwatig sa larawan.
-Uri-uriin kami ng may dalawang ships tungkol sumalungat.
Dahil habang ginagamit mo ang higit pa at higit pa ng stack, at bilang ating nakikita ngayon
pasulong, habang ginagamit mo ang higit pa at higit pa sa mga heap, tiyak masamang bagay na maaaring mangyari.
At sa katunayan, maaari naming humimok na sinasadya o hindi sinasadyang.
Kaya ang cliffhanger huling oras ay program na ito,
na hindi maghatid ng anumang functional layunin na iba sa upang ipakita
kung paano mo bilang isang masamang tao ay maaaring aktwal na tumagal bentahe ng mga bug programa ng isang tao sa
at angkinin ang isang programa o kahit isang buong sistema ng computer o server.
Kaya lang sa sulyap panandalian, ikaw mapapansin na ang pangunahing sa ibaba
tumatagal sa command line mga argument, bilang bawat argv.
At ito ay isang tawag sa isang function f, mahalagang isang nameless function na tinatawag na
f, at ito ay ang pagpasa sa argv [1].
>> Kaya kahit anong salita uri ng user sa sa ang prompt pagkatapos ng pangalan ng programa na ito,
at pagkatapos ay ang di-makatwirang pag-andar up tuktok, f, tumatagal sa isang string, aka char *,
bilang sinimulan namin ang pag-usapan, at pagtawag ito lang ito "bar."
Ngunit maaari naming tumawag ito ng kahit ano.
At pagkatapos nito declares, sa loob ng f, isang array ng mga character
na tinatawag na c-- 12 tulad character.
>> Ngayon, sa pamamagitan ng mga kuwento ako ay nagsasabi sa ng ilang sandali ang nakalipas, kung saan sa memory
ay c, o ay ang mga 12 char ng pagpunta sa mga end up?
Lamang na maging malinaw.
Oo?
>> Madla: Sa stack.
>> David J. MALAN: Sa stack.
Kaya c ay isang lokal na variable.
Kami ay humihingi ng 12 na karakter o 12 bytes.
Yaong ay pagpunta sa mga end up sa tinatawag na stack.
Ngayon sa wakas ay ang iba pang mga pagpapaandar na talagang kaakit-akit na kapaki-pakinabang,
ngunit kami ay hindi talaga ginamit ito ang ating mga sarili, strncopy.
Ito ay nangangahulugan string na kopya, ngunit lamang n titik, n character.
Kaya n character ay magiging kinopya mula sa bar sa c.
At kung gaano karaming?
Ang haba ng bar.
Kaya sa ibang salita, na isang linya, strncopy,
ay pagpunta sa kopyahin epektibong humadlang in sa c.
>> Ngayon, lamang sa uri ng inaasahan mga kapakanang moral ng mga kuwentong ito,
ano ang potensyal na problema dito?
Kahit na kami ay check ang haba ng bar at pagpasa ito sa strncopy,
kung ano ang iyong GUT na nagsasabi sa iyo ay sira pa rin tungkol sa programang ito?
Oo?
>> Madla: ba ang hindi isama room para sa mga null character.
David J. MALAN: Hindi kinabibilangan ng room para sa mga null character.
Potensyal na, hindi tulad ng sa nakalipas na kasanayan hindi namin kahit na
may kaya magkano ang bilang ng plus 1 hanggang tumanggap na null character.
Pero kahit na mas masahol kaysa iyon.
Ano pa ang bagsak namin upang gawin?
Oo?
>> Madla: [INAUDIBLE]
David J. MALAN: Perpekto.
Mahirap na naka-code na namin 12 medyo nagkataon.
Iyon ay hindi kaya magkano ang problema, ngunit ang katotohanan
na hindi man lamang namin ang pagsuri kung ang haba ng bar ay mas mababa sa 12,
sa kasong ito ay magiging Ligtas na ilagay ito papunta sa memorya ng
tinatawag c na nai-inilalaan namin.
Sa katunayan, kung ang bar ay tulad ng 20 character ang haba,
Lumilitaw na ito ang function na pagkopya 20 na mga character mula sa bar c, at sa gayon
pagkuha ng hindi bababa sa 8 bytes na hindi ito ay kailangang maging.
Iyan ang implikasyon dito.
>> Kaya sa maikling, putol na programa.
Hindi tulad ng isang malaking deal.
Siguro kang makakuha ng segmentation fault.
Na ang lahat Nagkaroon kami ng mga bug sa programa.
Namin ang lahat ng maaaring mayroon bug sa mga programa sa ngayon.
Ngunit kung ano ang mga implikasyon?
Well, narito ang isang naka-zoom-in na bersyon ng na larawan ng memorya aking computer.
Ito ay sa ilalim ng aking stack.
At sa katunayan, sa ilalim napaka ay kung ano ang tinatawag magulang routine stack, magarbong paraan
ng na nagsasabi na ang pangunahing.
Kaya kung sinuman na tinatawag na ang pag-andar f na pinag-uusapan natin ang tungkol.
Kaya ito ay sa ilalim ng stack.
Return address ay isang bagong bagay.
Palaging Naging doon, palagi nang naging sa na larawan.
Kami ay hindi kailanman lamang na tinatawag na pansin sa mga ito.
Dahil ito ay lumiliko out ang paraan kung paano gumagana c ay na kapag tawag isa-andar sa isa pa,
hindi lamang gawin ang mga argument na iyon function na makakuha ng matutulak papunta sa stack,
hindi lamang gawin lokal na ang pag-andar ng variable makakuha matutulak papunta sa stack,
isang bagay na tinatawag na return address din ay makakakuha ilagay papunta sa stack.
Sa partikular, kung pangunahing tawag foo, ang pangunahing ng sariling address sa memory, baka may isang bagay,
mabisa ay makakakuha ilagay papunta sa stack upang kapag f tapos na e-execute ito
alam kung saan upang lumipat pabalik sa sa teksto segment upang magpatuloy na e-execute.
>> Kaya, kung hindi kami dito conceptually, sa pangunahing, pagkatapos ay makakakuha ng f tinatawag.
Paano gumagana ang f malalaman kung sino ang sa kamay control pabalik?
Well, ito kaunti breadcrumb sa pula dito,
na tinatawag na ang return address, ito lamang pagsusuri, ano ang na return address?
Oh, hayaan mo akong lumipat pabalik sa pangunahing dito.
At iyon ang ilang sandali ng isang oversimplification,
dahil ang mga zero at mga para sa pangunahing ay technically
hanggang dito sa tech segment.
Ngunit iyon lamang ang mga ideya. f lamang ay may upang malaman kung ano
upang kung saan kontrol sa huli napupunta bumalik.
>> Subalit ang paraan computer na mahaba inilatag nang mga bagay
tulad ng lokal na mga variable at mga argument ay tulad nito.
Kaya sa tuktok ng larawan na ito sa asul ay ang stack frame para sa f, kaya ang lahat ng
ng memorya na f partikular na ay ginagamit.
Kaya nang naaayon, mapapansin na ang bar ay sa larawan na ito.
Bar ay argumento nito.
At namin na-claim na mga argumento upang mga function makakuha matutulak papunta sa stack.
At c, siyempre, ay sa larawan na ito din.
>> At para lamang sa mga layuning notational, mapansin sa kaliwang tuktok na sulok
ay kung ano ang magiging c bracket 0 at pagkatapos ay bahagyang pababa sa kanan
ay c bracket 11.
Kaya sa ibang salita, maaari mong isipin na mayroong isang grid ng mga byte
doon, una sa kung saan ay kaliwang tuktok, sa ilalim ng kung aling mga
ay ang huling ng mga 12 bytes.
>> Ngunit ngayon subukang i-fast forward.
Ano ang tungkol sa mangyayari kung pumasa namin sa isang string bar na mas mahaba kaysa c?
At hindi namin Sinusuri kung ito ay sa katunayan mas mahaba kaysa sa 12.
Aling mga bahagi ng larawan na ito ay pagpunta sa makakuha-o-overwrite sa pamamagitan ng mga byte 0, 1, 2, 3,
tuldok tuldok tuldok, 11, at pagkatapos ay masamang, 12, 13 sa pamamagitan ng 19?
Ano ang nangyayari sa mangyari dito, kung infer ka mula sa pag-order
na c bracket 0 ay nasa tuktok at c bracket 11 ay isang uri ng pababa
sa kanan?
Oo?
>> Madla: Well, ito ay pagpunta patungan ang mga char * bar.
>> David J. MALAN: Oo, mukhang ka ng pagpunta sa patungan char * bar.
At mas masahol pa, kung magpadala sa iyo sa isang talagang mahaba string, maaari mong patungan kahit ano?
Ang return address.
Aling muli, ay tulad ng isang breadcrumb upang sabihin sa programa kung saan ang
upang bumalik sa kapag f tapos na tinatawag.
>> Kaya kung ano ang karaniwang gawin masamang guys ay kung dumating sila sa isang programa
na sila malaman kung ay exploitable, mayroong bug sa paraang
na siya ay maaaring tumagal ng Samantalahin ang na bug,
Sa pangkalahatan ay hindi sila makakuha ng karapatang ito sa unang pagkakataon.
Simulan lang nila ang pagpapadala ng, halimbawa, random na string sa iyong programa,
kung sa keyboard, o tapat nila marahil
magsulat ng isang maliit na programa sa makatarungan awtomatikong bumuo ng mga string,
at simulan ang banging sa iyong programa sa pamamagitan ng pagpapadala sa maraming iba't ibang input
sa iba't ibang mga haba.
>> Sa sandaling ang iyong mga pag-crash ng programa, na ang isang kamangha-manghang mga bagay.
Dahil ito ay nangangahulugan na siya o siya ay natuklasan
kung ano ay marahil sa katunayan ng isang bug.
At pagkatapos ay maaari nilang makakuha ng higit pang matalino at simulan ang tumututok sa higit pang makitid
kung paano samantalahin na bug.
Sa partikular, kung ano siya ay maaari gawin ay magpadala ng, sa pinakamahusay na kaso, kumusta.
Walang malaking deal.
Ito ay isang string na may sapat na maikli.
Ngunit kung ano kung siya ay nagpapadala, at kami ng tuntuning panlahat ito bilang,
pag-atake code-- kaya zero at mga bago na gumawa ng mga bagay
tulad ng Rm-rf, na alisin ang lahat ng bagay mula sa hard drive o magpadala ng spam
o kahit papaano inaatake ang machine?
>> Kaya kung bawat isa sa mga mga titik A lamang ay kumakatawan,
conceptually, pag-atake, pag-atake, pag-atake, pag-atake, ang ilang mga masamang code
na may ibang tao na sinulat, ngunit kung ang taong iyon ay sapat na smart
hindi lamang isama ang lahat ng ng mga Rm-rfs, kundi pati na rin
mayroon kanyang huling ilang mga byte ay isang numero na tumutugon
sa address ng kanyang o ang kanyang sariling pag-atake code
na siya ang pumasa sa mga in lamang sa pamamagitan ng pagbibigay ito sa prompt,
mabisa mong linlangin ang computer sa makapansin kapag f tapos na e-execute,
naku, oras na para sa akin upang lumaktaw pabalik sa pulang return address.
Ngunit dahil siya ay may kahit papaano overlapped na return address
sa kanilang sariling mga numero, at ang mga ito ay sapat na smart
sa na-configure na numero na mag-refer, tulad ng sa iyo
makita sa sobrang tuktok kaliwang sulok doon,
ang aktwal na address sa computer memorya ng ilan sa kanilang mga pag-atake code,
Maaari linlangin ang isang masamang tao ang computer sa pagpapatupad sa kanyang sariling code.
>> At ang code na iyon, muli, ay maaaring maging kahit ano.
Sa pangkalahatan ito ay tinatawag na shell code, na lamang
isang paraan ng pagsabi na hindi kasing simple ng Rm-rf pangkalahatan ay isang bagay.
Ito ay talagang isang bagay tulad Bash, o isang aktwal na programa na nagbibigay sa kanya
o ang kanyang control program upang maisagawa anumang bagay na nais nilang.
Kaya sa maikling, ito ang lahat ng derives mula sa simpleng katotohanan
ang bug na ito kasangkot hindi pagsuri ang mga hangganan ng iyong array.
At dahil sa paraan ng mga computer sa trabaho ay na sila
gamitin ang stack mula sa mabisa, conceptually,
ibaba sa up, ngunit pagkatapos ay ang elemento itulak mo papunta sa stack na palaguin itaas pababa,
ito ay hindi kapani-paniwalang may problemang.
Ngayon, may mga paraan upang gumawa sa paligid ito.
At tapat, may mga wika kung saan upang gumawa sa paligid ito.
Java ay immune, halimbawa, sa partikular na isyu.
Dahil wala silang magbigay sa iyo ng payo.
Hindi nila magbibigay sa iyo ng direct memory address.
Kaya may mga kapangyarihan na ito na mayroon kami galawin ng kahit ano sa memorya
kami ay nais, admittedly, mahusay na panganib.
>> Kaya abangan.
Kung, tapat, sa mga buwan ng o taon na dumating, anumang oras
basahin mo ang tungkol sa ilang pagsasamantala ng isang programa o ng isang server,
kung kailanman nakakita ka ng isang pahiwatig ng isang bagay tulad ng isang buffer overflow atake,
o stack overflow ay isa pang uri ng pag-atake, katulad sa espiritu,
magkano bilang inspirasyon ng website pangalanan, kung alam mo ito,
lahat ng ito ay tungkol sa pakikipag-usap lamang overflowing ang laki ng ilang mga karakter
array o ilang array sa mas pangkalahatang paraan.
Ang anumang mga katanungan, pagkatapos, sa ito?
Huwag subukan ito sa bahay.
>> Lahat ng karapatan.
Kaya malloc kaya ngayon ay naging aming bagong kaibigan na maaari naming maglaan ng memorya
na hindi naman namin alam kung sa sumulong na gusto naming kaya wala kaming
sa hard code sa aming mga numero ng programa tulad ng 12.
Sa sandaling Sinasabi sa amin ang user kung magkano data siya ay nais na input,
maaari naming malloc na maraming memorya.
>> Kaya malloc ito ay lumiliko out, sa lawak namin na ginagamit mo ito,
tahasan huling beses, at pagkatapos ay ka guys ay nai-gamit ito
para sa getstring hindi-para sa ilang mga linggo, ang lahat ng memory malloc ni
ay mula sa tinatawag na heap.
At ito ang dahilan kung bakit getstring, halimbawa, Maaari maglaan ng memorya pabagu-bagong
nang walang pag-alam kung ano ang iyong pagpunta sa i-type nang maaga,
ipasa mo pabalik tagaturo patungo sa na memorya, at na memory ay sa iyo pa rin upang panatilihin,
kahit na matapos getstring babalik.
Dahil pagpapabalik pagkatapos ng lahat na ang stack ay patuloy na pagpunta pataas at pababa,
pataas at pababa.
At sa lalong madaling pumupunta ito pababa, na nangangahulugang anumang memory
ginagamit ang pagpapaganang ito dapat hindi dapat gamitin ng sinumang iba pa.
Ito ay ngayon ang mga halaga ng basura.
>> Subalit ang heap ay up dito.
At kung ano ang magaling tungkol sa malloc ay na kapag malloc naglalaan ng memory up dito,
hindi ito naapektuhan, para sa nakararaming bahagi, sa pamamagitan ng stack.
At nang sa gayon ay ma-access ang anumang mga pag-andar memory na na-malloc'd,
kahit na sa pamamagitan ng isang function tulad getstring, kahit na ito ay ibinalik.
>> Ngayon, ang usap ng malloc ay libre.
At sa katunayan, ang panuntunan mo kailangan upang simulan ang pagpapatibay
ay anumang, anumang, anumang oras na gamitin mo malloc Dapat mo ang iyong sarili gamitin ang libreng, sa huli,
sa na parehong pointer.
Ang lahat ng mga oras na ito tayo ay sumusulat mayroong bug, mayroong bug code, para sa maraming mga dahilan.
Ngunit isa sa kung saan ay gamit ang CS50 library, na
mismo ay sadyang mayroong bug, paglabas nito memorya.
Anumang oras na iyong na tinatawag na getstring sa nakalipas na ilang linggo
hinihiling namin sa operating system, Linux, para sa memorya.
At mo pa kailanman sa sandaling naibigay na ito pabalik.
At hindi ito, sa pagsasanay, isang magandang bagay.
>> At Valgrind, isa sa mga mga tool ipinakilala sa Pset 4,
ay tungkol sa pagtulong sa iyo na ngayon ang bug tulad na.
Ngunit thankfully para sa Pset 4 hindi mo kailangang gamitin ang CS50 library o getstring.
Kaya ang anumang mga bug na may kaugnayan sa memorya ay sa huli pagpunta upang maging iyong sarili.
>> Kaya malloc ay higit pa sa maginhawa para sa layuning ito.
Maaari aktwal na namin ngayon malutas fundamentally iba't ibang mga problema,
at fundamentally malutas ang problema nang higit pa epektibo tulad ng bawat linggo pangako ng zero.
Kaya ngayon ito ay ang sexiest istraktura ng data mayroon kaming.
At sa pamamagitan ng istraktura ng data ibig sabihin ko lang isang paraan ng conceptualizing memory
sa isang paraan na napupunta lampas lamang sinasabi, ito ay isang int, ito ay isang char.
Maaari naming magsimula sa kumpol ng mga bagay nang magkakasama.
>> Kaya isang array ay tumingin tulad nito.
At kung ano ang key sa tungkol sa isang array ay tumutulong ito ay nagbibigay sa iyo
back-to-pabalik chunks ng memorya, ang bawat isa
ay magiging ng parehong uri, int, int, int, int, o char, char, char,
char.
Ngunit mayroong ilang mga downsides.
Ito halimbawa, ay isang hanay ng mga laki ng anim.
Ipagpalagay mong punan ito ng array na may anim na mga numero at pagkatapos ay, para sa anumang kadahilanan,
Nais ng iyong mga gumagamit upang bigyan ikaw 1/7 numero.
Saan mo ilagay ito?
>> Ano ang solusyon kung mayroon kang Nalikha ang isang array sa stack,
halimbawa, sa pamamagitan lamang ng linggo dalawang pagtatanda na ipinakilala namin,
ng mga square bracket na may isang numero sa loob?
Well, mayroon ka ng anim na mga numero sa mga kahon.
Ano ang gusto maging iyong instincts?
Saan ninyo gustong ilagay ito?
>> Madla: [INAUDIBLE]
>> David J. MALAN: Paumanhin?
>> Madla: Ilagay ninyo sa dulo.
>> David J. MALAN: Ilagay ninyo sa dulo.
Kaya sa ibabaw lamang sa kanan, sa labas ng ang kahon na ito.
Aling ay magiging maganda, ngunit ito lumiliko out hindi mo maaaring gawin iyon.
Dahil kung hindi mo hiniling para sa chunk ng memorya,
maaaring ito ay sa pamamagitan ng pagkakataon na ito ay ginagamit sa pamamagitan ng ilang iba pang mga variable
nang sama-sama.
Isipin pabalik sa isang linggo o kaya kapag inilatag namin out Zamyla at Davin at Gabe ng mga pangalan
sa memory.
Sila ay literal pabalik upang i-back sa likod.
Kaya hindi namin maaari kinakailangan pinagkakatiwalaan na kung ano ang
sa paglipas dito ay magagamit para sa akin upang gamitin.
>> Kaya ano pa ang maaari mong gawin?
Well, sa sandaling napagtatanto mo Kailangan ng isang hanay ng mga laki ng pitong,
maaari mo lamang lumikha ng isang na hanay ng mga sukat ng pitong pagkatapos ay gamitin ang
isang para sa loop o isang habang loop, kopyahin ito sa bagong array,
at pagkatapos ay kahit papaano lamang mapupuksa ang ito array itigil o lamang na gamitin ito.
Ngunit iyon lamang ang hindi partikular na mahusay.
Sa maikli, array huwag mong pabayaan dynamic na baguhin mo ang sukat.
>> Kaya sa isa kamay kang makakuha ng random na pag-access, na kung saan ay kamangha-manghang.
Dahil nagbibigay-daan ito sa amin gawin ang mga bagay tulad ng hatiin at lupigin,
binary paghahanap, ang lahat ay hindi namin usapan tungkol sa screen dito.
Ngunit mo ipinta ang iyong sarili sa isang sulok.
Sa sandaling pindutin mo sa dulo ng iyong array,
kailangan mo lang gawin ng isang napaka mahal na operasyon
o magsulat ng isang buong bungkos ng code sa ngayon haharapin ang mga problema na iyon.
>> Kaya kung ano kung sa halip ay may namin isang bagay na tinatawag na isang listahan,
o ng isang listahan na naka-link sa mga partikular na?
Paano kung sa halip ng pagkakaroon ng parihaba para i-back upang i-back upang i-back,
mayroon kaming mga parihaba na mag-iwan ng kaunti bit ng wiggle room sa pagitan ng mga ito?
At kahit na iginuhit ko na ito larawan o inangkop ang larawang ito
mula sa isa sa ang mga teksto dito upang maging pabalik sa pabalik upang i-back napaka maayos, sa katotohanan,
isa sa mga parihaba Maaaring maging hanggang dito sa memorya.
Ang isa sa mga ito ay maaaring maging hanggang dito.
Ang isa sa mga ito ay maaaring magkaroon ng hanggang dito, sa paglipas dito, at iba pa.
>> Ngunit paano kung iginuhit namin, sa kasong ito, mga arrow
na kahit papaano i-link ang mga parihaba magkasama?
Sa katunayan, nasaksihan namin ang isang teknikal na incarnation ng isang arrow.
Ano pa namin ginamit sa kamakailang araw na iyon, sa ilalim ng hood,
ay kinatawan ng isang arrow?
Ang isang pointer, tama?
>> Kaya kung ano kung, sa halip ng pag-iimbak lamang ang mga numero,
tulad ng 9, 17, 22, 26, 34, paano kung namin na naka-imbak hindi
lamang ng isang numero ngunit isang pointer sa tabi ng bawat tulad number?
Kaya na halos tulad ng gusto mo thread ng karayom ​​sa pamamagitan ng isang buong bungkos ng tela,
kahit papaano tying bagay nang sama-sama, maaari kaparehong
namin na may mga payo, pati na incarnated sa pamamagitan ng mga arrow dito,
uri ng weave magkasama ang mga indibidwal na mga parihaba
sa pamamagitan ng epektibong paggamit ng isang pointer sa tabi ng bawat numerong iyon
tumuturo sa ilang mga susunod na numero, na tumuturo, siya namang, ang ilang mga susunod na numero?
Kaya sa ibang salita, kung ano ang kung gusto naming aktwal
upang ipatupad ang isang bagay tulad na ito?
Well sa kasamaang-palad, ang mga ito ng mga parihaba, hindi bababa sa isa sa 9, 17, 22,
at iba pa, ang mga ito ay hindi na Ang ganda ng mga parisukat na may iisang numero.
Ang ibaba, parihaba 9 sa ibaba, halimbawa,
kumakatawan sa kung ano ang dapat maging isang pointer, 32 bits.
Ngayon, hindi ako pa kamalayan sa anumang uri ng data sa C na nagbibigay sa iyo ng hindi lamang sa isang int
ngunit isang pointer nang sama-sama.
>> Kaya ano ang solusyon kung gusto namin upang imbentuhin ating sariling sagot sa ito?
Oo?
>> Madla: [INAUDIBLE]
>> David J. MALAN: Ano iyon?
>> Madla: Bagong istraktura.
>> David J. MALAN: Oo, kaya bakit huwag kaming lumikha ng bagong istraktura,
o sa C, ang isang struct?
Nakakita kami structs bago, kung panandalian, kung saan kami Aaksyunan isang mag-aaral ng istraktura
tulad nito, sino ay nagkaroon ng isang pangalan at isang bahay.
Sa Pset 3 breakout na ginamit mo sa kabuuan bungkos ng structs-- GRect at GOvals
Stanford na nilikha sa cluster impormasyon nang magkakasama.
Kaya kung ano kung gagawin namin ito parehong ideya ng ang mga keyword na "typedef" at "struct,"
at pagkatapos ay ang ilang mga bagay-bagay mag-aaral na tukoy, at magbabago ito sa mga sumusunod:
typedef struct node-- at node ay lamang ng isang napaka generic computer science
termino para sa isang bagay sa isang istraktura ng data, isang lalagyan sa isang istraktura ng data.
Ang isang node inaangkin ko ay pagpunta sa may isang int n, ganap prangka,
at pagkatapos ng kaunti pa cryptically, ito pangalawang linya, struct node * susunod.
Ngunit sa mas teknikal na mga termino, ano ay ang pangalawang linya
ng code sa loob ng kulot braces?
Oo?
>> Madla: [INAUDIBLE]
David J. MALAN: Isang pointer sa isa pang node.
Kaya admittedly, syntax ng kaunti cryptic.
Ngunit kung ito na basahin mo literal, susunod ay ang pangalan ng isang variable.
Ano ang uri nito data?
Ito ay isang maliit na verbose oras na ito, subalit ito ay uri ng struct node *.
Anumang oras na nakakita kami ng isang bagay na bituin, na Ang ibig sabihin ito ay isang pointer sa na uri ng data.
Kaya susunod ay tila isang pointer sa isang struct node.
>> Ngayon, kung ano ay isang struct node?
Well, napansin makita mo ang mga parehong salita sa kanang itaas.
At sa katunayan, mo ring makita ang mga salita "Node" down na dito sa kaliwang ibaba.
At ito ay tunay na isang kaginhawahan lamang.
Pansinin na sa aming kahulugan ng mag-aaral may mga salitang "mag-aaral" isang beses lamang.
At iyon ay dahil sa isang mag-aaral object ay hindi self-referential.
Wala sa loob ng isang mag-aaral ay na kailangan upang tumuro sa isa pang mag-aaral,
persay.
Iyon ay magiging isang uri ng kakaiba sa tunay na mundo.
>> Ngunit sa isang node sa isang naka-link listahan, binabasa namin gusto ang isang node
upang maging referential sa isang katulad na bagay.
At kaya mapapansin ang pagbabago dito ay hindi kung ano lamang ang nasa loob ng mga kulot braces.
Subalit idagdag namin ang salitang "node" sa pati na rin ang tuktok
pagdaragdag nito sa ibaba sa halip ng "mag-aaral."
At ito ay lamang ng isang teknikal na detalye kaya iyon, muli, ang iyong mga istraktura ng data
ay maaaring maging self-referential, kaya na ang isang na node ay maaaring tumuro sa isa pang katulad na node.
>> Kaya kung ano ito sa huli pagpunta sa ibig sabihin para sa amin?
Well, isa, mga bagay na ito sa loob ng ay ang mga nilalaman ng aming mga node.
Bagay na ito ng hanggang dito, kanang tuktok, sa gayon ay lamang
na iyon, muli, maaari naming sumangguni sa ating sarili.
At pagkatapos ay ang outermost bagay-bagay, kahit na node ay isang bagong term,
marahil, ito ay pa rin ang katulad ng mag-aaral at kung ano ang
ay sa ilalim ng hood sa SPL.
>> Kaya kung gusto naming ngayon upang simulan pagpapatupad na ito na naka-link listahan,
paano maaari naming isalin isang bagay na tulad nito sa code?
Well, sabihin makita ni lamang ng isang halimbawa ng isang programa na
talaga ay gumagamit ng isang naka-link na listahan.
Kabilang sa pamamahagi code ngayong araw ay isang programa na tinatawag na Listahan Zero.
At kung nagpatakbo ako ng ito nilikha ko ang isang napakabilis simpleng GUI, Graphical User Interface,
ngunit ito ay talagang lamang printf.
At ngayon Ibinigay ko sa sarili ko ng ilang menu options-- Tanggalin, Insert, Paghahanap,
at Traverse.
At quit.
Ang mga ito ay karaniwang lamang pagpapatakbo sa isang istraktura ng data na kilala bilang isang listahan ng link.
>> Ngayon, Tanggalin ang pagpunta sa tanggalin ang isang numero mula sa listahan.
Ipasok ang nangyayari upang magdagdag ng isang numero sa listahan.
Paghahanap ay pagpunta sa tumingin para sa numero sa listahan.
At traverse lamang magarbong paraan ng sinasabi, maglakad sa pamamagitan ng mga listahan,
i-print ito, ngunit iyan ay ito.
Huwag baguhin ito sa anumang paraan.
>> Kaya sabihin subukan ito.
Sabihin sige at i-type 2.
At pagkatapos ay pupuntahan ko ipasok ang numero ng, sabihin nating 9.
Ipasok.
At ngayon ang aking programa lamang -program upang sabihin, listahan 9 na ngayon.
Ngayon, kung pumunta ako magpatuloy at huwag Ipasok ang muli, sabihin
sa akin sige at mag-zoom out at i-type sa 17.
Ngayon aking listahan ay 9, pagkatapos ay 17.
Kung gagawin ko ipasok muli, ay laktawan ang isa ipaalam.
Sa halip na 22, bilang bawat ang larawan hindi namin hinahanap-hanap sa dito, hayaan mo akong tumalon nang mas maaga
at magpasok ng 26 susunod.
Kaya pupuntahan ko type 26.
Ang listahan ay tulad ng iyong inaasahan ko.
Ngunit ngayon, upang makita lamang kung ang code na ito ay magiging may kakayahang umangkop, ipaalam sa akin ngayon
uri 22, na hindi bababa sa conceptually, kung hindi kami
ito pinagsunod-sunod pagpapanatiling, na kung saan ay sa katunayan pagpunta sa maging sa ngayon isa pang layunin,
dapat pumunta sa pagitan ng 17 at 26.
Kaya hit ko ang Enter.
Sa katunayan, na gumagana.
At kaya ngayon hayaan mo akong ipasok ang huling, alinsunod sa mga larawang ito, 34.
>> Lahat ng karapatan.
Kaya para sa ngayon hayaan mo akong stipulate na Tanggalin at Traverse at Paghahanap gawin,
sa katunayan, gumana.
Sa katunayan, kung ako magpatakbo ng Paghahanap, sabihin maghanap para sa numerong 22, ang Enter.
Nag nahanap 22.
Kaya iyon ay kung ano ito Listahan ng programa Zero ang gumagana.
>> Ngunit kung ano ang aktwal na pagpunta sa na ipinapatupad ito?
Well, una maaaring mayroon ako, at sa katunayan Akong, isang file na tinatawag list0.h.
At sa isang lugar sa may ito linya, typedef, struct node,
pagkatapos ay mayroon ko ang aking kulot braces, int n, at pagkatapos struct-- kung ano ang naging kahulugan?
Struct node susunod.
Kaya kailangan namin ng mga bituin.
Ngayon technically makuha namin sa ang ugali ng pagguhit ng ito dito.
Maaari kang makakita ng mga aklat-aralin at online na mga sanggunian ito gagawin doon.
Ito ay katumbas sa pagtakbo.
Sa katunayan, ito ay isang kaunti pa tipikal.
Ngunit kukunin ko na maging pare-pareho sa kung ano ginawa namin huling beses at gawin ito.
At pagkatapos Panghuli, Pupunta ako upang gawin ito.
>> Kaya sa isang header na file sa isang lugar, sa list0.h
ngayon ay kahulugan struct na ito, at marahil ilang iba pang mga bagay-bagay.
Samantala sa list0c mayroong pagpunta sa maging ang ilang mga bagay.
Ngunit kami ay pagpunta sa makatarungan simulan at tapusin hindi na ito.
List0.h ay isang file na gusto ko isama sa aking C file.
At pagkatapos ay sa isang punto ako pagpunta sa mayroon int, pangunahing, walang bisa.
At pagkatapos ay pupuntahan ko kumuha ng gagawin meron dito.
Pupunta ako din upang magkaroon ng isang prototype, tulad ng walang silbi, paghahanap, int,
n, na ang layunin sa buhay ay upang maghanap para sa isang elemento.
At pagkatapos ay down na dito i-claim in ako code ngayon, walang bisa, paghahanap, int, n,
walang semicolon ngunit bukas kulot braces.
At ngayon nais ko upang kahit papaano maghanap para sa isang elemento sa listahang ito.
Ngunit wala kaming sapat impormasyon sa screen pa.
Mayroon akong hindi talaga kinakatawan ang listahan mismo.
Kaya isang paraan na maaari kaming ipatupad naka-link na listahan sa isang programa
ay uri ng ko nais upang gawin ang isang bagay tulad ng ipinahahayag listahan na naka-link dito.
Para sa pagiging simple, ako ako pagpunta sa gawin ito global, kahit na sa pangkalahatan namin
Hindi dapat gawin ito ng masyadong maraming.
Ngunit ito padaliin ang halimbawang ito.
Kaya gusto ko na idedeklara isang naka-link dito listahan up.
Ngayon, kung paano maaaring gawin ko na?
>> Narito ang litrato ng isang naka-link na listahan.
At gagawin ko hindi talaga alam sa sandaling ito kung paano
Pupunta ako sa pumunta tungkol kumakatawan sa kaya maraming bagay na may isa lamang
variable sa memorya.
Ngunit sa tingin pabalik ng ilang sandali.
Lahat ng oras na ito mayroon kaming mga string, na kung saan namin pagkatapos ay
mailalahad sa maging array ng character, na kung saan namin pagkatapos ay
mailalahad sa maging lamang isang pointer sa unang character
sa isang array ng mga character na null winakasan.
Kaya sa pamamagitan ng na logic, at may ito larawan uri ng seeding ang iyong mga pananaw,
kung ano ang nangangailangan ng aktwal na namin isulat sa aming code sa kumakatawan sa isang naka-link na listahan?
Magkano ng impormasyon na ito ang kailangan namin upang makuha sa C code, nais mong sabihin?
Oo?
>> Madla: Kailangan namin ng isang pointer sa isang node.
David J. MALAN: Ang isang pointer sa isang node.
Sa partikular, na node ng ginagawa ng iyong instincts maging upang mapanatili ang isang pointer sa?
>> Madla: Ang unang node.
>> David J. MALAN: Oo, marahil lang ang unang.
At napansin, ang unang na node ay isang iba't ibang mga hugis.
Ito ay lamang sa kalahati ng laki ng struct, dahil ito ay sa katunayan lamang ng isang pointer.
Kaya ano ang maaari mong gawin sa katunayan ay ipinahahayag naka-link na listahan upang maging ng uri ng node *.
At tumawag lamang ni muna itong ipaalam at initialize ito sa null.
Kaya null, muli, ay darating sa larawan dito.
Hindi lamang ay null ginagamit bilang tulad ng isang espesyal na return halaga para sa mga bagay tulad ng getstring
at malloc, null rin ang zero pointer, ang kakulangan ng isang pointer,
kung gagawin mo.
Ito lamang ay nangangahulugan na walang ay pa dito.
Ngayon unang, kaya kong nai na tinatawag na ito ng kahit ano.
Sana tinatawag ko ito "listahan" o anumang bilang ng iba pang mga bagay.
Ngunit ako pagtawag ito "unang" upang ito linya up gamit ang larawang ito.
Kaya tulad ng isang string maaaring katawanin may address ng kanyang unang byte,
kaya maaari isang naka-link na listahan.
At kami makita ang iba pang data kaayusan katawanin
sa pamamagitan lamang ng isang pointer, 32-bit na arrow, na nakaturo
sa pinakadulo unang node sa istraktura.
>> Ngunit inaasahan problema ngayon hayaan.
Kung lamang ako pagtanda sa aking mga programa sa address
ng unang node, ang unang Parihaba sa istraktura ng data,
kung ano ay nagkaroon ng mas mahusay na ang kaso tungkol sa pagpapatupad ng natitira sa aking mga listahan?
Ano ang isang mahalagang detalye na nangyayari upang matiyak na ito talaga gumagana?
At sa pamamagitan ng "talagang gumagana" ko ibig sabihin, halos tulad ng isang string,
hinahayaan pumunta sa amin mula sa unang character sa pangalan Davin sa pangalawa,
ang ikatlong, upang ang pang-apat, sa dulo napaka,
paano ko malalaman namin kapag hindi namin sa dulo ng isang naka-link na listahan na ganito ang hitsura?
Kapag ito ay walang bisa.
At ako kinakatawan na ang ganitong uri ng bilang tulad ng isang de-koryenteng inhinyero ay maaaring,
may maliit na grounding simbolo, ng mga klase.
Ngunit iyon lamang ay nangangahulugan na walang bisa sa kasong ito.
Maaari mong iguhit ito sa anumang numero ng ng paraan, ngunit may-akdang ito
Nangyari na gamitin ang simbolong ito dito.
>> Kaya hangga't kami ay stringing lahat ng mga nodes magkasama,
pag-alala lamang kung saan ang unang isa ay, sa gayon ang haba
bilang inilalagay namin ang isang espesyal na simbolo sa pinakadulo huling node sa listahan,
at gagamitin namin ang null, dahil iyon ang kung ano ang mayroon kaming magagamit sa amin,
listahan na ito ay kumpleto na.
At kahit na lamang ako magbibigay sa iyo ng isang pointer sa sa unang elemento, ikaw, ang programmer,
Maaari tiyak access ang iba sa mga ito.
Ngunit sabihin ang iyong isip ipaalam maglibot Medyo,
kung sila ay hindi na medyo wandered-- kung ano ang
pagpunta sa maging ang oras ng paggana ng paghahanap ng anumang bagay sa listahang ito?
Damn ito, ito ay malaki O ng n, na kung saan ay hindi masama, sa pagiging makatarungan.
Ngunit ito ay linear.
Nagbigay kami ng hanggang sa kung ano ang tampok ng array sa pamamagitan ng paggalaw nang higit pa
patungo ang larawang ito ng pabagu-bagong pinagtagpi-sama o naka-link node?
Binigyan namin ang hanggang random na pag-access.
Ang isang array ay maganda dahil mathematically ang lahat ng bagay
ay bumalik upang i-back upang i-back sa likod.
Kahit na ang larawang ito mukhang maganda, at kahit na
bagaman mukhang mga node ay may pagitan ng mabuti ang pagitan, sa katotohanan
maaari silang maging kahit saan.
Ox1, Ox50, Ox123, Ox99, ang mga nodes ay maaaring maging kahit saan.
Dahil malloc ang maglaan ng memorya mula sa heap, ngunit saanman sa heap.
Ikaw ay hindi kinakailangang malaman na ito pagpunta sa na bumalik upang i-back sa likod.
At gayon ang larawang ito sa katotohanan ni hindi pagpunta sa lubos na itong maganda.
>> Kaya ito ay pagpunta sa tumagal ng kaunting gumagana upang ipatupad ang pag-andar.
Kaya ipatupad sa paghahanap ngayon hayaan.
At kami makita ang uri ng isang matalino na paraan ng paggawa nito.
Kaya kung ako ay isang function ng paghahanap at Ako bibigyan ng variable, integer n
upang tumingin para sa, kailangan kong malaman ang bagong syntax para sa naghahanap sa loob
ng istruktura na itinuturo sa, upang makahanap ng n.
Kaya sabihin gawin ito.
>> Kaya unang pupuntahan ko pumunta Magpatuloy at ipinahahayag ang isang node *.
At ako pagpunta sa tumawag ito pointer, sa pamamagitan lamang ng convention.
At ako pagpunta sa initialize ito sa unang.
At ngayon maaari kong gawin ito sa isang bilang ng mga paraan.
Ngunit Pupunta ako sa tumagal ng isang karaniwang diskarte.
Habang pointer ay hindi kapantay sa null, at iyon ang wastong syntax.
At ito ay nangangahulugan lamang gawin ang mga sumusunod, kaya Hangga't hindi ka na tumuturo sa wala.
Ano ang gusto kong gawin?
>> Kung pointer tuldok n, hayaan mo akong bumalik upang iyon, equals-- ay katumbas ng kung ano?
Ano ang halaga ng aking hinahanap?
Ang aktwal n na ipinasa sa.
Kaya narito ang isa pang tampok ng C at maraming wika.
Kahit na ang istraktura na tinatawag na node May halaga n, ganap lehitimong
upang magkaroon din ng isang lokal na argumento o variable na tinatawag na n.
Dahil kahit na namin, na pantao mga mata, maaari makilala
na ito ay n baka iba mula sa n ito.
Dahil ang syntax ay iba.
Nakakuha ka ng isang tuldok at isang pointer, samantalang ang isang ito ay walang mga naturang bagay.
Kaya ito ay OK.
Iyon ang OK upang tawagan ang mga ito ng parehong mga bagay.
>> Kung ko mahanap ito, ako pagpunta sa nais na gawin ang isang bagay
tulad ng ipahayag na natagpuan namin n.
At pababayaan namin na nakalabas na bilang isang magkomento o pseudocode code.
Iba Pa, at narito ang kagiliw-giliw na bahagi, kung ano ang
ang gusto kong gawin kung ang kasalukuyang node ay hindi naglalaman ng n na akong pakialam tungkol sa?
Paano ko makamit ang sumusunod?
Kung ang aking daliri sa sandali ay PTR, at ito ay
na tumuturo sa kahit anong unang nakaturo sa,
paano ko ililipat ang aking daliri sa susunod na node sa code?
Well, ano ang breadcrumb kami pagpunta sa sundin sa kasong ito?
Madla: [INAUDIBLE].
David J. MALAN: Oo, kaya susunod.
Kaya kung pumunta ako pabalik sa aking code dito, sa katunayan, ako
pagpunta sa sige at sabihin ang pointer, na ay isa lamang pansamantalang variable-- ito
isang kakatwang mga pangalan, ptr, ngunit ito ay katulad lamang ng temp--
Pupunta ako upang i-set pointer katumbas ng kahit anong pointer is--
at muli, ito ay magiging isang maliit na mayroong bug para sa isang moment-- tuldok sa tabi.
Sa ibang salita, ako ako pagpunta sa tumagal ng aking daliri na tumuturo sa node na ito
dito at pupuntahan ko sabihin, alam mo na ano, tingnan ang susunod na field
at ilipat ang iyong daliri upang kahit anong ito ay tumuturo sa.
At ito ay pagpunta sa ulitin, ulitin, ulitin.
Ngunit kapag ang aking daliri itigil ang paggawa ng anumang bagay sa lahat?
Sa lalong madaling kung ano ang linya ng code kicks in?
Madla: [INAUDIBLE]
David J. MALAN: Kung punto habang pointer ay hindi kapantay sa null.
Sa ilang mga punto ang aking daliri ni pagpunta sa ay tumuturo sa null
at pupuntahan ko maisip iyon ang katapusan ng listahang ito.
Ngayon, ito ay isang maliit na puting kasinungalingan para sa pagiging simple.
Ito ay lumiliko out na kahit na namin natutunan lamang ito tuldok pagtatanda
para sa mga istraktura, pointer ay hindi isang struct.
ptr ay kung ano?
Lamang na maging mas nitpicky.
Ito ay isang pointer sa isang node.
Ito ay hindi isang node mismo.
Kung mayroon akong mga star dito, pointer absolutely-- ito ay isang node.
Ito ay tulad ng isang linggo deklarasyon ng isang variable,
kahit na ang salitang "node" ay bagong.
>> Ngunit sa lalong madaling ipakilala kami ng isang bituin, ito ay isang pointer sa isang node ngayon.
At sa kasamaang palad, hindi mo maaaring gamitin ang tuldok pagtatanda para sa isang pointer.
Kailangan mong gamitin ang mga arrow pagtatanda, na kung saan, strikingly,
ang unang pagkakataon na ang anumang mga piraso ng syntax mukhang madaling maunawaan.
Ito literal mukhang isang arrow.
At nang sa gayon ay isang magandang bagay.
At pababa dito literal mukhang isang arrow.
Kaya sa tingin ko na ang la-- gagawin ko hindi Sa tingin ko over-paggawa ng here-- ko
Sa tingin iyon ang huling bagong piraso ng syntax kami ng pagpunta upang makita.
At thankfully, ito ay sa katunayan mas madaling maunawaan ng kaunti.
>> Ngayon, para sa mga ng sa iyo kung sino baka mas gusto ang lumang paraan,
maaari mo pa ring gamitin ang pagtatanda na tuldok.
Ngunit bilang bawat Lunes ni pakikipag-usap, muna namin
kailangan upang pumunta doon, pumunta sa na tugunan, at pagkatapos ay i-access ang field.
Kaya ito ay tama rin.
At tapat, ito ay isang kaunti pa pedantic.
Literal na iyong sinasabi, dereference ang pointer at pumunta doon.
Pagkatapos grab .n, ang patlang na tinatawag n.
Ngunit tapat, walang sinuman ang nais ni i-type o basahin ito.
At kaya mundo imbento ang arrow pagtatanda, na
ay katumbas, magkakahawig, ito lamang ay syntactic asukal.
Kaya isang magarbong paraan ng pagsabi na ito mas mahusay ang hitsura, o mukhang mas simple.
>> Kaya ngayon ako pagpunta sa gawin ang isa sa iba pang mga bagay.
Pupunta ako sa sabihin ang "break" sa sandaling hindi ko Napag-alaman na kaya hindi ko panatilihin ang naghahanap para dito.
Ngunit ito ay ang gist ng isang function ng paghahanap.
Ngunit ito ay isang mas madaling, sa dulo, hindi upang maglakad sa pamamagitan ng code.
Ito ay sa katunayan ang pormal na pagpapatupad ng paghahanap sa pamamahagi ng code sa araw na ito.
Dare ko sabihin na insert ay hindi lalo na masaya upang maglakad sa pamamagitan ng
biswal, at hindi rin tanggalin, kahit na bagaman sa pagtatapos ng araw
pigsa sila pababa sa medyo simple heuristics.
>> Kaya sabihin gawin ito.
Kung ikaw katatawanan sa akin dito, ginawa ko magdala ng grupo ng mga bola ng stress.
Dinala ako ng isang bungkos ng mga numero.
At maaari naming makuha lamang ng ilang mga boluntaryo upang kumatawan 9, 17, 20, 22, 29, at 34?
Kaya mahalagang lahat ng tao sino ang dito ngayon.
Iyon ay isa, dalawa, tatlo, apat, lima, anim na tao.
At ako hilingin sa iyo na makita go--, walang isa sa likod itataas ang kanilang mga kamay.
OK, isa, dalawa, tatlo, apat, five-- hayaan mo akong i-load balance-- anim.
OK, ka ng anim na dumating sa up.
Kakailanganin naming ibang tao.
Dinala namin ang dagdag na mga bola ng stress.
At kung maaari kang, lamang ng isang sandali, linya
inyong sarili up lamang tulad ang larawang ito dito.
>> Lahat ng karapatan.
Ni makita Hayaan, kung ano ang iyong pangalan?
>> Madla: Andrew.
>> David J. MALAN: Andrew, ang numero 9 sa iyo.
Nice upang matugunan mo.
Narito kang pumunta.
Madla: Jen.
David J. MALAN: Jen.
David.
Numero 17.
Oo?
>> Madla: Ako Julia.
>> David J. MALAN: Julia, si David.
Numero 20.
Madla: Kristiyano.
David J. MALAN: Kristiyano, si David.
Numero 22.
At?
>> Madla: JP.
David J. MALAN: JP.
Numero 29.
Kaya sige lang at makakuha ng in-- Uh oh.
Uh oh.
Standby.
20.
Magkaroon ng isang marker ba?
Madla: Mayroon akong isang Sharpie.
David J. MALAN: Nakakuha ka ng Sharpie?
OK.
At mayroon ang isang piraso ng papel ang sinuman?
I-save ang lecture.
Halika sa.
Madla: Mayroon kaming ito.
David J. MALAN: Mayroon kaming ito?
Ang lahat ng mga karapatan, salamat sa iyo.
Narito pumunta namin.
Ay ito mula sa iyo?
Lamang-save ka ng araw.
Kaya 29.
Lahat ng karapatan.
Maling nabaybay ko 29, ngunit ang OK.
Sige.
Ang lahat ng mga karapatan, Bibigyan kita ng ang panulat ninyo bumalik sa ilang sandali.
Kaya mayroon kaming mga kasamahan dito.
Mayroon ng isang iba pang Hayaang.
Gabe, ang gusto mong i-play sa unang elemento dito?
Kailangan mo kami upang tumuro sa mga masasarap na kakailanganin ng mga tao.
Kaya 9, 17, 20, 22, uri ng 29, at pagkatapos ay 34.
Mawala ba namin ang isang tao?
Gagawin ko ay may 34.
Saan did-- OK, na nagnanais na maging 34?
OK, dumating sa up, 34.
Ang lahat ng mga karapatan, ito ay magiging mahusay nagkakahalaga ang rurok.
Ano ang inyong pangalan?
>> Madla: Peter.
>> David J. MALAN: Pedro, dumating sa up.
Ang lahat ng mga karapatan, kaya narito ang isang buong bungkos ng mga node.
Ang bawat isa sa iyo guys kumakatawan isa sa mga parihaba.
At Gabe, ang bahagyang kakaiba tao out, kumakatawan sa unang.
Kaya ang kanyang pointer ay isang maliit na mas maliit sa screen kaysa sa iba pa.
At sa kasong ito, sa bawat isa sa iyong kaliwa kamay ay magiging alinman sa ituro pababa,
at sa gayon ay kumakatawan sa null, upang lamang ang kawalan ng isang pointer,
o ito ang nangyayari na tumuturo sa isang susunod na node sa iyo.
>> Kaya ngayon kung adorn mo inyong sarili tulad ng larawan
dito, magpatuloy at punto sa isa't isa, na may Gabe
sa partikular na tumuturo sa numero 9 upang kumatawan sa listahan.
OK, at numero ng 34, ang iyong kaliwang kamay Dapat lamang na tumuturo sa sahig.
>> OK, kaya ito ay naka-link na listahan.
Kaya ito ang sitwasyon na pinag-uusapan.
At sa katunayan, ito ay kinatawan ng isang klase ng mga problema
na maaari mong subukan upang malutas gamit ang code.
Gusto mong ipasok sa huli isang bagong elemento na ito sa listahan.
Sa kasong ito, kami ay pagpunta sa subukan ang pagpapasok ng numero 55.
Ngunit may pupuntahan maging iba't ibang mga kaso upang isaalang-alang.
At sa katunayan, ito ay magiging isa ng malaki-larawan takeaways dito, ay,
ano ang iba't ibang mga kaso.
Ano ang iba't ibang mga kundisyon kung o sangay na maaaring mayroon ang iyong programa?
>> Well, ang bilang na sinusubukan mong insert, na alam natin ngayon upang maging 55,
ngunit kung hindi mo alam nang maaga, daresay ko
Nabibilang sa hindi bababa sa tatlong posibleng mga sitwasyon.
Saan maaaring maging isang bagong elemento?
Madla: At sa dulo o gitna.
David J. MALAN: Sa katapusan, sa sa gitna, o sa simula.
Kaya inaangkin ko mayroong hindi bababa sa tatlong mga problema na kailangan namin upang malutas.
Sabihin pumili kung ano ang marahil arguably ang pinakasimpleng
isa, kung saan ang mga bagong elemento Nabibilang sa simula.
Kaya pupuntahan ko mayroon code masyadong tulad ng paghahanap, na kung saan ko lang ay nagsulat.
At pupuntahan ko mayroon ptr, na Kukunin ko ay kumakatawan dito gamit ang aking daliri,
gaya ng dati.
>> At tandaan, kung ano ang halaga nag-initialize namin ptr sa?
Kaya nasimulan namin ito sa null sa umpisa.
Ngunit pagkatapos ay kung ano ang ginagawa namin nang isang beses namin ay sa loob ng aming pag-andar ng paghahanap?
Unang Itinakda namin ito katumbas ng, na kung saan ay hindi nangangahulugan ng paggawa nito.
Kung una itinakda ko ptr katumbas ng, kung ano ang dapat ang aking kamay ba talagang maging tumuturo sa?
I-right.
Kaya kung Gabe at ako ay pumunta sa upang maging katumbas ng halaga dito,
kailangan naming i-parehong punto sa numero 9.
>> Kaya ito ay ang simula ng aming kuwento.
At ngayon ito ay isa lamang prangka, kahit na ang syntax bago.
Conceptually ito ay isa lamang linear paghahanap.
Ay 55 na katumbas ng 9?
O sa halip, sabihin nating mas mababa sa 9.
Dahil sinusubukan ko upang malaman kung saan upang ilagay ang 55.
Mas mababa sa 9, mas mababa sa 17, mas mababa sa 20, mas mababa sa 22, mas mababa sa 29,
mas mababa sa 34, hindi.
Kaya ngayon kami ay sa kasong isa sa hindi bababa sa tatlong.
>> Kung gusto ko upang ipasok 55 sa paglipas dito, kung ano mga linya ng code na kailangan upang isagawa?
Paano gumagana ang larawang ito ng kailangang baguhin ang mga tao?
Ano ang gagawin ko sa aking kaliwang kamay?
Ito ay dapat na sa una null, dahil ako sa dulo ng listahan.
At ano ang dapat mangyari dito sa Pedro, ay ito?
Malinaw na Siya'y pagpunta sa ituro sa akin.
Kaya inaangkin ko mayroong hindi bababa sa dalawang linya ng code sa sample code mula ngayon
na pupuntahan ipatupad ang Ang sitwasyong ng pagdaragdag ng 55 sa likod o hulihan.
At maaari ba akong magkaroon ng isang tao hop up at kinakatawan lamang 55?
Ang lahat ng mga karapatan, ikaw ang bagong 55.
>> Kaya ngayon kung ano kung ang susunod na Ang sitwasyong ito ay kasama,
at gusto naming upang ipasok sa simula o ulo ng listahang ito?
At kung ano ang iyong pangalan, numero ng 55?
>> Madla: Jack.
>> David J. MALAN: Jack?
OK, mabait sa matugunan mo.
Maligayang pagdating sakay.
Kaya ngayon kami ay pagpunta sa magpasok ng, sabihin nating, ang bilang 5.
Narito ang pangalawang kaso ng tatlong ay dumating up kami sa dati.
Kaya kung 5 nabibilang sa simula, sabihin makita kung paano namin makita na ang out.
Initialize ko ang aking ptr pointer sa numero muli 9.
At ako natanto, oh, 5 ay mas mababa sa 9.
Kaya ayusin ang larawang ito para sa amin.
Kaninong mga kamay, Gabe o ni David ang or-- kung ano ang pangalan ng numero 9 ni?
>> Madla: Jen.
>> David J. MALAN: hands-- Jen ay kung alin sa aming mga kamay kailangang baguhin?
OK, kaya Gabe tumuturo sa kung ano ngayon?
Sa akin.
Ako ang bagong node.
Kaya idedetalye ko lang ang uri ng paglipat dito upang makita ito biswal.
At samantala ano ang gagawin ko ituro iyon?
Pa rin kung saan makakakuha ako ng pagturo.
Kaya na ito.
Kaya lamang talagang isang linya ng pag-aayos ng code sa partikular na isyu na ito, ay mukhang ito.
Ang lahat ng mga karapatan, sa gayon ay maganda.
At maaari isang tao maging isang placeholder para sa 5?
Halika sa up.
Susubukan naming kumuha ka ng susunod na pagkakataon.
>> Ang lahat ng mga karapatan, kaya now-- at bilang isang bukod, ang mga pangalan
Hindi ako sa paggawa ng tahasang pagbanggit ng karapatan ngayon, pred pointer, predecessor pointer
at mga bagong pointer, na na naibigay ang mga pangalan lamang
sa sample code upang ang mga payo o ang aking mga kamay na uri ng pagturo sa paligid.
Ano ang inyong pangalan?
>> Madla: Christine.
>> David J. MALAN: Christine.
Maligayang pagdating sakay.
Isaalang-alang natin ngayon ang lahat ng karapatan, kaya hayaan isang bahagyang higit pa nakakainis na sitwasyon,
kung saan gusto kong magpasok ng mga isang bagay tulad ng 26 sa ito.
20?
Ano?
Ang mga are-- magandang bagay na mayroon kami ito panulat.
Ang lahat ng mga karapatan, 20.
Kung may isang tao ay maaaring makakuha ng isa piraso ng papel na handa na, lamang sa case-- ang lahat ng karapatan.
Oh, kawili-wili.
Well ito ay isang halimbawa ng isang panayam bug.
OK kaya kung ano muli ang inyong pangalan?
Madla: Julia.
David J. MALAN: Julia, maaari mong i-pop out at magpanggap na kayo ay hindi kailanman doon?
OK, ito ay hindi kailanman nangyari.
Salamat sa iyo.
Kaya ipagpalagay na nais naming isingit Julia sa ito naka-link na listahan.
Siya ay ang bilang 20.
At syempre siya pagpunta sa nabibilang sa
begin-- ay hindi tumuturo sa kahit ano pa.
Kaya ang iyong mga kamay ay maaaring uri ng magiging down na null o ilang mga halaga ng basura.
Sabihin natin ang kuwento mabilis Hayaan.
Ako na tumuturo sa numero 5 oras na ito.
Pagkatapos suriin ko 9.
Pagkatapos suriin ko 17.
Pagkatapos suriin ko 22.
At Napag-alaman kong, ooh, Julia Kailangang pumunta bago 22.
Kaya kung ano ang kailangang mangyari?
Kailangan Kaninong mga kamay upang baguhin?
Julia, na mina, or-- kung ano muli ang inyong pangalan?
>> Madla: Kristiyano.
>> David J. MALAN: Christian o?
>> Madla: Andy.
>> David J. MALAN: Andy.
Christian o Andy?
Kailangang ituro sa Andy?
Julia.
Lahat ng karapatan.
Kaya Andy, ang gusto mong ituro sa Julia?
Ngunit maghintay ng isang minuto.
Sa kuwento kaya sa ngayon, Ako ang uri ng isa
sa pagsingil, sa kamalayan na pointer ay ang bagay na
paglipat sa listahan.
Maaaring mayroon kami ng isang pangalan para sa Andy, ngunit walang variable na tinatawag na Andy.
Ang tanging iba pang mga variable na mayroon kami ay una, kung sino ang kinakatawan ng Gabe.
>> Kaya ito ay talagang kung bakit kaya malayo hindi namin kinakailangan na ito.
Ngunit ngayon sa screen mayroong banggitin muli ng pred pointer.
Kaya hayaan mo akong maging mas tahasang.
Kung ito ang pointer, nagkaroon ako ng mas mahusay na makakuha ng higit sa isang maliit na matalino
tungkol sa aking iteration.
Kung hindi mo bale ko ang aking pagpunta sa pamamagitan dito muli, na nakaturo dito, na nakaturo dito.
Ngunit hayaan mo akong magkaroon ng isang pred pointer, predecessor pointer, na
uri ng pagturo sa elemento ako ay isa lamang sa.
Kaya kapag pumunta ko dito, ngayon ang aking mga pag-update pakaliwa kamay.
Kailan ko pumunta dito ang aking mga pag-update ng kaliwang kamay.
At ngayon Mayroon akong hindi lamang isang pointer sa ang elemento na pumupunta pagkatapos Julia,
Mayroon pa rin ako ng pointer sa Andy, bago ang element.
Kaya ikaw ay may access, tunay, breadcrumbs, kung gagawin mo,
sa lahat ng mga kinakailangang mga payo.
>> Kaya kung gumagamit ako ng pagturo sa Andy at ako rin ng pagturo
sa Kristiyano, na ang mga kamay dapat na ngayon itinuturo sa ibang lugar?
Kaya Andy ay maaari na ngayong tumuturo sa Julia.
Maaari na ngayong tumuturo sa Julia Kristiyano.
Dahil maaari niyang kopyahin ang aking pointer kanang kamay ni.
At na mabisang Binibigyan ka ng pabalik sa lugar na ito dito.
Kaya sa maikling, kahit na ito nagtatagal sa amin uri ng magpakailanman
upang aktwal na i-update ang isang listahan ng naka-link, Napagtanto
na ang mga operasyon ay medyo simple.
Ito'y ng isa, dalawa, tatlo linya ng code sa huli.
Ngunit balot sa paligid ng mga linya ng code baka
ay isang bit ng logic na mabisang itinatanong ang mga katanungan, kung saan tayo?
Sigurado kami sa simula, sa gitna, o sa dulo?
>> Ngayon, may mga tiyak na ang ilang mga iba pang mga pagpapatakbo na maaari naming ipatupad.
At ang mga larawan dito ilarawan lamang kung ano ang ginawa lang namin sa mga tao.
Paano ang tungkol sa pag-alis?
Kung gusto kong, halimbawa, alisin ang numero ng 34 o 55,
Maaaring mayroon ko ang mga parehong uri ng code, ngunit Pupunta ako sa kailangan ng isa o dalawang hakbang.
Dahil kung ano ang bago?
Kung aalisin ko ay may sa dulo, tulad ng numero ng 55 at pagkatapos ay 34,
kung ano ay mayroon ding upang baguhin tulad ng ginagawa ko na?
Kailangan ko bang hindi evict-- kung ano muli ang inyong pangalan?
>> Madla: Jack.
>> David J. MALAN: Jack.
Mayroon akong hindi lamang evict-- libreng Jack, kaya Literal na tawagan libreng Jack, o hindi bababa sa
ang pointer doon din, ngunit ngayon kung ano ang kailangang baguhin sa Peter?
Kanyang kamay mas mahusay na magsimula na nakaturo pababa.
Dahil sa lalong madaling tumawag ako ng libreng on Jack, kung pagturo pa rin ni Pedro sa Jack
at samakatuwid ko panatilihin traversing sa listahan at i-access ang pointer,
na kapag ang aming lumang segmentation kaibigan Kasalanan maaaring aktwal na kick in.
Dahil binigyan ka namin ang memory pabalik sa Jack.
>> Maaari kang manatili doon awkwardly para sa sandali lamang.
Dahil mayroon kaming dalawang lamang huling mga pagpapatakbo upang isaalang-alang.
Pag-aalis ng mga ulo ng listahan, o ang beginning-- at ang isang ito ay
isang maliit na nakakainis.
Dahil mayroon kaming malaman na Gabe ay uri ng espesyal na sa programang ito.
Dahil sa katunayan, siya ay kanyang sariling pointer.
Siya'y hindi lamang ini-itinuturo sa, bilang ay halos ang lahat ng iba pa dito.
>> Kaya kapag ang pinuno ng listahan ay Inalis, na ang mga kamay kailangang baguhin ngayon?
Ano ulit ang inyong pangalan?
>> Madla: Christine.
>> David J. MALAN: Ako ay kahindik-hindik sa mga pangalan, tila.
Kaya Christine at Gabe, na ang mga kamay kailangang baguhin
kapag sinubukan naming alisin ang Christine, numero 5, mula sa larawan?
OK, na gawin Gabe kaya hayaan.
Gabe pupuntahan ituro, baka, sa numero 9.
Ngunit kung ano ang susunod na dapat mangyari?
Madla: Christine dapat maging null [INAUDIBLE].
David J. MALAN: OK, dapat namin marahil make-- narinig ko "null" sa isang lugar.
Madla: Walang bisa at libreng kanya.
David J. MALAN: null ano?
Madla: Walang bisa at libreng kanya.
David J. MALAN: Walang bisa at libreng kanya.
Kaya ito ay napakadali.
At ito ay perpekto na ikaw ngayon uri ng nakatayo doon, na hindi kasali.
Dahil mo pa decoupled mula sa listahan.
Epektibo mong pa orphaned mula sa listahan.
At sa gayon mas mahusay na kami ay tumawag sa libreng ngayon Christine upang bigyan na memory pabalik.
Kung hindi man sa bawat oras na namin tanggalin ang isang node mula sa listahan
Maaaring ginagawa namin ang listahan mas maikli, ngunit hindi tunay na nagpapababa
sa laki sa memorya.
At kaya kung panatilihin namin ang pagdaragdag at pagdaragdag, pagdaragdag ng mga bagay sa listahan,
maaaring makakuha ng mas mabagal sa aking computer at mas mabagal at mas mabagal,
dahil Nauubusan na ako ng memorya, kahit na hindi ako talaga
gamit bytes Christine ni ng memorya na ngayon.
>> Kaya sa katapusan mayroong iba pang mga mga sitwasyon, ng course-- pag-alis
sa gitna, pag-alis sa dulo, tulad ng nakita natin.
Ngunit ang mas kawili-wiling Ang hamon ngayon ay
magiging upang isaalang-alang nang eksakto kung ano ang oras tumatakbo ang.
Kaya hindi lamang maaari mong panatilihin ang iyong piraso ng papel, kung, Gabe,
hindi mo nais na bale pagbibigay lahat ng bola ng stress.
Salamat sa iyo kaya magkano sa aming listahan na naka-link ng mga boluntaryo dito, kung dati mo.
>> [APPLAUSE]
>> David J. MALAN: Lahat ng karapatan.
Kaya ng ilang Analytical mga katanungan pagkatapos, kung maaari ko.
Nakakita kami pagtatanda na ito bago, O malaki at wakas, itaas na hangganan
at mas mababang mga hangganan sa oras ng paggana ng ilang mga algorithm.
Kaya isaalang-alang na lamang hayaan isang pares ng mga katanungan.
>> Ang isa, at sinabi namin ito bago, ano ang tumakbo
oras ng paghahanap para sa isang listahan sa mga tuntunin ng malaking O?
Ano ang isang pang-itaas nakatali sa pagtakbo oras ng naghahanap ang isang naka-link na listahan
bilang ipinatupad ng aming mga boluntaryo dito?
Ito ay malaking O ng n, linear.
Dahil sa ang pinakamasama kaso, ang elemento, tulad ng 55,
maaaring hinahanap namin para sa ay maaaring maging kung saan Jack ay, ang lahat ng mga paraan sa dulo.
At sa kasamaang-palad, hindi tulad ng isang array hindi namin maaaring makakuha ng magarbong oras na ito.
Kahit na ang lahat ng aming mga tao ay pinagsunod-sunod mula sa maliit na mga elemento, 5,
ang lahat ng mga paraan ng hanggang sa ang mas malaking elemento, 55, na kadalasan ay isang magandang bagay.
Ngunit ano ang ginagawa na palagay hindi na-daan sa amin upang gawin?
Madla: [INAUDIBLE]
David J. MALAN: Sabihing muli?
Madla: Random access.
David J. MALAN: Random access.
At siya namang ay nangangahulugan na maaari naming hindi na gagamitin ng mahina ng mga zero, Swersey,
at obviousness ng paggamit ng binary maghanap at hatiin at lupigin.
Dahil kahit na namin mga tao ay maaaring malinaw naman
makita na Andy o Kristiyano ay halos sa gitna ng listahan,
Alam namin na bilang lamang computer sa pamamagitan ng skimming sa listahan
mula sa napaka-simula.
Kaya binigyan up namin na random na pag-access.
>> Kaya malaking O ng n ay ngayon sa itaas mapasailalim sa aming oras ng paghahanap.
Paano ang tungkol sa wakas ng aming paghahanap?
Ano ang mas mababang nakatali sa paghahanap para sa ilang mga numero sa listahang ito?
Madla: [INAUDIBLE]
David J. MALAN: Sabihing muli?
Madla: Isa.
David J. MALAN: Isa.
Kaya tuluy-tuloy na oras.
Sa pinakamahusay na kaso, Christine ay sa katunayan sa simula ng listahan.
At kaming naghahanap ng para sa numero 5, kaya natagpuan namin sa kanya.
Kaya walang malaki deal.
Subalit siya nakuha upang maging sa simula ng listahan sa kasong ito.
Paano ang tungkol sa isang bagay tulad Tanggalin?
Paano kung gusto mong tanggalin ang isang elemento?
Ano ang itaas na nakatali at mas mababang mga hangganan sa pagtanggal ng isang bagay mula sa naka-link
ilista?
Madla: [INAUDIBLE]
David J. MALAN: Sabihing muli?
Madla: n.
David J. MALAN: n ay sa katunayan itaas na hangganan.
Dahil sa ang pinakamasama kaso subukan namin tanggalin Jack, tulad ng ginawa namin lamang.
Siya ay ang lahat ng mga paraan sa dulo.
Tumatagal magpakailanman sa amin, o n hakbang na ito upang mahanap sa kanya.
Kaya na ang isang itaas na hangganan.
Iyon ang linear, sigurado.
At ang pinakamahusay na kaso sa pagtakbo ang oras, o ang mas mababang mga hangganan sa pinakamahusay na kaso
ay magiging tuluy-tuloy na oras.
Dahil siguro sinusubukan naming tanggalin Christine, at makakuha pa lang namin masuwerteng
siya sa simula.
Ngayon maghintay ng isang minuto.
Gabe ay sa simula rin, at nagkaroon din namin na i-update ang Gabe.
Kaya na ay hindi isang hakbang lamang.
Kaya ito ay sa katunayan pare-pareho oras, sa pinakamahusay na kaso,
alisin ang pinakamaliit na elemento?
Ito ay, kahit na maaari itong maging dalawa, tatlo, o kahit na 100 mga linya ng code,
kung ito ay ang parehong bilang ng mga mga linya, hindi sa ilang mga loop,
at independiyenteng ng laki ng listahan, walang pasubali.
Tinatanggal ang elemento sa sa simula ng listahan,
kahit na mayroon kami upang harapin ang Gabe, ay pare-pareho ang oras pa rin.
>> Kaya ito ay tila tulad ng isang napakalaking hakbang paurong.
At kung ano ang isang pag-aaksaya ng panahon kung, sa linggo ng isa at linggo
zero namin ay may mga hindi lamang pseudocode code ngunit aktwal na code
upang ipatupad ang isang bagay na pag-log base n, o mag-log, sa halip, ng n, base 2,
sa mga tuntunin ng running time nito.
Kaya bakit ang heck ay nais naming simulan gamit ang isang bagay tulad ng isang naka-link na listahan?
Oo.
>> Madla: Kaya maaari mong idagdag mga elemento sa array.
David J. MALAN: Kaya maaari mong magdagdag ng mga elemento sa array.
At ito ay masyadong thematic.
At patuloy kaming makita ito, ito kalakalan-off, magkano
tulad ng nasaksihan namin ang isang kalakalan-off ang may-uri-merge.
Talaga namin mai-mapabilis maghanap o pag-uuri, sa halip,
kung gastusin namin ng kaunti pang espasyo at May dagdag na chunk ng isang memory
o isang array para sa uri merge.
Ngunit gastusin namin ng higit pang espasyo, ngunit i-save namin ang oras.
Sa kasong ito, hindi namin pagbibigay up oras ngunit kami ay
pagkakaroon ng kakayahang umangkop, dynamism kung gagawin mo,
na kung saan ay arguably ang positibong tampok na ito.
>> Din kami gumagasta ng espasyo.
Sa anong kahulugan ay naka-link ilista ang mas mahal
sa mga tuntunin ng espasyo kaysa sa isang array?
Saan nagmumula ang mga dagdag na espasyo mula sa?
Oo?
>> Madla: [INAUDIBLE] pointer.
>> David J. MALAN: Oo, namin Mayroon din ang pointer.
Kaya ito ay minorly nakakainis sa na hindi na am
Ako sa pag-iimbak lamang sa isang int kinakatawan ang isang int.
Ako sa pag-iimbak sa isang int at isang pointer, na kung saan ay 32 bits din.
Kaya ako literal pagdodoble ang halaga ng puwang ng kasangkot.
Kaya na ang isang kalakalan-off, ngunit na sa kaso ng int.
Ipagpalagay na hindi ka nag-iimbak ng int, ngunit ipagpalagay bawat isa sa mga parihaba
o bawat isa sa mga kawani na tao ay kumakatawan sa isang salita, isang salitang Ingles na
ay maaaring maging limang mga character, 10 character, siguro ay mas mabuti.
Pagkatapos ng pagdaragdag ng 32 lamang sa higit pang mga piraso ay maaaring maging mas mababa ng isang malaking deal.
>> Paano kung ang bawat isa sa mga mag-aaral sa demonstration
ay literal structs mag-aaral na May mga pangalang at bahay at siguro
mga numero ng telepono at Twitter humahawak at mga katulad.
Kaya ang lahat ng mga patlang na sinimulan namin pakikipag-usap tungkol sa iba pang araw,
higit na mas mababa ng isang malaking bilang deal ang aming mga node makakuha ng higit pang mga kawili-wiling
at malaki gastusin, eh, ang isang karagdagang pointer lamang i-link ang mga iyon nang magkakasama.
Ngunit sa katunayan, ito ay isang kalakalan-off.
At sa katunayan, ang code ay mas kumplikado, bilang ikaw
makita sa pamamagitan ng skimming sa pamamagitan ng na partikular na halimbawa.
Ngunit ano kung mayroong ang ilang mga banal grail dito.
Paano kung hindi kami gumawa ng isang hakbang paurong ngunit isang napakalaking hakbang pasulong
at ipatupad ang data istraktura sa pamamagitan ng kung saan namin
Maaari mahanap ang mga elemento tulad ng Jack o Christine o anumang iba pang mga elemento
sa array na ito sa tunay na pare-pareho ang oras?
Paghahanap ay pare-pareho.
Tanggalin ay pare-pareho.
Isingit ay pare-pareho.
Ang lahat ng mga pagpapatakbong ito ay pare-pareho.
Iyon ay magiging banal sa aming grail.
At iyon ay kung saan namin ay kukunin sa susunod na pagkakataon.
Tingnan mo pagkatapos.