[Powered by Google Translate] [Seachtain 6, lean] [David J. MALAN] [Ollscoil Harvard] [Tá sé seo CS50.] [CS50.TV] Is é seo an CS50 agus is é seo an deireadh seachtaine 6. Mar sin, CS50x, ar cheann de na cúrsaí chéad Harvard ar bainteach leis an tionscnamh edX go deimhin, debuted an Luan seo caite. Más mian leat a fháil glimpse ar cad daoine eile ar an Idirlíon iad seo a leanas anois chomh maith le, is féidir leat ceann a x.cs50.net. A chuirfidh tú a athdhíriú ar an áit chuí ar edx.org, a bhí i gcás seo agus cúrsaí eile ó MIT agus Berkeley beo anois. Beidh tú le clárú le haghaidh cuntas; beidh tú go bhfuil an t-ábhar den chuid is mó mar an gcéanna mar atá tú a bhí an trian seo, cé go cúpla seachtain moill, de réir mar a fháil againn gach rud réidh. Ach cad a dhéanfaidh mac léinn i CS50x fheiceáil anois comhéadan go leor mar seo amháin. Seo, mar shampla, tá Zamyla i gceannas ar an walkthrough do 0 leagtha fhadhb. Ar logáil isteach chuig edx.org bhfeiceann, mac léinn CS50x na cineál rudaí a mbeifeá ag súil a fheiceáil i gcúrsa: an léacht ar an Luan, léacht ar Dé Céadaoin, shorts éagsúla, na tacair fhadhb, na walkthroughs, PDFs. Ina theannta sin, mar a fheiceann tú anseo aistriúcháin meaisín, de scríbhinní Béarla i Sínis, Seapáinis, Spáinnis, Iodáilis, agus a bunch iomlán de theangacha eile a bheidh cinnte neamhfhoirfe agus muid ag rolladh amach iad programmatically ag baint úsáide as rud ar a dtugtar an API, nó comhéadan cláir iarratais, ó Google a ligeann dúinn a thiontú Béarla do na teangacha eile. Ach a bhuíochas leis an spiorad iontach roinnt oibrithe deonacha céad-móide, daoine randamach ar an Idirlíon a thairiscint kindly a bheith páirteach sa tionscadal seo, beidh orainn de réir a chéile a bheith feabhas ar chaighdeán na haistriúcháin ag a bhfuil daoine a cheartú na botúin go bhfuil ár ríomhairí a rinneadh. Mar sin, casadh sé amach go raibh muid a thaispeáint mic léinn cúpla níos mó suas ar an Luan ná mar a measadh againn ar dtús. Go deimhin, anois tá CS50x 100,000 duine a leanas chomh maith sa bhaile. Mar sin, realize go bhfuil tú go léir mar chuid den aicme tionscnaimh a dhéanamh ar an gcúrsa san eolaíocht ríomhaireachta oideachais níos ginearálta, ar bhonn níos leithne, inrochtana. Agus is é an réaltacht anois, le roinnt de na cúrsaí ollmhór ar líne, siad ag tosú ar fad leis na huimhreacha an-ard, de réir mar is cosúil go bhfuil déanta anseo. Ach an sprioc i ndeireadh na dála, is é do CS50x i ndáiríre do dhaoine mar go leor a fháil chun an líne a chríochnú agus is féidir. De réir dearadh, tá CS50x ag dul a bheith ar fáil ó Dé Luain seo caite léir ar an mbealach tríd an 15 Aibreán, 2013, ionas go mbeidh folks a bhfuil tiomantais scoil in áit eile, obair, teaghlach, coimhlintí eile agus a leithéidí, tá solúbthacht le beagán níos mó a chun tumadóireacht a dheanamh i gcúrsa seo, a, is leor a rá, Tá go leor ambitiously dhéanamh más rud é amháin le linn ach trí mhí i rith sheimeastar is gnách. Ach beidh ar na mic léinn dul i ngleic le tacair fhadhb chéanna, breathnú ar an ábhar céanna, bhfuil rochtain acu ar an shorts céanna agus a leithéidí. Mar sin, a thuiscint go bhfuil muid go léir i ndáiríre i seo le chéile. Agus nach bhfuil ceann de na spriocanna deireadh CS50x ach a fháil folks mar go leor chun an líne a chríochnú agus a thabhairt dóibh an tuiscint newfound de eolaíocht ríomhaireachta agus cláir ach freisin go bhfuil a bheith acu an taithí roinnte. Ceann de na tréithe a shainmhíniú de 50 ar an gcampas, tá súil againn, Tá an saghas taithí phobail, le haghaidh níos fearr nó níos measa, uaireanta, ach a bhfuil na daoine seo dul chuig an taobh clé agus ar dheis, uaireanta oifige agus agus an hackathon agus ar an aonach. Tá sé beagán níos deacra a dhéanamh go pearsanta le daoine ar líne, ach beidh CS50x i gcrích i mí Aibreáin leis an Expo an chéad uair riamh CS50, Beidh a oiriúnú ar líne ar ár smaoineamh ar an aonach áit a mbeidh na mílte mac léinn a cuireadh do gach a chur isteach 1 - go dtí 2 nóiméad físeán, ceachtar screencast n deiridh an tionscadail nó físeán acu waving dia duit agus ag caint faoina tionscadal agus demoing é, i bhfad cosúil le do réamhtheachtaithe a dhéanamh anseo ar an gcampas ar an aonach, ionas go bhfuil ag deireadh na seimeastar, is é an dóchas go bhfuil taispeántas domhanda de na mic léinn CS50x 'tionscadail deiridh, i bhfad mar go awaits a bhfuil tú an Nollaig anseo ar an gcampas. Mar sin, níos mó ar sin sna míonna atá le teacht. Le 100,000 mac léinn, cé go dtagann, gá le CAanna cúpla níos mó. Ós rud go bhfuil tú guys blazing an rian anseo agus ag cur CS50 roinnt seachtainí roimh an t-ábhar ar scaoileadh chun an folks ar edX, a bhaint amach ba bhreá linn i gceist mar go leor de na mic léinn féin agus is féidir sa tionscnamh seo, le linn an tseimeastair chomh maith leis an gheimhridh agus an earraigh ag teacht. Mar sin, más mian leat a bheith páirteach i CS50x, go háirithe ag teacht isteach i ar CS50x Pléigh, an leagan edX de CS50 Pléigh, a bhfuil go leor de tú ag baint úsáide as ar an gcampas, an bord fógraí ar líne, le do thoil ceann leis an URL, in iúl dúinn cé tú féin, mar ba bhreá linn a thógáil suas le foireann na mac léinn agus na foirne agus dáimhe araon ar an gcampas atá a imirt ach chomh maith agus cuidiú amach. Agus nuair a fheiceann siad ceist go bhfuil taithí acu, éisteacht tú ag mac léinn ag tuairisciú roinnt bug áit éigin amuigh ansin i roinnt tíortha ar an Idirlíon, agus go bhfuil fáinní le clog toisc go raibh tú ró-sin tsaincheist chéanna i do d-halla tamall ó shin, tá súil againn ansin is féidir leat clingíní i agus do thaithí féin a roinnt. Mar sin, le do thoil páirt a ghlacadh más mian leat. Tá cúrsaí eolaíocht ríomhaireachta ag Harvard le beagán de thraidisiún, CS50 ina measc, a bhfuil cuid éadaigh, roinnt éadaí, gur féidir leat a chaitheamh proudly ag seimeastar deireadh na bliana, ag rá go leor proudly go chríochnaigh tú CS50 agus ghlac CS50 agus a leithéidí, agus muid iarracht i gcónaí do mhic léinn i gceist sa phróiseas seo oiread agus is féidir, trína tugaimid cuireadh, thart ar an am seo den seimeastar, mic léinn dearaí a chur isteach ag baint úsáide as Photoshop, nó cibé uirlis de rogha gur mhaith leat úsáid a bhaint as má tá tú dearthóir, a chur faoi bhráid dearadh le haghaidh T-léinte agus sweatshirts agus tá scáthanna fearthainne agus bandanas beag le haghaidh madraí againn anois agus a leithéidí. Agus tá gach rud ansin - na buaiteoirí gach bliain ar taispeáint ansin ar an gcúrsa ar shuíomh gréasáin ag store.cs50.net. Tá gach rud a dhíoltar ar chostas ann, ach an láithreán gréasáin Ritheann díreach é féin agus tugann sé deis do dhaoine a roghnú na dathanna agus dearadh gur mhaith leo. Mar sin, shíl mé gur mhaith linn a roinnt ach cuid de na bliana seo caite dearaí a bhí ar an láithreán gréasáin sa bhreis ar an gceann seo anseo, a bhfuil traidisiún bliantúil. "Gach lá mé ag seg Faultn" a bhí ar cheann de na haighneachtaí bliana seo caite, atá fós ar fáil ann do alumni. Bhí orainn an gceann seo, "CS50, Bunaithe 1989." Ar cheann de na Bowdens, Rob, bhí an-tóir ar an bhliain seo caite. "Foireann Bowden" a rugadh, a cuireadh faoi bhráid an dearadh, i measc na díoltóirí barr. Mar a bhí an ceann seo anseo. A lán daoine go raibh "Bowden Fiabhras" de réir na logs díolacháin. Realize go d'fhéadfadh a bheith anois do dhearadh ann, suas ar an Idirlíon. Tá níos mó sonraí ar seo an fhadhb seo chugainn Leagann atá le teacht. Uirlis amháin níos mó: tú a bhí ar roinnt nochtadh agus táthar ag súil anois roinnt taithí phraiticiúil le GDB, atá, ar ndóigh, dífhabhtóir agus is féidir leat a ionramháil do chlár ar leibhéal sách íseal, ag déanamh cén cineál rudaí? Cad a dhéanann GDB in iúl duit a dhéanamh? Yeah? Tabhair dom rud éigin. [Freagra na Mac Léinn, dothuigthe] Dea-. Céim isteach fheidhm, agus mar sin ní gá duit ach chun cineál reáchtáil agus tá an buille chláir trí huile agus go hiomlán, priontáil amach rudaí chuig aschur caighdeánach. Ina ionad sin, is féidir leat céim tríd líne ar líne, bíodh sé ag clóscríobh seo chugainn líne chun dul ag líne ar líne nó ar chéim chun tumadóireacht a dheanamh i bhfeidhm, de ghnáth amháin gur scríobh tú. Cad eile nach GDB a ligean a dhéanann tú? Yeah? [Freagra na Mac Léinn, dothuigthe] Athróg a phriontáil. Mar sin, más mian leat a dhéanamh le introspection beag taobh istigh de do chlár gan dul i muinín a scríobh ráitis printf ar fud na háite, féidir leat a phriontáil ach athróg nó athróg a thaispeáint. Cad eile is féidir leat a dhéanamh le dífhabhtóir mhaith GDB? [Freagra na Mac Léinn, dothuigthe] Go díreach. Is féidir leat Brisphointí a leagtar; is féidir leat a rá forghníomhú sos ag an phríomhfheidhm nó fheidhm foo. Is féidir leat a rá forghníomhú sos ag líne 123. Agus tá Brisphointí mar theicníc cumhachtach i ndáiríre mar má tá tú tuiscint ghinearálta ar d'fhadhb nuair a is dócha go bhfuil, nach bhfuil tú ag am le dramhaíl stepping tríd an chláir go hiomlán. Is féidir leat léim go bunúsach ceart ann, agus ansin clóscríobh tús - stepping tríd le céim nó eile nó a leithéid. Ach tá an ghabháil le rud éigin cosúil le GDB go gcuidíonn sé tú, an duine, teacht ar do chuid fadhbanna agus do bugs a aimsiú. Ní chuireann sé a fháil gá iad sin i bhfad ar do shon. Mar sin, thugamar isteach an style50 lá eile, a bhfuil uirlis líne ghairid orduithe a dhéanann iarracht a stylize do chód le beagán níos mó cleanly ná tú, an duine a d'fhéadfadh, a bheith déanta. Ach sin, freisin, tá i ndáiríre ach rud aeistéitiúil. Ach casadh sé amach níl an uirlis eile ar a dtugtar Valgrind go bhfuil beagán níos arcane a úsáid. Is é an aschur atrociously cryptic ar an gcéad amharc. Ach tá sé iontach, go háirithe anois go bhfuil muid ag an chuid den téarma áit a bhfuil tú ag tosú a úsáid malloc agus leithdháileadh cuimhne dinimiciúil. Is féidir le rudaí a théann i ndáiríre, mícheart i ndáiríre go tapa. Toisc má dhéanann tú dearmad go saor in aisce do chuimhne, nó téigh i pointeoir NULLComment tú roinnt, nó téigh i tú roinnt pointeoir truflais, cad é de ghnáth ar an symptom go bhfuil na torthaí? Seg locht. Agus gheobhaidh tú an comhad seo lárnach de roinnt ar líon na cilibheart nó meigibheart gur ionann an staid de do chláir cuimhne nuair a thuairteáil sé, ach do chlár seg deireadh thiar lochtanna, locht deighilt, rud a chiallaíonn rud éigin a tharla dona i gcónaí a bhaineann beagnach le botún cuimhne a bhaineann go ndearna tú áit éigin. Mar sin, cuidíonn Valgrind leat teacht ar rudaí mar seo. Is uirlis a ritheann tú, cosúil le GDB, tar éis atá tú le chéile do chlár, ach seachas a reáchtáil do chlár go díreach, ritheann tú Valgrind agus éiríonn leat é a do chlár, díreach mar a dhéanann tú le GDB. Anois, an úsáid, a fháil ar an cineál is fearr an aschuir, Tá beagán fada, mar sin ceart ann ar bharr na craoibhe ar an scáileán mbainfidh tú a fheiceáil Valgrind-v. "-V" ciallaíonn beagnach go huilíoch verbose nuair a bhíonn tú ag baint úsáide as cláir ar ríomhaire Linux. Mar sin, ciallaíonn sé spit amach níos mó sonraí ná mar a d'fhéadfadh tú de réir réamhshocraithe. "- Sceite-seiceáil = iomlán." Tá sé seo ag rá díreach a sheiceáil le haghaidh gach leaks cuimhne is féidir, botúin a d'fhéadfadh a rinne mé. Seo, freisin, tá paradigm coiteann le cláir Linux. Go ginearálta, má tá tú argóint ar an líne ordaithe tá go "athrú", go s ceaptha a athrú ar an gclár ar iompar, agus tá sé ina litir amháin, tá sé-v, ach más rud é go tá aistrigh, ach ag dearadh an Ríomhchláraitheoir, Tá focal iomlán nó sraith de na focail, tosaíonn an argóint ar an líne orduithe le -. Is iad seo ach coinbhinsiúin an duine, ach go mbainfidh tú iad a fheiceáil níos mó. Agus ansin, ar deireadh, "a.out" Is é an t-ainm treallach don chlár sa sampla seo go háirithe. Agus anseo tá roinnt aschur ionadaíoch. Sula táimid ag méid a d'fhéadfadh a chiallaíonn, lig dom dul thar a Blúire de chód thar anseo. Agus lig dom seo a bhogadh amach as an mbealach seo, ag teacht go luath, agus a ligean ar ghlacadh le breathnú ar memory.c, a bhfuil an sampla gearr anseo. Mar sin, sa chlár seo, lig dom a súmáil isteach ar na feidhmeanna agus na gceisteanna. Tá príomhfheidhm go bhfuil gá a chomhlíonadh, f, agus ansin cad f aghaidh a dhéanamh, i mBéarla beagán teicniúil? Cad a dhéanann f aghaidh a dhéanamh? Cad é faoi Feicfidh mé tús le líne a 20, agus nach bhfuil an réalta suíomh ábhar, ach beidh mé a bheith díreach ag teacht anseo le léacht seo caite. Cad a dhéanann líne 20 dúinn? Ar thaobh na láimhe clé. Beidh muid bhriseadh síos a thuilleadh. Int * x: cad a dhéanann a dhéanamh? Maith go leor. Tá sé seo dhearbhú pointeoir, agus anois a ligean ar a bheith níos mó teicniúil. Cad a chiallaíonn sé, an-nithiúil, a dhearbhú pointeoir? D'iarr duine éigin eile? Yeah? [Freagra na Mac Léinn, dothuigthe] Too go dtí seo. Mar sin, tá tú ag léamh go dtí an taobh na láimhe deise de an comhartha comhionann. A ligean ar díriú ach ar thaobh na láimhe clé, díreach ar slánuimhir * x. Seo fholaíonn "a dhearbhú" a pointeoir, ach anois ligean ar Léim i níos doimhne leis an sainmhíniú. Cad a dhéanann go nithiúil, go teicniúil chiallaíonn? Yeah? [Freagra na Mac Léinn, dothuigthe] Maith go leor. Tá sé ag ullmhú a shábháil seoladh i gcuimhne. Dea-. Agus a ligean ar dhéanfaidh an taisceadh sin amháin eile; tá sé dhearbhú athraitheach, x, go bhfuil 32 giotán. Agus tá a fhios agam go bhfuil sé 32 giotán mar gheall ar -? Níl sé mar tá sé ina slánuimhir, mar tá sé ina pointeoir sa chás seo. Chomhtharlú go bhfuil sé ar cheann agus mar an gcéanna le slánuimhir, ach ar an bhfíric go bhfuil an réalt Ciallaíonn é seo pointeoir agus sa fearas, mar a bhfuil ríomhairí go leor, ach ní go léir, tá leideanna 32 giotán. Ar chrua-earraí níos nua-aimseartha ar nós na Macs is déanaí, na ríomhairí pearsanta is déanaí, a bheadh ​​agat 64-giotán threo, ach i an fearas, is iad na rudaí 32 giotán. Mar sin, beidh orainn a chaighdeánú ar sin. Níos nithiúil, téann an scéal mar a leanas: Táimid "Dearbhaíonn" a pointeoir; cad a chiallaíonn? Ullmhú againn chun é a stóráil ar ainm na cuimhne. Cad a chiallaíonn? Táimid a chruthú x athróg ar a dtugtar a thógann suas 32 giotán a stóráil go luath ar an seoladh slánuimhir. Agus sin is dócha faoi beacht agus is féidir linn a fháil. Tá sé go breá ag bogadh ar aghaidh a shimpliú ar fud an domhain agus díreach rá a dhearbhú go bhfuil pointeoir ar a dtugtar x. A dhearbhú go bhfuil pointeoir, ach a bhaint amach agus a thuiscint cad atá ar siúl iarbhír ar fiú amháin i díreach na carachtair beag. Anois, an ceann seo beagnach beagán níos éasca, cé tá sé ina léiriú níos faide. Mar sin, cad seo a dhéanamh, go bhfuil béim anois: "malloc (10 * Is uimhir (o));" Yeah? [Freagra na Mac Léinn, dothuigthe] Dea-. Agus beidh mé ansin é. Tá sé seo leithdháileadh le smután de chuimhne ar feadh deich slánuimhreacha. Agus lig anois s Léim i beagán níos doimhne; tá sé leithdháileadh le smután de chuimhne ar feadh deich slánuimhreacha. Cad é malloc filleadh ansin? An seoladh an smután, nó, níos nithiúil, seoladh an chéad bheart an smután. Conas ansin mé, an Ríomhchláraitheoir, go mbeadh a fhios i gcás go smután de foircinn gcuimhne? Tá a fhios agam go bhfuil sé tadhlach. Malloc, de réir sainmhínithe a bheidh, a thabhairt duit le smután tadhlach de chuimhne. Níl aon bearnaí ann. Tá tú rochtain ar gach beart sa smután, droim le droim ar ais, ach conas a fhios agam áit a bhfuil an deireadh an smután de chuimhne? Nuair a úsáideann tú malloc? [Freagra na Mac Léinn, dothuigthe] Chéasta. Nach bhfuil tú. Tá tú chun cuimhneamh orthu. Caithfidh mé a mheabhrú gur úsáid mé an luach 10, agus ní féidir liom is cosúil fiú a bheith déanta go anseo. Ach tá an dualgas go hiomlán ar dom. Strlen, a againn a bheith beagán ag brath ar do teaghráin, oibríonn ach amháin mar gheall ar an coinbhinsiún seo a bhfuil \ 0 nó carachtar seo speisialta nialasach, úsáidte, ag deireadh an teaghrán. Ní sin a shealbhú ar feadh díreach smután treallach de chuimhne. Tá sé suas chun tú. Mar sin, líne 20, ansin Leithdháileann, le smután de chuimhne is féidir a stóráil deich slánuimhreacha, agus siopaí sé an seoladh an chéad bheart den smután de chuimhne sa x athróg ar a dtugtar. Ergo, a bhfuil pointeoir. Mar sin, ag teacht 21, ar an drochuair, bhí botún. Ach ar dtús, cad a dhéanamh? Tá sé seo ag rá siopa ag suíomh 10, 0 innéacsú, an smután de chuimhne ar a dtugtar x 0 luach. Mar sin, fógra cúpla rudaí ag dul ar aghaidh. Cé go bhfuil x ina pointeoir, aisghlaoch ó cúpla seachtain ó shin gur féidir leat a úsáid i gcónaí an sraith-stíl nodaireacht scriosaidh cearnach. Toisc go bhfuil i ndáiríre gearr-láimh Scríobhtar an uimhríochtúil pointeoir níos mó cryptic-lorg. i gcás ina mbeadh linn a dhéanamh rud éigin mar seo: Tóg an x ​​seoladh, bogadh 10 spotaí os a chionn, ansin dul ann le cibé seoladh a stóráil ag an suíomh sin. Ach frankly, tá sé seo ach atrocious a léamh agus a fháil compordach leis. Mar sin, úsáideann an domhan de ghnáth na lúibíní cearnacha díreach mar tá sé sin i bhfad níos mó duine-chairdiúil a léamh. Ach go bhfuil ag tarlú i ndáiríre ar thíos an cochall; Is é x nach a seoladh, eagar, per se. Mar sin, tá sé seo a stóráil 0 ag suíomh 10 in x. Cén fáth go bhfuil sé seo dona? Yeah? [Freagra na Mac Léinn, dothuigthe] díreach. Leithdháileadh muid ach deich ints, ach táimid comhaireamh ó 0 nuair cláir i C, ionas go mbeidh tú rochtain 0 10 1 2 3 4 5 6 7 8 9, ach nach bhfuil. Mar sin, go bhfuil an clár ag dul go dtí locht seg nó nach bhfuil sé. Ach níl a fhios againn i ndáiríre; tá sé seo saghas iompar nondeterministic. Braitheann sé gur ar cé acu a fháil againn ádh. Má casadh sé amach nach bhfuil an córas oibriúcháin aigne má úsáideann mé beart breise, cé nach bhfuil sé tugtha domsa, ní fhéadfadh mo chlár tuairteála. Tá sé amh, tá sé Buggy, ach ní a d'fhéadfadh leat a fheiceáil go symptom, nó a d'fhéadfadh leat é a fheiceáil ach aon uair amháin ar feadh tamaill. Ach tá an réaltacht go bhfuil an fabht, i ndáiríre, ansin. Agus tá sé i ndáiríre fadhbanna má tá tú i scríbhinn ar chlár gur mian leat a bheith ceart, go atá tú a dhíol ar an gclár go bhfuil daoine úsáid a bhaint as gach dheasca uair amháin ar feadh tamaill mar, ar ndóigh, nach bhfuil sé seo go maith. Go deimhin, má tá tú fón Android nó iPhone agus tú apps íoslódáil na laethanta seo, má tá tú go raibh riamh an app a scor go díreach, ar fad ar tobann imíonn sé, go beagnach i gcónaí mar thoradh ar roinnt cheist cuimhne a bhaineann le, trína Ríomhchláraitheoir screwed suas agus dereferenced a pointeoir go bhfuil sé nó nár chóir di a bheith acu, agus mar thoradh ar iOS nó Android a mharú ach an clár ar fad seachas iompar undefined riosca nó de shaghas éigin comhréiteach slándála. Níl aon bug eile sa chlár seo sa bhreis ar an gceann seo. Cad eile a bhfuil screwed mé suas sa chlár seo? Ní mé a chleachtadh méid atá mé seanmóir. Yeah? [Freagra na Mac Léinn, dothuigthe] Chéasta. Nach bhfuil mé freed an chuimhne. Mar sin, an riail an ordóg anois tar éis a bheith ag am ar bith a ghlaonn tú malloc, ní mór duit glaoch saor in aisce nuair atá tú ag déanamh úsáid a bhaint as cuimhne. Anois, ba mhaith nuair a bhím ag iarraidh go saor in aisce leis an gcuimhne? Is dócha, ag glacadh leis an chéad líne a bhí ceart, ba mhaith liom iarraidh a dhéanamh anseo. Toisc nach raibh mé in ann, mar shampla, an bhfuil sé síos anseo. Cén fáth? Díreach amach a bhfuil raon feidhme. Mar sin, cé go bhfuil muid ag caint faoi threo, tá sé seo le seachtain 2 nó 3 a eisiúint, i gcás x ach amháin i raon taobh istigh de na braces gcuach nuair a bhí dearbhaithe sé. Mar sin, tá tú nach féidir saor in aisce cinnte sé ann. Is é mo seans ach amháin go saor in aisce sé thart tar éis an líne 21. Is clár simplí go leor; bhí sé éasca go leor nuair a tá tú de chineál ar fillte d'intinn thart ar cad an clár a dhéanamh, áit a raibh na botúin. Agus fiú amháin más rud é nach raibh tú é a fheiceáil ar dtús, tá súil againn tá sé ina beagán soiléir anois go bhfuil na botúin go leor go héasca réiteach agus go héasca a dhéanamh. Ach nuair a bhíonn clár níos mó ná 12 línte fada, tá sé 50 línte fada, 100 línte fada, ag siúl trí do líne cód le líne, ag smaoineamh tríd go loighciúil, Is féidir é ach gan spraoi go háirithe a dhéanamh, i gcónaí ag lorg bugs, agus tá sé deacair freisin a dhéanamh, agus sin an fáth a bhfuil uirlis mhaith Valgrind. Lig dom dul ar aghaidh agus é seo a dhéanamh: lig dom a oscailt mo fhuinneog críochfoirt, agus lig dom ní reáchtáil díreach chuimhne, mar is cosúil cuimhne a bheith fíneáil. Tá mé ag dul t-ádh. Ag dul leis an beart breise ag deireadh an sraith Ní cosúil go ró-fadhbanna. Ach lig dom, mar sin féin, a dhéanamh seiceáil sanity, rud a chiallaíonn go díreach a sheiceáil cibé acu atá nó nach bhfuil sé seo i ndáiríre ceart. Mar sin a ligean a dhéanamh valgrind-v - sceitheadh-seiceáil = iomlán, agus ansin an t-ainm ar an gclár sa chás seo nach bhfuil cuimhne, a.out. Mar sin, lig dom dul ar aghaidh agus é seo a dhéanamh. Buail isteach. A chara Dia. Is é seo a aschur, agus tá sé seo cad a alluded mé níos luaithe. Ach, má fhoghlaim tú chun léamh tríd gach ceann de na nonsense anseo, Tá an chuid is mó de seo ach aschur diagnóiseacha ní go bhfuil suimiúil. Cad é do shúil ar mhaith leo bheith ag lorg aon lua earráid nó neamhbhailí. Focail go bhfuil fadhbanna le fios. Agus go deimhin, a ligean ar a fheiceáil cad atá ar siúl mícheart síos anseo. Tá mé achoimre de chineál éigin, "in úsáid ag amach:. 40 bytes i 1 bloic" Níl mé i ndáiríre cinnte cad é bloc go fóill, ach 40 bytes i ndáiríre mothaíonn mhaith raibh mé in ann an figiúr amach nuair a tá go teacht as. 40 bytes. Cén fáth go bhfuil 40 bytes in úsáid ag imeacht? Agus níos mó go sonrach, má scrollaigh muid síos anseo, cén fáth a chaill mé cinnte 40 bytes? Yeah? [Freagra na Mac Léinn, dothuigthe] foirfe. Yeah, go díreach. Bhí deich slánuimhreacha, agus gach ceann de na is méid 4, nó 32 giotán, mar sin tá mé caillte go beacht 40 bytes toisc, mar a mhol tú, nach bhfuil mé ar a dtugtar saor in aisce. Sin ceann bug, agus anois a ligean ar breathnú síos beag breise agus a fheiceáil in aice leis seo, "Is neamhbhailí scríobh de mhéid 4." Tá Anois, cad é seo? Tá an seoladh in iúl nodaireacht bonn cad, is cosúil? Tá sé seo heicsidheachúlach, agus aon uair a fheiceann tú roinnt ag tosú le 0x, ciallaíonn sé heicsidheachúlach, rud a rinne muid ar bhealach ar ais i roinn, I mo thuairimse, pset 0 de ceisteanna, a bhí díreach a dhéanamh ar fheidhmiú warmup, ag athrú dheachúlach i heicsidheachúlach go dénártha agus mar sin de. Heicsidheachúlach, ach de réir an ghnáis an duine, a úsáidtear de ghnáth chun leideanna ionadaíocht a dhéanamh ar nó, níos ginearálta, díríonn. Tá sé ach coinbhinsiún, mar tá sé ina beagán níos éasca le léamh, tá sé ina beagán níos dlúithe ná rud éigin cosúil le dheachúlach, agus tá sé dénártha useless do dhaoine an chuid is mó a úsáid. Mar sin, anois cad a chiallaíonn sé? Bhuel, tá sé cosúil le níl a scríobh neamhbhailí de mhéid 4 ar líne 21 de memory.c. Mar sin a ligean dul ar ais go dtí an líne 21, agus go deimhin, anseo go bhfuil scríobh neamhbhailí. Mar sin, nach bhfuil Valgrind ag dul a shealbhú go hiomlán mo lámh agus inis dom cad é an shocrú, ach tá a bhrath sé go bhfuil mé ag déanamh a scríobh neamhbhailí. Tá mé ag touching 4 bytes nár chóir dom a bheith, agus is cosúil é sin mar, mar a dúirt tú amach, tá mé ag déanamh [10] in ionad [9] fónamh, nó [0] nó rud éigin idir eatarthu. Le Valgrind, a bhaint amach am ar bith go bhfuil tú ag scríobh anois le clár go leideanna úsáideann agus a úsáideann chuimhne, agus malloc níos sonraí, cinnte a fháil isteach an nós a reáchtáil seo fada ach an-éasca a chóipeáil agus a ghreamú gceannas Valgrind a fheiceáil má tá roinnt earráidí ann. Agus beidh sé a bheith mór gach uair a fheiceann tú an t-aschur, ach luaitear ach pharsáil trí amhairc gach ceann de an t-aschur agus a fheiceáil má fheiceann tú na n-earráidí nó rabhaidh nó neamhbhailí nó caillte. Aon focail screwed fuaime mar tú suas áit éigin. Mar sin, realize go bhfuil uirlis nua i do bosca uirlisí. Anois ar an Luan, bhí againn a bunch iomlán de folks teacht suas anseo agus ionadaíocht a dhéanamh ar an nóisean de liosta nasctha. Agus thug muid ar an liosta nasctha mar réiteach leis an méid a réiteach? Yeah? [Freagra na Mac Léinn, dothuigthe] Chéasta. Ní féidir arrays bhfuil cuimhne curtha leo. Má leithdháileadh tú le sraith de mhéid 10, sin uile a fhaigheann tú. Is féidir leat glaoch feidhm mhaith realloc má d'iarr tú ar dtús malloc, agus gur féidir iarracht a dhéanamh ag fás an eagar má tá spás i dtreo an deireadh é go bhfuil aon duine eile ag baint úsáide as, agus más rud é nach bhfuil, beidh sé a fháil ach tú le smután níos mó áit éigin eile. Ach ansin beidh sé cóip gach ceann de na bearta sa réimse nua. Fuaimeanna seo cosúil le réiteach an-ceart. Cén fáth go bhfuil sé seo feiliúnach? Ciallaíonn mé a oibríonn sé, tá daoine a réiteach an fhadhb seo. Cén fáth gur gá dúinn é a réiteach ar an Luan le liostaí nasctha? Yeah? [Freagra na Mac Léinn, dothuigthe] D'fhéadfadh sé a ghlacadh le fada. Go deimhin, am ar bith go bhfuil tú ag iarraidh malloc nó realloc nó calloc, a bhfuil eile fós ar cheann, aon uair a dhéanann tú, an clár, ag caint leis an gcóras oibriúcháin, claonadh a bhíonn tú mall síos ar an gclár. Agus má tá tú ag déanamh na cineálacha rudaí i lúb, agus tú ag moilliú i ndáiríre rudaí síos. Níl tú ag dul a thabhairt faoi deara seo le haghaidh an simplí de "hello domhan" cláir cineál, ach i gcláir i bhfad níos mó, ag iarraidh an córas oibriúcháin arís agus arís eile chun cuimhne nó claonadh a thugann sé ar ais arís agus arís eile gan a bheith ina rud maith. Plus, tá sé ach saghas hintleachtúil - tá sé ina dramhaíl iomlán an am. Cén fáth a cuimhne a dháileadh níos mó agus níos mó, riosca a chóipeáil gach rud isteach sa réimse nua, má tá tú rogha eile a ligeann a dháileadh tú cuimhne ach oiread agus is gá duit i ndáiríre? Mar sin, níl pluses agus minuses i anseo. Ceann de na pluses anois go bhfuil muid fuinneamh. Nach cuma cá bhfuil na smután de chuimhne atá saor in aisce, Is féidir liom a shórtáil díreach de a chruthú ar na blúiríní aráin trí leideanna chun teaghrán mo liosta nasctha go hiomlán le chéile. Ach íocann mé amháin ar a laghad phraghas. Cad a dhéanfaidh mé a thabhairt suas a fháil ar liostaí nasctha? Yeah? [Freagra na Mac Léinn, dothuigthe] Chéasta. Ní mór duit cuimhne níos mó. Anois, is gá dom a spás le haghaidh na leideanna, agus i gcás an liosta seo nasctha Super simplí go bhfuil ag iarraidh ach amháin chun é a stóráil slánuimhreacha, a bhfuil 4 bytes, a choinneáil orainn ag rá go maith, tá pointeoir 4 bytes, mar sin anois tá mé faoi dhó literally an méid chuimhne is gá mé díreach tar éis a stóráil ar an liosta seo. Ach arís, is é seo tradeoff leanúnach san eolaíocht ríomhaireachta idir am agus spás agus forbairt, iarracht agus acmhainní eile. Cad é eile downside de ag baint úsáide as liosta nasctha? Yeah? [Freagra na Mac Léinn, dothuigthe] Dea-. Ní furasta teacht orthu. Is féidir linn a thuilleadh a ghiaráil seachtain 0 prionsabail cosúil le roinnt agus conquer. Agus níos mó go sonrach, cuardaigh dénártha. Mar gheall ar cé go táimid ag daoine Is féidir a fheiceáil go garbh áit a bhfuil an lár an liosta seo, an ríomhaire a fhios ach go dtosaíonn an liosta nasctha ag an seoladh iarradh i dtosach. Agus sin 0x123 nó rud éigin mar sin. Agus is féidir an t-aon bhealach leis an gclár teacht ar an eilimint láir Is é a chuardach i ndáiríre an liosta iomlán. Agus fiú ansin, tá sé literally chun cuardach a dhéanamh ar an liosta iomlán mar gheall ar fiú nuair a sroicheann tú an eilimint láir trí na leideanna, tú, ar an gclár, nach bhfuil aon smaoineamh cá fhad a bhfuil an liosta, d'fhéadfadh a bheith, go dtí go bhuail tú ar deireadh é, agus cén chaoi a fhios agat programmatically go bhfuil tú ag deireadh an liosta nasctha? Níl pointeoir NULLComment speisialta, mar sin arís, coinbhinsiún. Seachas seo a úsáid pointeoir, táimid cinnte nach bhfuil ag iarraidh é a bheith roinnt luach truflais dírithe amach céim áit éigin; ba mhaith linn é a bheith ar láimh síos, NULLComment, ionas gur féidir linn an aistir sa struchtúr seo sonraí sin a fhios againn nuair a gcríochnaíonn sé. Cad a tharlaíonn má ba mhaith linn a ionramháil seo? Rinne muid an chuid is mó ar an radharc, agus le daoine, ach cad más mian linn a dhéanamh ar chur isteach? Mar sin, bhí ar an liosta bunaidh 9, 17, 20, 22, 29, 34. Cad a tharlaíonn má bhíomar ag iarraidh ansin chun spás malloc do líon 55, nód chun é, agus ansin ba mhaith linn a chur isteach 55 isteach ar an liosta díreach mar a rinne muid ar an Luan? Conas is féidir linn é seo a? Bhuel, tháinig Anita suas agus shiúil sí go bunúsach ar an liosta. Thosaigh sí ag an chéad ghné, ansin an chéad cheann eile, an chéad cheann eile, an chéad cheann eile, an chéad cheann eile, an chéad cheann eile. Ar deireadh, bhuail an láimhe clé léir ar an mbealach síos agus a baineadh amach ó, is é seo NULLComment. Mar sin, is gá ionramháil pointeoir cad atá le déanamh? An duine a bhí ar an deireadh, uimhir 34, is gá a lámh chlé a ardaíodh go pointe ag 55, is gá 55 a lámh chlé dírithe síos a bheith ar an nua NULLComment Críochnaitheoir. Arna dhéanamh. Éasca go leor a chur isteach 55 i liosta in eagar. Agus d'fhéadfadh conas breathnú? Lig dom dul ar aghaidh agus a oscailt roinnt sampla cód suas anseo. Feicfidh mé a oscailt suas gedit, agus lig dom a oscailt suas dhá chomhad ar dtús. Is é ceann list1.h, agus lig dom i gcuimhne go díreach go raibh sé seo an smután de chód a úsáid againn chun ionadaíocht a dhéanamh nód. Tá nód araon o dtugtar n agus pointeoir ar a dtugtar eile go díreach pointí an rud eile ar an liosta. Is é sin anois an comhad a. H. Cén fáth? Níl an coinbhinsiún seo, agus ní mór dúinn glacadh buntáiste a bhaint as seo méid ollmhór féin, ach an duine a scríobh feidhmeanna printf agus eile Thug mar bhronntanas ar an domhan ar fad na feidhmeanna sin trí scríobh comhad a dtugtar stdio.h. Agus ansin níl string.h, agus ansin níl map.h, agus níl gach na comhaid h go mb'fhéidir go mbeadh tú ag feiceáil nó a úsáid i rith an téarma scríofa ag daoine eile. De ghnáth, sna. Tá comhaid h rudaí ach cosúil le typedefs nó dearbhuithe de chineálacha saincheaptha nó dearbhuithe tairisigh. Ní gá duit a chur ar fheidhmeanna 'implementations i gcomhaid header. Chuir tú, ina ionad sin, ach a gcuid fréamhshamhlacha. Chuir tú rudaí is mian leat a roinnt leis an domhan méid is gá dóibh d'fhonn a thiomsú a n-cód. Mar sin, ach chun dul isteach ar an nós seo, shocraigh muid a dhéanamh ar an rud céanna. Ní Tá i bhfad i list1.h, ach tá muid rud éigin a chur a d'fhéadfadh a bheith spéisiúil do dhaoine ar fud an domhain atá ag iarraidh a bhaint as ár bhfeidhm liosta nasctha. Anois, i list1.c, ní bheidh mé dul tríd an rud ar fad mar tá sé ina beagán fada, an clár seo, ach a ligean ar siúl fíor go tapa ag an pras. Lig dom é a thiomsú Liosta1, lig dom a reáchtáil ansin Liosta1, agus cad a mbainfidh tú a fheiceáil atá déanta againn insamhladh clár beag simplí anseo go dul ar a ligean dom a chur leis agus uimhreacha a bhaint le liosta. Mar sin, lig dom dul ar aghaidh agus 3 cineál do na 3 rogha roghchlár. Ba mhaith liom a chur isteach ar an líon - a ligean ar a dhéanamh ar an chéad uimhir a bhí 9, agus anois tá mé in iúl go bhfuil an liosta anois 9. Lig dom dul ar aghaidh agus eile isteach a dhéanamh, mar sin bhuail mé 3 rogha roghchlár. Cén uimhir ba mhaith liom a chur isteach? 17. Cuir isteach. Agus beidh mé a dhéanamh ach amháin níos mó. Lig dom isteach uimhir 22. Mar sin, ní mór dúinn an tús an liosta nasctha a bhí againn i bhfoirm sleamhnán nóiméad ó shin. Conas atá an chur isteach ag tarlú i ndáiríre? Go deimhin, tá 22 anois ag deireadh an liosta. Mar sin, an scéal a chuir muid ar an stáitse ar an Luan agus recapped díreach anois Ní mór i ndáiríre a bheith ag tarlú i cód. A ligean ar ghlacadh le breathnú. Lig dom scrollú síos sa chomhad seo. Beidh muid snasta thar roinnt de na feidhmeanna, ach beidh muid ag dul síos go dtí, abair, an fheidhm isteach. A ligean ar a fheiceáil conas a théann muid faoi chur isteach nód nua isteach sa liosta nasctha. I gcás ina ndearbhaítear an liosta? Bhuel, a ligean ar scrollaigh go léir ar an mbealach suas ag an mbarr, agus faoi deara go bhfuil mo liosta nasctha dhearbhú go bunúsach mar pointeoir amháin go bhfuil ar dtús NULLComment. Mar sin, tá mé ag baint úsáide as athróg domhanda anseo, atá i gcoitinne againn preached i gcoinne mar a dhéanann sé do chód a messy beag a choimeád ar bun, tá sé saghas leisciúil, de ghnáth, ach níl sé leisciúil agus nach bhfuil sé mícheart, agus nach bhfuil sé olc má tá do chláir aon chuspóir sa saol a insamhail liosta amháin nasctha. Cé acu is go díreach cad tá ag éirí linn. Mar sin, seachas a dhearbhú seo le príomhghnéithe agus ansin é a pas a fháil gach feidhm againn i scríbhinn sa chlár seo, tuigimid ionad OH, a ligean ar a dhéanamh ach domhanda é toisc go bhfuil an cuspóir iomlán an chláir a léiriú amháin agus gan ach amháin liosta nasctha. Ionas go mbraithfidh ceart go leor. Seo iad mo fréamhshamhlacha, agus ní bheidh muid ag dul tríd gach ceann de na, ach scríobh mé feidhm a scriosadh, feidhm a fháil, feidhm isteach, agus feidhm lean. Ach a ligean ar dul anois ar ais síos go dtí an fheidhm isteach agus a fheiceáil conas a oibríonn an ceann seo anseo. Cuir isteach ar líne - Seo muid réidh. Ionsáigh. Mar sin, ní dhéanann sé aon argóintí, mar gheall ar táimid ag dul a iarraidh an taobh istigh úsáideoir an fheidhm seo don líon is mian leo a chur isteach. Ach ar dtús, a ullmhú againn a thabhairt dóibh roinnt spáis. Is é seo an saghas cóipeáil agus greamaigh ón sampla eile. Sa chás sin, bhí a leithdháileadh againn o; an uair seo táimid ag leithdháileadh nód. Ní cuimhin liom i ndáiríre cé mhéad bytes is nód, ach sin fíneáil. Is féidir Is uimhir figiúr sin amach dom. Agus cén fáth Táim ag seiceáil mé do NULLComment ag teacht 120? Cad a d'fhéadfadh dul go mícheart ag teacht 119? Yeah? [Freagra na Mac Léinn, dothuigthe] Dea-. D'fhéadfadh a bheith díreach an cás go bhfuil mé d'iarr cuimhne i bhfad ró- nó nach bhfuil rud éigin cearr agus an córas oibriúcháin a bheith bytes leor a thabhairt dom, mar sin léiríonn sé an oiread agus is trína sheoladh ar ais NULLComment, agus más rud é nach féidir liom a sheiceáil le haghaidh sin agus mé díreach tar éis blindly ar aghaidh chun úsáid a bhaint as an seoladh ar ais, d'fhéadfadh sé a bheith NULLComment. D'fhéadfadh sé a bheith roinnt luach anaithnid; ní rud maith mura I - Ní bheidh a bheith i ndáiríre luach anaithnid. D'fhéadfadh sé a bheith NULLComment, mar sin níl mé ag iarraidh le mí-úsáid é agus riosca dereferencing é. Má tharlaíonn sin, mé ar ais díreach agus beidh muid ag ligean cosúil nach raibh mé a fháil ar ais aon chuimhne ar chor ar bith. Seachas sin, inis mé an t-úsáideoir a thabhairt dom roinnt a chur isteach, cuir glaoch ar liom ár GetInt sheanchara, agus ansin ba é seo an chomhréir nua a tugadh isteach againn ar an Luan. Ciallaíonn 'newptr-> n' a chur ar an seoladh a tugadh duit ag an malloc a léiríonn an chéad bheart de rud nód nua, agus ansin dul leis an réimse a dtugtar n. Tá ceist beag trivia: Tá sé seo comhionann leis an méid líne níos mó cryptic de chód? Conas a d'fhéadfadh eile tá mé scríofa é seo? Want a ghlacadh stab? [Freagra na Mac Léinn, dothuigthe] Dea-. Bain úsáid as an n., Ach nach bhfuil sé simplí go leor mar mar seo. Cad is gá dom ar dtús a dhéanamh? [Freagra na Mac Léinn, dothuigthe] Dea-. Gá dom a dhéanamh * newptr.n. Mar sin, tá sé seo ag rá Tá pointeoir nua ndóigh seoladh. Cén fáth? Toisc go raibh ar ais dó le malloc. An newptr * ag rá "dul ann," agus ansin nuair a bhfuil tú ann, ansin is féidir leat úsáid a bhaint as an níos mó taithí agam orthu. n, ach tá sé seo ach beagán ghránna, go háirithe má tá muid daoine ag dul go dtí tharraingt leideanna le saigheada-am ar fad; tá an domhan caighdeánaithe ar an nodaireacht arrow, a dhéanann go díreach an rud céanna. Mar sin leat é a úsáid ach amháin an -> nodaireacht nuair is é an rud ar chlé a pointeoir. Seachas sin, má tá sé struct iarbhír, bain úsáid as an n.. Agus ansin seo: Cén fáth a bhfuil mé thúsú newptr-> aice le Eolas faoin margadh saothair? Nílimid ag iarraidh a lámh chlé dangling as an deireadh na céime. Ba mhaith linn cur in iúl é díreach síos, rud a chiallaíonn deireadh an liosta D'fhéadfadh a bheith d'fhéadfadh a bheith ag an nód, mar sin a dhéanamh linn níos fearr cinnte go bhfuil sé NULLComment. Agus, go ginearálta, initializing do athróga nó do bhaill sonraí agus structs chun rud éigin ach dea-chleachtais. Just a ligean ar cíos truflais ann agus leanúint ar aghaidh de bheith ann go ginearálta faigheann tú i dtrioblóid má dhéanann tú dearmad rud éigin a dhéanamh níos déanaí. Seo roinnt cásanna. Seo, arís, is é an fheidhm isteach, agus is é an chéad rud a sheiceáil mé má d'iarr an athróg chéad uair, go bhfuil athróg domhanda NULLComment, ciallaíonn sé nach bhfuil aon liosta nasctha. Ní Tá a cuireadh isteach aon uimhreacha, mar sin tá sé fánach a chur isteach ar an uimhir atá ann faoi láthair isteach ar an liosta, mar gheall ar go mbaineann sé ach ag tús an liosta. Mar sin, ba é seo nuair a bhí Anita seasamh suas díreach anseo ina n-aonar, ag ligean aon duine eile a bhí suas anseo ar an stáitse go dtí leithdháileadh againn nód, ansin d'fhéadfadh sí a ardú a lámh don chéad uair, más rud é gur tháinig gach duine eile suas ar an stáitse i ndiaidh di ar an Luan. Anois anseo, tá sé seo le seic beag áit a bhfuil mé a rá má tá an nód nua luach n Tá seo chugainn, a chiallaíonn go téigh go dtí an struct go s á chuir ar ag newptr, mar sin tá muid anseo, dul ann. Ansin tá an arrow rá a fháil ar an réimse seo chugainn, agus ansin tá an = rá a chur ar cad é luach atá ann? An luach a bhí i dtús; cén luach a bhí i dtús? An Chéad a bhí dírithe ag an nód, ionas go ciallaíonn ba chóir é seo pointe anois ag an nód. I bhfocail eile, féachann cad cé praiseach ridiculous le mo chuid scríbhneoireachta, cad smaoineamh simplí ach ag gluaiseacht na saighde ar fud aistríonn cód le líneálach ach an ceann seo. Stóráil cad atá i chéad uair sa réimse seo chugainn agus ansin thabhairt cothrom le dáta cad é an chéad i ndáiríre. Lig dul ar aghaidh agus go tapa ar aghaidh trí roinnt de seo, agus ach breathnú ar an chur isteach eireaball le haghaidh anois. Is dócha mé a fháil chun an pointe nuair teacht liom go bhfuil an réimse eile de chuid nód NULLComment. Agus ag an bpointe seo sa scéal, a mion go bhfuil mé glossing thar Tá go bhfuil mé isteach eile pointeoir suas anseo ag teacht 142, pointeoir réamhtheachtaí. Go bunúsach, ag an bpointe seo sa scéal, faigheann uair an liosta fada, Mé cineál is gá chun siúl sé le dhá mhéar mar má théann mé i bhfad ró, cuimhneamh i liosta amháin-fad, ní féidir leat dul ar gcúl. Dá bhrí sin tá an smaoineamh seo de predptr mo mhéar chlé, agus newptr - ní newptr. Eile is ea an pointeoir go anseo tá mo mhéar eile, agus tá mé díreach de chineál ar siúl ar an liosta. Sin an fáth a bhfuil sin. Ach a ligean ar a mheas ach ceann amháin de na cásanna simplí anseo. Más rud é go pointeoir ar réimse eile NULLComment, cad é an impleacht loighciúil? Má tá tú ag trasnú an liosta seo agus bhuail tú pointeoir NULLComment? Tá tú ag deireadh an liosta, agus mar sin an cód a gceangal ansin ngné amháin breise Tá go mbeidh saghas an iomasach a ghlacadh go nód a bhfuil pointeoir NULLComment atá romhainn, sin tá sé seo faoi láthair NULLComment, agus é a athrú, áfach, a bheith ar an seoladh an nód nua. Mar sin, táimid ag tarraingt go díreach i gcód an arrow a tharraing muid ar an stáitse ag ardú duine láimhe clé. Agus an cás go mbainfidh mé tonn mo lámha ar do anois, díreach toisc go Sílim go bhfuil sé éasca a bheith caillte nuair a dhéanaimid é i saghas seo de chomhshaoil, Tá seiceáil do chur isteach ar an liosta ar lár. Ach amháin intuitively, ní mór cad a tharlóidh más mian leat chun an figiúr amach i gcás ina mbaineann le huimhir éigin i lár bhfuil tú ag siúl air le níos mó ná ceann amháin finger, níos mó ná aon pointeoir, Is é an figiúr amach nuair a mbaineann sé leis ag seiceáil an ghné An ceann atá ann faoi láthair, agus nuair a fhaigheann tú áit sin, ansin caithfidh tú a dhéanamh den chineál seo cluiche bhlaosc nuair a bhogann tú na leideanna thart go han-chúramach. Agus an freagra, más rud é gur mhaith leat chúis tríd an bhaile ar do chuid féin, boils síos go díreach leis an dá líne de chód, ach tá an t-ordú na línte Super tábhachtach. Toisc má tá tú titim duine ar láimh agus a ardú duine éigin eile san ord mícheart, arís, d'fhéadfaí tú suas go deireadh orphaning an liosta. Mar achoimre níos choincheapa de, is é an chur isteach ag an eireaball réasúnta simplí. Is é an chur isteach ag ceann freisin sách simplí, ach ní mór duit thabhairt suas chun dáta le pointeoir breise an am seo a squeeze uimhir 5 isteach ar an liosta anseo, agus baineann sé ansin isteach i lár iarracht fiú níos mó, go han-chúramach isteach uimhir 20 ina suíomh ceart, a bhfuil idir 17 agus 22. Mar sin, is gá duit rud éigin a dhéanamh cosúil leis an nód 20 nua phointe a 22, agus ansin ní mór, a nód ar pointeoir thabhairt cothrom le dáta deireanach? Tá sé 17, a chur isteach i ndáiríre. Mar sin, arís, beidh mé siar ar an gcód iarbhír don chur i bhfeidhm go háirithe. Ar an gcéad amharc, tá sé ina beag mór, ach tá sé i ndáiríre ach lúb gan teorainn go s looping, looping, looping, looping, agus briseadh chomh luath agus a bhuail tú ar an pointeoir NULLComment, ag an bpointe sin is féidir leat a dhéanamh a chur isteach is gá. Seo, ansin, tá cód isteach ionadaíoch nasctha liosta. Ba é an cineál go leor, agus mothaíonn sé cosúil le atá againn réiteach fadhb amháin, ach tá muid isteach ar cheann ar fad eile. Frankly, tá muid chaith seo go léir am ar mór O agus Ω agus a reáchtáil am, ag iarraidh chun fadhbanna a réiteach níos tapúla, agus anseo tá muid ag glacadh céim mhór ar gcúl, mothaíonn sé. Agus fós, má tá an sprioc a sonraí a stóráil, mothaíonn sé cosúil leis an Soitheach Naofa, mar a dúirt muid ar an Luan go mbeadh, a bheith i ndáiríre chun rudaí a stóráil láithreach. Go deimhin, is dócha go raibh muid a chur ar liosta leataobh nasctha ar feadh nóiméad agus thugamar isteach in ionad an nóisean de tábla. Agus a ligean ar smaoineamh go díreach ar an tábla ar feadh nóiméad mar eagar. An eagar agus sa chás seo tá anseo roinnt gnéithe 26, 0 go 25, agus is dócha go raibh gá tú roinnt smután de stórála le haghaidh ainmneacha: Alice agus Bob agus Charlie agus a leithéidí. Agus ní mór duit roinnt struchtúr sonraí a stóráil na hainmneacha. Bhuel, d'fhéadfá a úsáid rud éigin cosúil le liosta nasctha agus d'fhéadfaí tú ag siúl ar an liosta isteach Alice roimh Bob agus Charlie tar éis Bob agus mar sin de. Agus, go deimhin, más mian leat a fheiceáil cód mar sin mar chur ar ceal, Tá a fhios go list2.h, a dhéanann muid go díreach. Ní bheidh muid ag dul tríd an cód, ach tá sé seo is malairt leagain é an chéad sampla go isteach ar cheann struct eile againn le feiceáil roimh mhic léinn ar a dtugtar, agus ansin cad siopaí sé i ndáiríre ar an liosta nasctha le pointeoir le déanmhas mac léinn seachas slánuimhir simplí beag, n. Mar sin a bhaint amach níl cód ann a mbíonn i gceist teaghráin iarbhír, ach más rud é an sprioc ar láimh i ndáiríre anois chun aghaidh a thabhairt ar an bhfadhb éifeachtúlacht, ní bheadh ​​sé deas má táimid tugtha rud ar a dtugtar Alice, ba mhaith linn í a chur isteach sa suíomh ceart i struchtúr sonraí, mothaíonn sé cosúil mhaith sé a bheith i ndáiríre deas a chur díreach Alice, le hainm le A, sa suíomh ar dtús. Agus Bob, le hainm le B, sa dara suíomh. Le sraith, nó a ligean ar tús a chur ag glaoch sé ina tábla, tábla hash ag an, Is féidir linn a dhéanamh go díreach. Má tá léargas tugtha ainm cosúil le Alice, ar shraith ar nós Alice, nuair a dhéanann tú a chur ar A-l-i-c-e? Ní mór dúinn a hueristic. Ní mór dúinn feidhm a chur roinnt ionchur cosúil le Alice agus seol ar ais a fhreagairt, "Cuir Alice ag an suíomh seo." Agus an fheidhm seo, an bosca dubh, ag dul a bheith ar a dtugtar feidhm hash. Tá feidhm hash rud éigin a thógann ionchur, cosúil le "Alice", agus tuairisceáin a thabhairt duit, de ghnáth, an suíomh uimhriúil i roinnt struchtúr sonraí i gcás ina mbaineann Alice. Sa chás seo, ba chóir ár n-fheidhm hash a bheith réasúnta simplí. Ba chóir Ár fheidhm hash rá, má tá tú a tugadh "Alice", agus ba chóir carachtar liom faoi? An chéad cheann. Mar sin, mé ag amharc ar [0], agus ansin rá liom má tá [0] carachtar A, seo an líon 0. Má tá sé B, ar ais 1. Má tá sé C, ar ais 2, agus mar sin de. Bheadh ​​gach innéacs 0, agus a chuireann ar chumas dom a chur isteach Alice agus ansin Bob agus ansin Charlie agus mar sin de isteach sa struchtúr sonraí. Ach tá fadhb ann. Cad a tharlaíonn má thagann Anita chomh maith arís? Nuair is féidir linn a chur Anita? Bhí a ainm, freisin Tosaíonn, leis an litir A, agus mothaíonn sé cosúil le atá déanta againn le praiseach fiú níos mó ar an bhfadhb. Tá muid anois leanas a chur isteach láithreach, chur isteach am ar tairiseach, i struchtúr sonraí seachas cás níos measa-líneach, ach cad is féidir linn a dhéanamh leis an Anita sa chás seo? Cad iad an dá rogha, i ndáiríre? Yeah? [Freagra na Mac Léinn, dothuigthe] Maith go leor, mar sin d'fhéadfadh muid a bheith gné eile. Sin maith. Mar sin, is féidir linn rudaí a thógáil amach i 3D mar phléamar bhéal ar an Luan. D'fhéadfadh muid a chur eile rochtain anseo, ach is dócha nach bhfuil aon, tá mé ag iarraidh seo a choinneáil simplí. Is é an sprioc iomlán anseo go bhfuil láithreach leanúnach-am rochtana, mar sin tá go cur chastacht iomarca. Cad iad na roghanna eile nuair a iarraidh a chur isteach Anita isteach sa struchtúr sonraí? Yeah? [Freagra na Mac Léinn, dothuigthe] Chéasta. Mar sin, d'fhéadfadh muid a bhogadh gach duine eile síos, cosúil le Charlie nudges síos Bob agus Alice, agus ansin chuir muid Anita nuair is mian léi i ndáiríre a bheith. Ar ndóigh, anois, níl a éifeacht taobh seo. Is é seo an struchtúr sonraí is dócha úsáideach ní mar ba mhaith linn do dhaoine isteach uair amháin ach mar ba mhaith linn a sheiceáil má tá siad ann ina dhiaidh sin más mian linn a phriontáil amach gach ceann de na hainmneacha sa struchtúr sonraí. Táimid ag dul rud éigin a dhéanamh leis na sonraí seo ar deireadh thiar. Mar sin, anois tá muid de chineál ar screwed thar Alice, atá ar a thuilleadh nuair a tá sí ceaptha a bheith. Is é Ná Bob, ná Charlie. Mar sin, b'fhéidir nach bhfuil sé seo den sórt sin ag smaoineamh maith. Ach go deimhin, tá sé seo rogha amháin. D'fhéadfadh muid a athrú gach duine síos, nó heck, tháinig Anita déanach leis an cluiche, cén fáth nach bhfuil muid a chur díreach Anita Ní anseo, ní anseo, ní anseo, a ligean ar chur díreach aici beagán níos ísle ar an liosta. Ach tosaíonn ansin an fhadhb seo a chineachadh arís. D'fhéadfá a bheith in ann teacht Alice toirt, bunaithe ar a ainm ar dtús. Agus Bob láithreach, agus Charlie. Ach ansin tú ag féachaint do Anita, agus a fheiceann tú, hmm, tá Alice ar an mbealach. Bhuel, lig dom a sheiceáil thíos Alice. Ní Bob Anita. Ní Charlie Anita. Ó, tá Anita. Agus má leanann tú ar an traein sin de loighic léir ar an mbealach, cad é an t-am is measa ar chás reáchtáil a aimsiú nó a chur isteach Anita isteach sa struchtúr sonraí nua? Tá sé O (n), ceart? Mar gheall ar an gcás is measa, níl Alice, Bob, Charlie. . . léir ar an mbealach síos go dtí duine éigin darb ainm "Y", agus mar sin níl ach amháin ar an láthair ar chlé. Thankfully, ní mór dúinn aon duine ar a dtugtar "Z", mar sin chuir muid Anita ag bun an-. Ní Tá réiteach i ndáiríre go fhadhb. Mar sin, b'fhéidir mór dúinn a thabhairt isteach an tríú toise. Agus casadh sé amach, más rud é is féidir linn seo a thabhairt isteach tríú toise, ní féidir linn é seo a dhéanamh go foirfe, ach tá an Soitheach Naofa ag dul a bheith ag fáil leanúnach-am leanas a chur isteach agus insertions dinimiciúil ionas go nach bhfuil againn go crua-cód le sraith de mhéid 26. Is féidir linn a chur isteach mar go leor ainmneacha mar is mian linn, ach a ligean ar ár n-5-nóiméad sos a ghlacadh anseo agus a dhéanamh ansin i gceart. Gach ceart. Leag mé an scéal suas go leor go saorga ag roghnú Alice agus ansin Bob agus ansin Charlie agus ansin Anita, a bhfuil a ainm a bhí ag dul ar ndóigh go collide le Alice. Ach tá an cheist dar críoch muid ar an Luan le díreach cé chomh dócha go bhfuil sé go mbeadh tú a fháil ar na cineálacha na n-imbhuailtí? I bhfocail eile, má thosaíonn muid chun seo a úsáid struchtúr tábla, atá i ndáiríre ach le sraith, sa chás seo de 26 ionad, cad más rud é ár n-ionchur in ionad a dháileadh go haonfhoirmeach? Níl sé go saorga Alice agus Bob agus Charlie agus David agus mar sin in ord aibítre de, tá sé dháileadh go haonfhoirmeach thar A trí Z. B'fhéidir beidh orainn a fháil ach t-ádh agus ní táimid ag dul go mbeadh dhá A nó dhá B le dóchúlacht an-ard, ach mar a dúirt duine éigin amach, má dhéanann muid ginearálaithe an fhadhb seo agus ní 0-25 ach, a rá, 0 go 364 nó 65, go minic líon na laethanta i mbliain tipiciúil, agus d'iarr an cheist, "Cad é an dóchúlacht go mbeidh bheirt againn sa seomra seo ar an lá breithe céanna?" Chur ar bhealach eile, cad é an dóchúlacht go bhfuil dhá cheann de dúinn ainm ag tosú le A? Is é an cineál ceiste mar an gcéanna, ach an spás seoladh, an spás cuardaigh, tá níos mó i gcás laethanta breithe, toisc go bhfuil muid an oiread sin lá níos mó i rith na bliana ná litreacha sa aibítir. Cad é an dóchúlacht imbhualadh? Bhuel, is féidir linn smaoineamh ar seo ag figuring amach an mata ar an mbealach os coinne. Cad é an dóchúlacht nach imbhuailtí? Bhuel, a deir an abairt anseo go bhfuil an méid an dóchúlacht má níl ach duine amháin sa seomra seo, go bhfuil siad lá breithe ar leith? Tá sé 100%. Toisc má tá ach duine amháin sa seomra, Is féidir a bheith aige nó aici lá breithe aon cheann de na 365 lá amach as na bliana. Mar sin, tugann roghanna 365/365 dom luach 1. Dá bhrí sin tá an dóchúlacht atá i gceist i láthair na huaire ach 1. Ach má tá an dara duine sa seomra, cad é an dóchúlacht go bhfuil a gcuid lá breithe éagsúla? Níl ach 364 lá is féidir, bliain leap neamhaird, as a lá breithe gan collide leis na daoine eile. Mar sin, 364/365. Má thagann tríú duine i, tá sé 363/365, agus mar sin de. Mar sin, a choinneáil orainn a iolrú le chéile ar na codáin, atá ag éirí níos lú agus níos lú, Is é a dhéanamh amach cad é an dóchúlacht go bhfuil gach duine againn breithlá ar leith? Ach ansin is féidir linn, ar ndóigh, a ghlacadh ach an freagra agus é a smeach thart agus a dhéanamh 1 lúide gach ceann de sin, slonn beidh orainn a fháil sa deireadh más cuimhin leat an chúl do leabhar math, tá sé rud beag mar seo, a bhfuil i bhfad níos éasca léirmhíniú go grafach. Agus tá an ghrafaic anseo ar an ais x líon na laethanta breithe, nó ar líon na ndaoine a bhfuil laethanta breithe, agus ar an ais y an dóchúlacht chluiche. Agus is é an méid seo á rá go má tá tú, a ligean ar a rá, fiú, a ligean ar roghnaigh rud éigin cosúil le 22, 23. Má tá 22 nó 23 duine sa seomra, an dóchúlacht go bhfuil dhá cheann de na daoine beag ag dul go bhfuil an lá breithe céanna i ndáiríre ard Super, combinatorially. 50 odds% go in aicme ach 22 duine, seimineár, go praiticiúil, 2 de na daoine ag dul a bheith ar an lá breithe céanna. Mar níl an oiread sin bealaí inar féidir leat a bheith ar an lá breithe céanna. Níos measa fós, má fhéachann tú ar an thaobh na láimhe deise den chairt, ag an am a bhfuil tú rang le 58 mac léinn ann, Is é an dóchúlacht 2 daoine a bhfuil lá breithe Super, ard Super, beagnach 100%. Anois, Tá gur saghas rud spraoi faoin saol fíor. Ach na himpleachtaí, anois, do na struchtúir sonraí agus faisnéis a stóráil Ciallaíonn sé sin go díreach ag glacadh leis go bhfuil tú, deas glan, dáileadh aonfhoirmeach na sonraí agus tá tú eagar mór go leor ionas go luífidh sé a bunch de rudaí Ní chiallaíonn sé bhfuil tú ag dul le daoine a fháil i suímh ar leith. Tá tú ag dul go imbhuailtí a bheith acu. Mar sin, ar an gcoincheap sin de hashing, mar tá sé ar a dtugtar, ag cur ionchur cosúil le "Alice" agus massaging sé ar bhealach éigin agus ag fáil ansin ar ais le freagra cosúil le 0 nó 1 nó 2. Dul ar ais roinnt aschur ó fheidhm sin atá cráite ag an dóchúlacht imbhualadh. Mar sin, conas is féidir linn déileáil leis na imbhuailtí? Bhuel, ar an gcás amháin, is féidir linn a ghlacadh ar an smaoineamh a bhí le tuiscint go. Is féidir linn a athrú ach gach duine síos, nó b'fhéidir, beagán níos simplí, seachas gach duine bogadh eile, a ligean ar bogadh díreach Anita go bun an láthair atá ar fáil. Mar sin, má tá Alice in 0, tá Bob in 1, tá Charlie i 2, beidh orainn a chur díreach Anita ag suíomh 3. Agus tá sé seo le teicníc i struchtúir sonraí ar a dtugtar líneach deacra. Líneach toisc go bhfuil tú ag siúl ach an líne seo, agus tá tú saghas deacra do spotaí ar fáil sa struchtúr sonraí. Ar ndóigh, chineachann seo san O (n). Má tá an struchtúr sonraí i ndáiríre iomlán, níl 25 duine ann cheana féin, agus ansin a thagann Anita chomh maith, críochnaíonn sí suas ar cad a bheadh ​​suíomh Z, agus go bhfuil fíneáil. N-oireann sí fós, agus is féidir linn í a fháil ina dhiaidh sin. Ach ba é seo contrártha leis an sprioc de rudaí a bhrostú. Mar sin, cad má thugamar isteach in ionad an tríú toise? Sin teicníc ar a dtugtar de ghnáth shlabhrú ar leith, nó a bhfuil slabhraí. Agus cad is tábla hash anois, an struchtúr tábla, agus Is é do tábla díreach le sraith de leideanna. Ach cad iad leideanna pointe buille faoi thuairim cad é? Tá liosta nasctha. Mar sin, cad má táimid a ghlacadh an chuid is fearr den dá cheann de na saol? Táimid arrays úsáid le haghaidh na innéacsanna tosaigh isteach sa struchtúr sonraí ionas gur féidir linn dul láithreach go dtí [0] [1], [30] nó mar sin de, ach mar sin go bhfuil roinnt solúbthacht agus is féidir linn oiriúnach Anita agus Alice agus Adam agus aon ainm, muid in iúl in ionad an ais eile ag fás treallach. Agus muid ar deireadh, mar an Luan, tá go cumas expressive le liosta nasctha. Is féidir linn ag fás le struchtúr sonraí treallach. Nó, d'fhéadfadh muid a dhéanamh ach ollmhór 2-tríthoiseach eagar, ach tá go dul a bheith ina staid uafásach más rud é ceann de na sraitheanna i sraith 2-tríthoiseach Ní mór go leor le haghaidh an duine breise a bhfuil a ainm a tharlaíonn tús a chur leis A. Dia forbid ní mór dúinn a ath-leithroinnt ollmhór 2-tríthoiseach struchtúr díreach mar níl an oiread sin daoine ainmnithe A, go háirithe nuair a bhíonn daoine chomh beag darb ainm Z rud éigin. Tá sé ag dul ach a bheith an-tanaí sonraí struchtúr. Mar sin, nach bhfuil sé foirfe trí mhodh ar bith, ach anois againn ar a laghad a bhfuil an cumas a fháil láithreach i gcás ina mbaineann Alice nó Anita, ar a laghad ó thaobh an ais ingearach, agus ansin ní mór dúinn ach chun cinneadh a dhéanamh nuair a chur Anita nó Alice sa liosta seo nasctha. Más rud é nach ndéanaimid cúram faoi rudaí a shórtáil, conas a d'fhéadfadh go tapa muid isteach Alice i struchtúr mar seo? Tá sé am i gcónaí. Innéacs muid isteach [0], agus mura bhfuil aon duine ann, Alice Téann ag tús an liosta sin nasctha. Ach ní ar sin le déileáil go mór. Toisc má thagann Anita ansin feadh roinnt ar líon na céimeanna ina dhiaidh sin, ní i gcás Anita leis? Bhuel, [0]. Oop. Alice cheana féin sa liosta nasctha. Ach más rud é nach ndéanaimid cúram faoi sórtáil na hainmneacha, is féidir linn dul díreach Alice os a chionn, cuir isteach Anita, ach fiú go bhfuil am i gcónaí. Fiú má tá Alice agus Adam agus seo go léir eile a ainmneacha, nach bhfuil aistriú sé i ndáiríre iad go fisiciúil. Cén fáth? Toisc go raibh muid ach anseo le liosta nasctha, a bhfuil aithne aige bhí go bhfuil na nóid sin féin? Gach bhfuil tú a dhéanamh ná bogadh na blúiríní aráin. Bog na saigheada thart; ní gá duit a bhogadh go fisiciúil aon sonraí timpeall. Mar sin, is féidir linn a chur isteach Anita, sa chás sin, láithreach. Am tairiseach. Mar sin, ní mór dúinn i gcónaí-am lookup, agus tairiseach-am a chur isteach duine éigin cosúil le Anita. Ach de chineál ar oversimplifying ar fud an domhain. Cad a tharlaíonn má ba mhaith linn ina dhiaidh sin a fháil Alice? Cad a tharlaíonn má ba mhaith linn ina dhiaidh sin a fháil Alice? Cé mhéad céimeanna go bhfuil ag dul a ghlacadh? [Freagra na Mac Léinn, dothuigthe] Go díreach. Líon na ndaoine os comhair Alice ar an liosta nasctha. Mar sin, nach bhfuil sé go leor foirfe, mar gheall ar ár struchtúr sonraí, arís, tá an rochtain ingearach agus ansin tá sé ar na liostaí nasctha crochta - i ndáiríre, a ligean ar nach bhfuil a tharraingt sé eagar ar. Tá sé tar éis na liostaí seo nasctha crochta amach de sé go Breathnaíonn rud beag mar seo. Ach tá an fhadhb má Alice agus Adam agus seo go léir eile a n-ainmneacha suas go deireadh níos mó agus níos mó ann, aimsiú d'fhéadfadh duine deireadh suas ag cur a bunch de na céimeanna, bcause tá tú chun lean an liosta nasctha, bhfuil oibríocht líneach. Mar sin, i ndáiríre, ansin, is é an t-am isteach ar deireadh thiar O (n), áit a bhfuil n líon na n-eilimintí sa liosta. Roinnte ar, a ligean ar glaoch treallach é m, áit a bhfuil m líon na liostaí nasctha go bhfuil muid ar an ais ingearach. I bhfocail eile, má glacadh againn go fírinneach dáileadh aonfhoirmeach na n-ainmneacha, go hiomlán neamhréadúil. Níl ar ndóigh níos mó de na roinnt litreacha ná daoine eile. Ach má glacadh againn le haghaidh na huaire dáileadh aonfhoirmeach, agus ní mór dúinn a n daoine ar fad, agus slabhraí iomlán m ar fáil dúinn, ansin fad gach ceann de na slabhraí cothrom é ach ag dul a bheith an iomlán, n roinnt ar líon na slabhraí. Mar sin, n / m. Ach anseo nuair is féidir linn a bheith go léir cliste go matamaiticiúil. Is m ar tairiseach, mar níl líon seasta de na. Tá tú ag dul a dhearbhú do eagar ag an tús, agus nach mbeimid méid a athrú ar an ais ingearach. De réir sainmhíniú, tréimhsí fanachta atá socraithe. Tá sé ach an ais chothrománach, mar a déarfá, go bhfuil athrú. Mar sin go teicniúil, tá sé seo i gcónaí. Mar sin anois, an t-am isteach Is é O go leor i bhfad (n). Mar sin, nach mbraitheann go léir i bhfad níos fearr. Tá Ach cad é an fhírinne anseo? Bhuel, ar fad an am seo, ar feadh seachtaine, tá muid ag rá O (n ²). O (n), 2 x n ², - n, arna roinnt ar 2. . . ech. Tá sé díreach ² n. Ach anois, sa chuid seo den seimeastar, is féidir linn tús a chur ag caint faoi an saol fíor arís. Agus is é n / m go hiomlán níos tapúla ná díreach n-aonar. Má tá tú míle ainmneacha, agus tú iad a bhriseadh suas i buicéid il ionas go mbeidh tú ach deich ainmneacha i ngach ceann de na slabhraí, go hiomlán ag cuardach deich rudaí ag dul a bheith níos tapúla ná míle rudaí. Agus mar sin tá sé ar cheann de na tacair fhadhb atá le teacht ag dul chun dúshlán duit smaoineamh ar go díreach cé, yeah, asymptotically agus mathematically, is é seo fós ach líneach, a sucks go ginearálta nuair a iarraidh chun rudaí a aimsiú. I ndáiríre, tá sé ag dul a bheith níos tapúla ná mar a mar gheall ar an divisor. Agus mar sin tá ann dul arís a bheith ar an trádáil-uaire agus an choimhlint idir teoiric agus réaltacht, agus beidh ar cheann de na knobs tús a chur ag casadh ag an bpointe seo i Seimeastar Is é níos mó de na fírinne amháin agus muid ag saghas ullmhú le haghaidh deireadh semster, ar mar atá muid isteach ar fud an domhain cláir gréasáin, nuair i ndáiríre, tá feidhmíocht ag dul a chomhaireamh mar go bhfuil do chuid úsáideoirí ag dul go dtí tús le mothú agus a léirthuiscint cinntí droch-dhearadh. Mar sin, conas a dhéanann tú dul faoi chur i bhfeidhm nasctha - tábla hash le 31 heilimintí? Agus bhí an sampla roimhe seo treallach faoi breithlaethanta. Má tá duine lá breithe de 1 Eanáir nó Feabhra 1, beidh orainn iad a chur sa buicéad. Má tá sé 2 Eanáir, Feabhra 2, 2 Márta, beidh orainn iad a chur sa buicéad. Sin an fáth a bhí sé 31. Conas is féidir leat a fhógairt tábla hash? Is féidir é a simplí go leor, tá tábla * nód mo ainm treallach ar sé, [31]. Tugann sé seo dom 31 leideanna chun nóid, agus ceadaíonn sé go dom go bhfuil 31 leideanna chun liostaí nasctha fiú má tá na slabhraí dtús NULLComment. Cad é ba mhaith liom a chur más mian liom a stóráil "Alice," "Bob," "Charlie"? Bhuel, is gá dúinn a wrap na rudaí i struchtúr mar is gá dúinn Alice a chur in iúl do Bob, go pointe le Charlie, agus mar sin de. Ní féidir linn a bheith díreach ainmneacha féin, mar sin raibh mé in ann a chruthú struchtúr nua ar a dtugtar nód anseo. Cad is nód iarbhír? Cad is nód sa liosta nua nasctha? Is é an chéad rud, ar a dtugtar focal, chun an duine a ainm. FAD, is dócha, a bhaineann le fad uasta na an duine a ainm, is cuma cad é sin, 20, 30, 40 carachtair i gcásanna chúinne dÚsachtach, agus is é 1 le haghaidh cad é? Tá sé díreach an carachtar NULLComment breise, \ 0. Mar sin, tá an nód timfhilleadh "rud éigin" taobh istigh de féin, ach Dearbhaíonn sé freisin pointeoir ar a dtugtar eile ionas gur féidir linn slabhra Alice go Bob le Charlie agus mar sin de. Féidir a bheith NULLComment ach nach bhfuil gá a bheith. Ceisteanna ar bith ar na táblaí hash? Yeah? [Mac Léinn ag iarraidh ceist, dothuigthe] An eagar - ceist mhaith. Cén fáth go bhfuil an focal ruabhric i sraith seachas díreach * Char? Sa sampla seo beagán treallach, ní raibh mé ag iarraidh a rogha le malloc do gach ceann de na hainmneacha bunaidh. Bhí mé a dhearbhú uasmhéid de chuimhne ar an teaghrán ionas go bhféadfaí mé a chóipeáil isteach i struchtúr Alice \ 0 agus nach bhfuil chun déileáil le malloc agus saor in aisce agus a leithéidí. Ach raibh mé in ann é sin a dhéanamh dá mba mhaith liom a bheith níos mó comhfhiosach ar úsáid spáis. Dea-gceist. Mar sin a ligean iarracht a ghinearálú amach as an agus fócas an chuid eile den lá atá inniu ann ar struchtúir sonraí níos ginearálta agus fadhbanna eile gur féidir linn a réiteach ag baint úsáide as an bunúsacha céanna cé go bhfuil an struchtúir sonraí a d'fhéadfadh iad féin difriúil a sonraí. Mar sin, casadh sé amach san eolaíocht ríomhaireachta, crainn an-choitianta. Agus is féidir leat smaoineamh ar saghas crann cosúil le crann teaghlaigh, nuair a bhfuil roinnt fréamhacha, roinnt matriarch nó patriarch, grandma nó grandpa nó níos luaithe ar ais, faoi ​​bhun a bhfuil mamaí agus daidí nó deartháireacha éagsúla nó a leithéidí. Mar sin, tá struchtúr crann nóid agus é a clann, de ghnáth 0 leanaí nó níos mó do gach nód. Agus roinnt de na béarlagair a fheiceann tú sa phictiúr seo anseo Is é aon cheann de na páistí nó grandkids beag ar an imeall nach bhfuil aon saighde a thagann as dóibh, iad siúd na duilleoga mar a thugtar air, agus duine ar bith ar an taobh istigh Is nód istigh; is féidir leat glaoch sé rud ar bith feadh na línte. Ach tá an struchtúr seo go leor coitianta. Tá sé seo ar cheann beagán treallach. Tá leanbh amháin ar chlé, ní mór dúinn trí leanaí ar dheis, beirt pháistí ar bun na láimhe clé. Mar sin, is féidir linn a bheith difriúil-iarrachtaí crainn, ach má thosaíonn muid chun rudaí a chaighdeánú, agus d'fhéadfá a thabhairt chun cuimhne seo ó físeán Pádraig ar cuardaigh dénártha ó ghearrliosta roimhe Ní ar líne, cuardaigh dénártha a chur i bhfeidhm le sraith nó píosaí de pháipéar ar gclár dubh. Má ghlactar leis go raibh tú a shábháil ar do uimhreacha i struchtúr sonraí níos sofaisticiúla. D'fhéadfá a chruthú crann mar seo. D'fhéadfá a bheith nód dhearbhú i C, agus gur féidir le nód ar a laghad dhá ghné taobh istigh de sé a bheith. Is é ceann an líon is mian leat a stóráil, agus an duine eile - go maith, ní mór dúinn amháin níos mó. Is é an eile a leanaí. Mar sin tá anseo struchtúr eile sonraí. An uair seo, tá nód shainmhíniú mar a stóráil ar líon n agus ansin dhá threo; leanbh ar chlé agus ar dheis leanbh. Agus ní bhíonn siad treallach. Cad é suimiúil faoi an crann? Cad é an patrún i gcaoi atá leagtha síos againn é seo amach nó conas a leagtar Pádraig sé amach ina físeán? Tá sé de chineál ar léir go bhfuil roinnt shórtáil ar siúl anseo, Tá ach cad é an riail simplí? Yeah? [Freagra na Mac Léinn, dothuigthe] Perfect. Má tá tú Sracfhéachaint ar an, a fheiceann tú ar an líon beag ar thaobh na láimhe clé, líon mór ar thaobh na láimhe clé, ach is é sin fíor i gcás gach nód. I gcás gach nód, a leanbh chlé níos lú ná é, agus a leanbh ceart níos mó ná é. Cad ciallaíonn sé seo anois más mian liom a chuardach an struchtúr sonraí le haghaidh, abair, an uimhir 44, Tá mé chun tús a chur ag an fhréamh, mar gheall ar mar a bhfuil gach ceann de na níos casta struchtúir sonraí anois, ní mór dúinn ach pointeoir go rud amháin, an tús. Agus sa chás seo, is é an tús an fhréamh. Níl sé an deireadh chlé, tá sé an fhréamh an struchtúr seo. Mar sin, féach mé anseo tá 55, agus tá mé ag lorg 44. Cén treo is mian liom dul? Bhuel, ba mhaith liom dul go dtí an taobh clé, mar gheall ar ndóigh, tá an ceart ag dul a bheith ró-mhór. Mar sin, fógra anseo, tá tú saghas choincheapa de chopping an crann i leath mar ní atá tú ag dul síos go dtí an thaobh na láimhe deise. Mar sin anois mé ag dul ó na 55 go 33. Tá sé ró-bheag de líon. Táim ag lorg 44, ach anois tá a fhios agam má tá 44 sa crann, is féidir liom dul ar ndóigh leis an gceart. Mar sin, arís, tá mé bearradh an crann ina dhá leath. Tá sé deas i bhfad comhionann coincheapúil leis an leabhar teileafóin. Tá sé comhionann leis an méid a rinne muid leis na páipéir ar an gclár dubh, ach tá sé ina struchtúr níos sofaisticiúla a ligeann dúinn a dhéanamh i ndáiríre seo a roinnt agus a conquer ag dearadh an algartam, agus go deimhin, trasnú struchtúr mar seo - Whoops. Thrasnaíonn struchtúr mar seo, nuair a tá sé ach "dul ar an mbealach seo nó go bhealach dul," Ciallaíonn léir go bhfuil cód gur chrom d'intinn ar dtús nuair a chur chun feidhme in alt nó ag siúl tríd sa bhaile, ar chuardach dhénártha, úsáid a bhaint as athchúrsáil nó atriall, tá sé ina pian i muineál. Faigh an eilimint lár, a dhéanamh ansin do chothromú suas nó síos. Níl áilleacht seo mar is féidir linn úsáid a bhaint anois athchúrsáil arís, ach i bhfad níos mó cleanly. Go deimhin, má tá tú ag an uimhir 55 agus is mian leat a fháil 44, théann tú fágtha sa chás seo, ansin cad a dhéanann tú? Ritheann tú an algartam céanna. Leat seiceáil luach an nód, ansin a théann tú ar chlé nó ceart. Ansin tú ag seiceáil luach an nód, téigh ar chlé nó ceart. Tá sé seo oiriúnach breá do athchúrsáil. Mar sin, cé san am atá caite atá déanta againn roinnt samplaí go cothrom treallach a bhaineann le cuardach ar nach raibh gá a bheith recursive, le stuctures sonraí, go háirithe crainn, tá sé ina iarratas foirfe ar an smaoineamh a ghlacadh ar fhadhb, crapadh é, agus ansin a réiteach leis an gcineál céanna, ach níos lú, clár. Mar sin, níl eile struchtúr sonraí gur féidir linn a thabhairt isteach. Tá sé seo ar cheann deartha ar an gcéad amharc a chuardach cryptic, ach tá an ceann seo iontach. Mar sin, tá sé seo le struchtúr sonraí ar a dtugtar trie, trie, a bhfuil oidhreacht ón aisghabháil focal, nach bhfuil pronounced ath-iarracht-Val, ach go bhfuil an méid a iarrann an domhan na rudaí seo. Iarracht. T-r-i-e. Is struchtúr crann de chineál éigin, ach gach ceann de na nóid i trie cosúil go bhfuil cad é? Agus tá sé seo le beagán míthreorach toisc go bhfuil sé de chineál ar ghiorrú. Ach tá sé cosúil go bhfuil gach nód sa trie i ndáiríre le sraith. Agus cé nach bhfuil an t-údar an léaráid seo a thaispeántar é, sa chás seo, tá an trie struchtúr sonraí bhfuil sé mar aidhm sa saol é sin le focail a stóráil cosúil le A-l-i-c-e nó B-o-b. Bhealach agus an i seo siopaí sonraí Alice agus Bob agus Charlie agus Anita agus mar sin de Is é a úsáideann sé le sraith trína a stóráil Alice i trie, tús a chur againn ar an nód fhréamh a bhreathnaíonn ar nós eagar, agus tá sé scríofa i nodaireacht luathscríbhinne. An t-údar ar lár abcdefg toisc nach raibh aon ainmneacha leis sin. Léirigh siad ach M agus P agus T, ach sa chás seo, a ligean ar bogadh ar shiúl ó Alice agus Bob agus Charlie a roinnt ainmneacha atá anseo. Maxwell i ndáiríre sa léaráid. Mar sin, conas a rinne an siopa údar M-a-x-w-e-l-l? Sé nó sí a thosaigh ag an nód fréimhe, agus chuaigh sé chun [M], agus mar sin thart ar 13, an suíomh 13ú sa eagar. Ansin ó ann, níl a pointeoir. A pointeoir a dtiocfaidh eile eagar. Ó tá an t-údar innéacsaithe isteach eagar ag suíomh A, mar a léirítear ann ar barr ar clé, agus ansin lean sé nó sí go pointeoir eile eagar, agus chuaigh sé chun an pointeoir ag suíomh X. Ansin, sa suíomh W chéad sraith, E, L, L, agus mar sin de, agus ar deireadh, a ligean ar iarracht iarbhír pictiúr a chur leis seo. Cén cuma nód mhaith i cód? Tá A nód i trie le sraith de threo le nóid níos mó. Ach tá go fuair freisin a bheith de shaghas éigin luach Boole, ar a laghad sa chur i bhfeidhm. Tharlóidh liom a ghlaoch air is_word. Cén fáth? Toisc nuair a bhíonn tú isteach Maxwell, nach bhfuil tú ag chur isteach rud ar bith isteach sa struchtúr sonraí. Níl tú ag scríobh M. Ní bhíonn tú ag scríobh X. Gach bhfuil tú a dhéanamh é seo a leanas leideanna. An pointeoir gur ionann M, ansin an pointeoir gur ionann A, ansin an pointeoir gur ionann X, ansin W, E, L, L, ach an méid is gá duit a dhéanamh ag deireadh saghas dul, a sheiceáil, tháinig mé ar an suíomh seo. Bhí focal a chríochnaíonn anseo i struchtúr sonraí. Mar sin, cad a trie líonadh i ndáiríre leis agus an t-údar roghnaigh chun ionadaíocht a dhéanamh na terminuses le triantáin beag. Ciallaíonn sé seo go díreach é an bhfíric seo triantán anseo, an luach Boole de fíor Ciallaíonn sé sin má théann tú ar gcúl sa gcrann, go gciallaíonn focal ainmnithe Maxwell é seo. Ach an focal foo, mar shampla, nach bhfuil an crann, mar má thosaíonn mé ag an nód fhréamh suas anseo ag barr, Níl aon pointeoir f, ní pointeoir o, ní pointeoir o. Ní Foo ainm sa bhfoclóir. Ach ag gcodarsnacht leis sin, Turing, t-u-r-i-n-g. Arís, ní raibh mé a stóráil t nó u nó r nó i nó n nó g. Ach rinne mé siopa sa struchtúr sonraí ar luach ar bhealach fíor síos anseo ar an nód - sa crann ag leagan síos an luach Boole de is_word go fíor. Mar sin, is trie chineál seo struchtúr meta-suimiúil, i gcás nach bhfuil tú ag a stóráil i ndáiríre na focail féin don chineál seo foclóra. Chun a bheith soiléir, go bhfuil tú ag a stóráil ach tá nó gan aon, tá focal a chríochnaíonn anseo. Tá Anois, cad é an impleacht? Má tá tú 150,000 focal i bhfoclóir go bhfuil tú ag iarraidh a stóráil i gcuimhne ag baint úsáide as rud éigin cosúil le liosta nasctha, bhfuil tú ag dul go bhfuil 150,000 nóid i do liosta nasctha. Agus d'fhéadfadh a aimsiú ar cheann de na focail sin in ord aibítre a ghlacadh O (n) am. Am Líneach. Ach i gcás anseo ar trie, cad é an t-am ag rith a aimsiú focal? Casadh sé amach ar an áilleacht anseo go fiú má tá tú 149,999 focal cheana féin sa bhfoclóir seo, arna cur chun feidhme leis an struchtúr sonraí, cé mhéad ama a thógann sé a fháil nó a chur isteach duine amháin níos mó i sin, cosúil le Alice, Alice? Bhuel, tá sé ach 5, b'fhéidir 6 céimeanna le haghaidh an carachtar trailing. Mar gheall ar an presense na n-ainmneacha eile sa struchtúr ní a fháil ar an mbealach isteach Alice. Thairis sin, a aimsiú Alice uair amháin go bhfuil 150,000 focal sa bhfoclóir ní fháil ar do bhealach a aimsiú Alice ar chor ar bith, toisc go bhfuil Alice. . . . . anseo, mar fuair mé luach Boole. Agus nach bhfuil mura bhfuil aon Boole fíor, Alice ansin sa struchtúr seo sonraí na bhfocal. I bhfocail eile, an t-am ag rith na rudaí a aimsiú agus a chur isteach i rudaí isteach sa nua Tá sonraí struchtúr trie O - nach bhfuil sé n. Toisc go bhfuil an presense de 150,000 duine níl aon éifeacht ar Alice, is cosúil. Mar sin a ligean glaoch ar é k, áit a bhfuil k an fad uasta focal i mBéarla a bhfuil de ghnáth gan níos mó ná 20-rud éigin carachtair. Mar sin, is tairiseach é k. Mar sin, an Soitheach Naofa is cosúil go bhfuil le fáil anois is é sin de am, trie gcónaí iatáin, do lookups, do scriosadh. Mar gheall ar líon na rudaí cheana féin ar an struchtúr, nach bhfuil a fiú ann go fisiciúil. Arís, tá siad ag réiteach go díreach ar a sheiceáil amach, tá nó gan aon, nach bhfuil aon tionchar ar a chuid ama ag rith amach anseo. Ach tá go fuair a bheith ina ghabháil, ar shlí nach mbeadh againn amú an oiread sin ama ar gach na struchtúir sonraí eile ach a fháil ar deireadh leis an gceann a rúnda go iontach. Mar sin, cén praghas atá ag íoc againn chun seo a bhaint amach greatness anseo? Spás. Is é seo an rud is ollmhór. Agus ar an gcúis go bhfuil an t-údar Ní raibh i láthair anseo, fógra go bhfuil gach ceann de na rudaí a bhfuil cuma arrays, ní raibh sé a tharraingt ar an gcuid eile den chrann, an chuid eile den trie, toisc go bhfuil siad nach bhfuil ach a bhaineann leis an scéal. Ach tá gach ceann de na nóid Super leathan, agus tógann sé gach nód sa crann suas 26 nó i ndáiríre d'fhéadfadh a bheith, 27 carachtair mar gheall sa chás seo lena n-áirítear mé spás do apostrophe ionas go bhféadfadh muid a bheith focail apostrophized. Sa chás seo, tá na arrays leathan. Mar sin, cé nach bhfuil siad ag picutured, Bíonn seo suas méid ollmhór RAM. D'fhéadfadh a bheith go maith, especilly i crua-earraí nua-aimseartha, ach go bhfuil an tradeoff. Faighimid níos lú ama ag caitheamh níos mó spáis. Mar sin, i gcás ina sé seo ag dul ar fad? Bhuel, a ligean ar a dhéanamh - ligean ar a fheiceáil anseo. Déanaimis a dhéanamh léim ar an Guy anseo. Creid nó ná creid, spraoi an oiread agus is go bhfuil C a bhí le tamall anois, táimid ag teacht ar an pointe i Seimeastar ina sé an am a aistriú go dtí rudaí níos nua-aimseartha. Rudaí ar leibhéal níos airde. Agus cé haghaidh an chéad chúpla seachtain beidh muid ag leanúint ar aghaidh go fóill a thumadh féin i saol na leideanna agus bainistíocht cuimhne a fháil go chompord leis ar féidir linn a thógáil ansin ar, Is é an cluiche deiridh sa deireadh thiar a thabhairt isteach, ní ironically, an teanga seo. Beidh muid a chaitheamh, ar nós 10 nóiméad ag caint faoi HTML. Tá gach HTML teanga marcála, agus cad is teanga marcála Tá na sraitheanna de lúibíní oscailte agus lúibíní dúnta a rá 'a dhéanamh ar an cló trom' 'Seo a dhéanamh gcló iodálach', 'seo a dhéanamh lárnach'. Níl sé go léir go suimiúil go hintleachtúil, ach tá sé Super úsáideach. Agus tá sé cinnte omnipresent na laethanta. Ach cad cumhachtach mar gheall ar an domhan de HTML, agus cláir gréasáin níos ginearálta, ag tógáil rudaí dinimiciúil; scríobh cód i dteangacha cosúil PHP nó Python nó Ruby nó Java nó C #. Really, tá cuma cad é do rogha teanga, agus a ghiniúint HTML dinimiciúil. Ag giniúint rud ar a dtugtar CSS dinimiciúil. Stílbhileoga cascáideacha, a bhfuil freisin faoi aeistéitic. Agus mar sin cé go, lá atá inniu ann, má théim chuig roinnt suíomh gréasáin cosúil leis an Google.com ar an eolas, agus a théann mé a fheiceáil, forbróir, foinse dearcadh, a b'fhéidir déanta agat roimh, ach ag dul fhoinse a fheiceáil, Breathnaíonn an stuif is dócha go leor cryptic. Ach is é seo an cód bunúsach go gcuireann Google.com. Ar an ceann tosaigh. Agus ar ndóigh, is é seo go léir fluffy aeistéitic stuif. Is é seo an CSS suas anseo. Má Coinneoidh mé scrollaigh síos beidh orainn a fháil ar roinnt rudaí dathchódaithe. Tá sé seo HTML. Breathnaíonn cód Google cosúil le praiseach, ach má oscailt iarbhír suas fuinneog éagsúla, is féidir linn a roinnt struchtúr a fheiceáil seo. Má osclaíonn mé suas, fógra anseo, tá sé beagán níos inléite. Táimid ag dul a fheiceáil roimh i bhfad gclib seo, [focal] Is chlib, HTML, ceann, comhlacht, div, script, limistéar téacs, réise, dírithe div. Agus é seo a shórtáil freisin cryptic-lorg ar an gcéad amharc, ach seo a leanas go léir ar an praiseach patrúin áirithe, agus patrúin aithrise, ionas go uair a fháil againn an Basics síos, beidh tú in ann a scríobh cód mar seo agus a ionramháil ansin cód mar seo ag baint úsáide as fós teanga eile, ar a dtugtar JavaScript. Agus is é JavaScript teanga a ritheann taobh istigh de bhrabhsálaí lá atá inniu ann a úsáid againn ar chúrsaí Harvard, don uirlis siopadóireachta chúrsa go n-úsáideann Google léarscáileanna a thabhairt duit a bunch iomlán de fuinneamh, tugann Facebook leat a thaispeáint nuashonruithe stádas an toirt, Twitter úsáideann sé a thaispeáint duit tweets láithreach. Seo go léir cuirfimid tús a thumadh féin isteach Ach a bheith ann, ní mór dúinn tuiscint a fháil ar rud beag mar gheall ar an Idirlíon. Is é seo an gearrthóg anseo ach nóiméad ar fad, agus a ligean ar glacadh leis do anois tá sé seo, i ndáiríre, conas a oibríonn an Idirlíon mar teaser do cad atá ar tí teacht. A thabhairt liom tú "laochra ar an Idirlíon." [♫ ceol cór Mall ♫] [Scéalaí Fireann] Tháinig sé le teachtaireacht. Le prótacal ar fad a chuid féin. [♫ ceol níos tapúla leictreonach ♫] Tháinig sé go dtí saol na ballaí dóiteáin fionnuar, ródairí uncaring, agus contúirtí i bhfad níos measa ná bás. Tá sé go tapa. Tá sé láidir. Tá sé TCP / IP, agus tá sé fuair do sheoladh. Laochra an glan. [MALAN] An tseachtain seo chugainn, mar sin. An tIdirlíon. Cláir gréasáin. Is é seo an CS50. [CS50.TV]