DOUG LLOYD: Felly, yn CS50, rydym wedi cynnwys llawer o strwythurau data gwahanol, iawn? Rydym wedi gweld arrays, a'u cysylltu rhestrau, a thablau hash, a geisiau, staciau a ciwiau. Byddwn hefyd yn dysgu ychydig am goed a phentyrrau, ond mewn gwirionedd mae'r rhain i gyd yn unig yn dod i ben draw yn amrywiadau ar thema. Mewn gwirionedd mae yna rhain math o bedwar syniad sylfaenol Gall fod popeth arall yn berwi i lawr i. Araeau, rhestrau cysylltiedig, tablau hash, a geisiau. Ac fel y dywedais, mae amrywiadau arnynt, ond mae hyn yn eithaf llawer yn mynd i grynhoi popeth rydyn ni'n mynd i siarad am yn y dosbarth hwn o ran C. Ond sut mae hyn i gyd mesur i fyny, dde? Rydym wedi siarad am y manteision a'r anfanteision o bob un mewn fideos ar wahân arnynt, ond mae llawer o rifau cael eu taflu o gwmpas. Mae llawer o gyffredinol meddyliau cael eu taflu o gwmpas. Gadewch i ni geisio atgyfnerthu i mewn dim ond un lle. Gadewch i ni bwyso a mesur y manteision yn erbyn yr anfanteision, ac ystyried pa strwythur data Efallai fod y data cywir strwythur ar gyfer eich sefyllfa benodol, pa bynnag fath o ddata yr ydych yn storio. Nid ydynt o reidrwydd bob amser angen i chi defnyddio'r mewnosod gyflym super, dileu, a am-edrych o trie os ydych yn wir nid ydynt yn poeni am mewnosod a dileu gormod. Os oes angen dim ond ar hap yn gyflym mynediad, efallai amrywiaeth yn well. Felly gadewch i ni distill hynny. Gadewch i ni siarad am bob un o'r pedwar mathau pwysig o strwythurau data ein bod wedi siarad am, ac ond yn gweld pryd y gallent fod yn dda, a phan efallai na fyddant yn mor dda. Felly, gadewch i ni ddechrau gyda arrays. Felly mewnosod, dyna fath o ddrwg. 

Mewnosod ar ddiwedd amrywiaeth yn iawn, os ydym yn adeiladu amrywiaeth wrth i ni fynd. Ond os bydd angen i fewnosod elfennau i mewn i'r canol, yn meddwl yn ôl i fewnosod didoli, mae llawer o symud i ffitio elfen mewn 'na. Ac felly os ydym yn mynd i fewnosod yn unrhyw le ond diwedd amrywiaeth, dyna debyg nad mor fawr. 

Yn yr un modd, dileu, oni bai ein bod yn dileu o ddiwedd amrywiaeth, Nid yw mor fawr os na thebyg hefyd nid ydym am adael bylchau gwag, sydd fel arfer nid ydym yn ei wneud. Rydym yn awyddus i gael gwared ar elfen, ac Yna fath o yn ei gwneud yn glyd eto. Ac felly ddileu elfennau o amrywiaeth, hefyd nid mor fawr. 

Am-edrych, fodd bynnag, yn wych. Mae gennym fynediad ar hap, am-edrych o amser yn gyson. Rydym yn unig yn dweud saith, ac rydym yn mynd i adleoli amrywiaeth saith. Rydym yn dweud 20, gyda ewch i amrywiaeth adleoli 20. Nid oes rhaid i ni ailadrodd ar draws. Dyna 'n bert da. 

Araeau hefyd yn gymharol hawdd i ddatrys. Bob tro y byddwn yn siarad am didoli algorithm, megis didoli dethol, didoli fewnosod, didoli swigen, uno didoli, rydym bob amser yn defnyddio araeau i wneud hynny, oherwydd araeau yn eithaf hawdd i'w didoli, o'i gymharu â'r strwythurau data rydym wedi gweld hyd yn hyn. 

Maent hefyd yn gymharol fach. Does dim llawer o le ychwanegol. Rydych yn unig a neilltuwyd yn union gymaint fel y bydd angen i chi gynnal eich data, a dyna 'n bert lawer iddo. Felly, maent yn eithaf bach ac yn effeithlon yn y ffordd honno. Ond anfantais arall, fodd bynnag, yw eu bod yn sefydlog o ran maint. Mae'n rhaid i ni ddatgan yn union sut mawr rydym eisiau i'n amrywiaeth i fod, a dim ond cael un ergyd yn ei. Ni allwn dyfu ac yn crebachu ei. 

Os bydd angen i dyfu neu leihau ei, rydym yn Mae angen i ddatgan amrywiaeth hollol newydd, gopïo'r holl elfennau'r amrywiaeth cyntaf i mewn i'r ail arae. Ac os ydym yn miscalculated bod pryd, mae angen ei wneud eto. Nid mor fawr. Felly nid araeau yn rhoi'r hyblygrwydd i ni i gael niferoedd amrywiol o elfennau. 

Gyda rhestr cysylltiedig, mewnosod yn eithaf hawdd. Rydym yn unig dacio ar y tu blaen. Dileu hefyd yn eithaf hawdd. Mae'n rhaid i ni ddod o hyd i'r elfennau. Mae hynny'n golygu rhywfaint o chwilio. 

Ond unwaith y byddwch wedi dod o hyd i'r elfen ydych yn chwilio am, y cyfan sydd angen i chi ei wneud yn newid pwyntydd, o bosibl dau os oes gennych yn gysylltiedig list-- yn ddwbl rhestr gysylltiedig, rather-- ac yna gallwch jyst ddim y nôd. Nid oes rhaid i chi symud popeth o gwmpas. Rydych yn unig yn newid dau awgrymiadau, felly dyna 'n bert gyflym. 

Am-edrych yn ddrwg fodd bynnag, dde? Er mwyn i ni ddod o hyd i elfen mewn rhestr cysylltiedig, boed yn unigol neu ddwbl cysylltiedig, mae'n rhaid i ni llinol chwilio amdano. Mae'n rhaid i ni gychwyn ar ddechrau a symud y diwedd, neu'n dechrau ar y diwedd yn symud i'r dechrau. Nid oes gennym fynediad ar hap anymore. Felly, os ydym yn gwneud llawer o chwilio, efallai Nid rhestr cysylltiedig yn mor dda i ni. 

Maen nhw hefyd yn wir anodd i ddidoli, dde? Yr unig ffordd y gallwch 'n sylweddol ddatrys rhestr cysylltiedig yw i ddatrys y wrth i chi adeiladu ei. Ond os byddwch yn datrys y mater wrth i chi adeiladu ei, eich bod bellach gan wneud mewnosodiadau gyflym anymore. Nid ydych ond yn mynd i'r afael pethau ar y tu blaen. Mae'n rhaid i chi ddod o hyd i'r fan a'r lle cywir i roi, ac yna eich mewnosod yn dod yn unig am mor ddrwg fel fewnosod yn arae. Felly nid yw'r rhestrau cysylltiedig yn mor fawr ar gyfer didoli data. 

Maen nhw hefyd yn eithaf bach, maint-ddoeth. Rhestr gysylltiedig ychydig ddwbl yn fwy na'r rhestrau cysylltiedig yn unigol, sydd ychydig yn fwy na araeau, ond nid yw'n llawer iawn o le gwastraffu. Felly, os oes lle yn brin, ond Nid premiwm mewn gwirionedd dwys, gallai hyn fod y ffordd iawn i fynd. 

Tablau hash. Gosod i mewn i dabl hash yn weddol syml. Mae'n broses dau gam. Yn gyntaf mae angen i redeg ein data trwy swyddogaeth hash i gael cod hash, ac yna rydym yn mewnosod yr elfen mewn i'r tabl hash yn y cod hash lleoliad. 

Dileu, yn debyg i'r rhestr gysylltiedig, yn hawdd ar ôl i chi ddod o hyd i'r elfen. Mae'n rhaid i chi ddod o hyd iddo yn gyntaf, ond wedyn pan fyddwch yn dileu y peth, 'ch jyst angen i chi gyfnewid un neu ddau o awgrymiadau, os ydych yn defnyddio gadwyno ar wahân. Os ydych yn defnyddio treiddgar, neu os nad ydych yn gan ddefnyddio gadwyno o gwbl yn eich tabl hash, dileu yn hawdd iawn mewn gwirionedd. Y cyfan sydd angen i chi ei wneud yw hash y data, ac yna mynd i'r lleoliad. A chan dybio nad ydych yn ei wneud os oes gennych unrhyw gwrthdrawiadau, byddwch yn gallu dileu yn gyflym iawn. 

Yn awr, am-edrych yn lle pethau cael ychydig yn fwy cymhleth. Mae'n well ar gyfartaledd na rhestrau cysylltiedig. Os ydych yn defnyddio gadwyno, byddwch yn dal i gael rhestr gysylltiedig, sy'n golygu eich bod yn dal i gael yr chwilio anfantais rhestr cysylltiedig. Ond oherwydd eich bod yn cymryd eich cysylltu rhestr a hollti dros 100 neu 1,000 neu n elfennau yn eich tabl hash, rydych yn rhestrau cysylltiedig i gyd yn un nfed y maint. Maen nhw i gyd yn sylweddol llai. N Rydych wedi rhestrau cysylltiedig yn lle hynny o un rhestr gysylltiedig o faint n. 

Ac felly y byd go iawn yn gyson ffactor, yr ydym yn gyffredinol peidiwch â siarad am ran cymhlethdod amser, Nid mewn gwirionedd yn gwneud gwahaniaeth yma. Felly am-edrych yn dal i fod llinol chwilio os ydych yn defnyddio gadwyno, ond hyd y rhestr ydych yn chwilio trwy yn iawn, byr iawn o'i gymharu. Unwaith eto, os didoli yw eich nod yma, tabl hash yn yn ôl pob tebyg nid y ffordd iawn i fynd. Dim ond yn defnyddio amrywiaeth os didoli yn bwysig iawn i chi. 

A gallant redeg y gamut o faint. Mae'n anodd dweud a yw bwrdd hash yn fach neu'n fawr, gan ei fod yn wir yn dibynnu ar pa mor fawr yw eich tabl hash yn. Os ydych yn unig yn mynd i fod yn storio pum elfen yn eich tabl hash, a bod gennych dabl hash gyda 10,000 o elfennau ynddo, yn ôl pob tebyg rydych yn gwastraffu llawer o le. Cyferbyniad chi gall bod hefyd rhaid tablau hash gryno iawn, ond mae'r bwrdd hash llai yn cael, yr hiraf pob un o'r rhestrau cysylltiedig rheini cael. Ac felly does 'n sylweddol dim ffordd i ddiffinio yn union yr un maint â tabl hash, ond mae'n fwy na thebyg yn ddiogel i ddweud ei fod yn gyffredinol mynd i fod yn fwy na cysylltiedig Rhestr storio'r un data, ond yn llai na trie. 

A geisiau yn y pedwerydd o'r strwythurau hyn ein bod ni wedi bod yn siarad am. Mewnosod i mewn i trie yn gymhleth. Mae llawer o deinamig dyrannu cof, yn enwedig ar y dechrau, fel y ydych yn dechrau i adeiladu. Ond mae'n amser cyson. Dim ond yr elfen ddynol yma sy'n ei gwneud yn anodd. Gorfod dod ar draws pwyntydd null, malloc gofod, yn mynd yno, lle o bosib malloc oddi yno eto. Y math o ffactor bygwth awgrymiadau o ran dyrannu cof deinamig yw'r rhwystr i glirio. Ond unwaith y byddwch wedi clirio ei, mewnosod mewn gwirionedd yn dod yn eithaf syml, ac yn sicr yn bryd gyson. 

Dileu yn hawdd. Y cyfan sydd angen i chi ei wneud yw navigate i lawr cwpl o awgrymiadau a rhydd y nôd, felly dyna 'n bert da. Am-edrych hefyd yn eithaf cyflym. Dim ond ei seilio ar y hyd eich data. Felly os eich holl ddata yn pum llinynnau cymeriad, er enghraifft, eich bod yn storio pump llinynnau cymeriad yn eich trie, dim ond yn cymryd pum cam i hyd i'r hyn rydych chi'n chwilio amdano. Pump yn unig yn ffactor cyson, felly eto, mewnosod, dileu, ac am-edrych dyma holl amser yn gyson, yn effeithiol. 

Peth arall yw bod eich trie yn mewn gwirionedd yn datrys fath o barod, dde? Yn rhinwedd sut rydym yn elfennau mewnosod, trwy lythyr yn mynd trwy lythyr y allweddol, neu drwy digid digid o'r allweddol, Fel arfer, mae eich trie yn dod i ben i fyny yn cael math o didoli wrth i chi adeiladu. Nid yw'n wir yn gwneud synnwyr i feddwl am didoli yn yr un ffordd rydym yn meddwl am 'i ag araeau, neu restrau cysylltiedig, neu dablau hash. Ond mewn rhyw ystyr, eich trie cael ei ddidoli wrth i chi fynd. 

Mae anfantais, wrth gwrs, yw bod yn trie yn gyflym yn dod yn enfawr. O bob pwynt gyffordd, efallai y byddwch have-- os yw eich allwedd yn cynnwys ddigid, mae gennych 10 arall leoedd y gallwch fynd, a oedd yn golygu bod pob nod yn cynnwys gwybodaeth am y data rydych am ei storio ar y nod, yn ogystal â 10 o awgrymiadau. Pa rai, ar CS50 IDE, yn 80 bytes. Felly mae'n o leiaf 80 bytes am pob nod eich bod yn creu, ac nid yw hynny'n hyd yn oed yn cyfrif data. Ac os yw eich nodau yn llythyrau yn hytrach na digidau, Erbyn hyn mae gennych 26 o awgrymiadau o bob lleoliad. A 26 o weithiau 8, mae'n debyg 200 bytes, neu rywbeth fel 'na. Ac mae gennych gyfalaf a lowercase-- gallwch gweld lle roeddwn i'n mynd gyda hyn, dde? Gall eich nodau ca 'n sylweddol mawr, ac felly mae'r trie ei hun, ar y cyfan, gall cael fawr iawn, hefyd. Felly os gofod yn uchel premiwm ar eich system, Efallai na fydd trie yw'r ffordd gywir i fynd, er bod ei budd-daliadau eraill yn dod i chwarae. Rwy'n Doug Lloyd. Mae hyn yn CS50.