1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SIARADWR 1: pob hawl, felly rydym yn ôl. 3 00:00:13,120 --> 00:00:14,480 Croeso i CS50. 4 00:00:14,480 --> 00:00:16,510 Mae hyn yn y diwedd yr wythnos saith. 5 00:00:16,510 --> 00:00:20,200 Felly, dwyn i gof bod y tro diwethaf, rydym yn dechrau edrych ar ychydig yn fwy soffistigedig 6 00:00:20,200 --> 00:00:21,100 strwythurau data. 7 00:00:21,100 --> 00:00:25,110 Ers hyd yn hyn, i gyd oedd gennym mewn gwirionedd ar gael i ni oedd hyn, arae. 8 00:00:25,110 --> 00:00:29,340 >> Ond cyn i ni daflu y casgliad gan nad bob un sy'n ddiddorol, sydd yn wir mae'n 9 00:00:29,340 --> 00:00:33,570 mewn gwirionedd yw, beth yw rhai o'r pwyntiau cadarnhaol o'r data syml 10 00:00:33,570 --> 00:00:34,560 strwythur hyd yn hyn? 11 00:00:34,560 --> 00:00:36,110 Beth yw ei dda? 12 00:00:36,110 --> 00:00:39,450 Cyn belled ag yr ydym wedi gweld? 13 00:00:39,450 --> 00:00:42,540 Beth ydych chi'n ei gael? 14 00:00:42,540 --> 00:00:44,028 Dim byd. 15 00:00:44,028 --> 00:00:45,020 >> MYFYRIWR: [Anghlywadwy]. 16 00:00:45,020 --> 00:00:45,395 >> SIARADWR 1: Beth sy'n bod? 17 00:00:45,395 --> 00:00:46,410 >> MYFYRIWR: [Anghlywadwy]. 18 00:00:46,410 --> 00:00:47,000 >> SIARADWR 1: faint sefydlog. 19 00:00:47,000 --> 00:00:51,260 Iawn, felly pam mae maint sefydlog da er bod? 20 00:00:51,260 --> 00:00:53,180 >> MYFYRIWR: [Anghlywadwy]. 21 00:00:53,180 --> 00:00:56,240 >> SIARADWR 1: OK, felly mae'n effeithlon yn yr ystyr eich bod yn gallu dyrannu 22 00:00:56,240 --> 00:01:00,070 swm penodol o le, a gobeithio, yn union gymaint 23 00:01:00,070 --> 00:01:01,180 gofod ag y dymunwch. 24 00:01:01,180 --> 00:01:02,720 Fel y gallai fod yn hollol yn fantais. 25 00:01:02,720 --> 00:01:06,530 >> Beth sydd i fyny ochr arall o fyrdd? 26 00:01:06,530 --> 00:01:07,610 Yeah? 27 00:01:07,610 --> 00:01:08,750 >> MYFYRIWR: [Anghlywadwy]. 28 00:01:08,750 --> 00:01:09,550 >> SIARADWR 1: Mae'r holl - mae'n ddrwg gennyf? 29 00:01:09,550 --> 00:01:11,270 >> MYFYRIWR: [Anghlywadwy]. 30 00:01:11,270 --> 00:01:13,620 >> SIARADWR 1: Pob y blychau er cof neu nesaf at ei gilydd. 31 00:01:13,620 --> 00:01:15,220 Ac mae hynny'n ddefnyddiol - pam? 32 00:01:15,220 --> 00:01:15,970 Mae hynny'n hollol wir. 33 00:01:15,970 --> 00:01:18,611 Ond sut y gallwn fanteisio ar y gwirionedd? 34 00:01:18,611 --> 00:01:21,500 >> MYFYRIWR: [Anghlywadwy]. 35 00:01:21,500 --> 00:01:24,490 >> SIARADWR 1: Yn union, gallwn gadw golwg ar lle mae popeth yn unig trwy wybod 36 00:01:24,490 --> 00:01:28,560 un cyfeiriad, sef gyfeiriad y beit cyntaf y darn o gof. 37 00:01:28,560 --> 00:01:30,420 Neu yn achos y llinyn, cyfeiriad y cyntaf 38 00:01:30,420 --> 00:01:31,460 torgoch yn y llinyn. 39 00:01:31,460 --> 00:01:33,330 Ac oddi yno, gallwn ddod o hyd i ddiwedd y llinyn. 40 00:01:33,330 --> 00:01:35,710 Gallwn ddod o hyd i'r ail elfen, y drydedd elfen, ac yn y blaen. 41 00:01:35,710 --> 00:01:38,740 >> Ac felly y ffordd ffansi o ddisgrifio bod nodwedd yw bod araeau yn rhoi i ni 42 00:01:38,740 --> 00:01:40,020 mynediad ar hap. 43 00:01:40,020 --> 00:01:44,330 Dim ond drwy ddefnyddio'r sgwâr braced nodiant a nifer, gallwch neidio i 44 00:01:44,330 --> 00:01:48,070 elfen benodol yn yr arae mewn amser yn gyson, O mawr 45 00:01:48,070 --> 00:01:49,810 o un, fel petai. 46 00:01:49,810 --> 00:01:51,080 >> Ond mae wedi bod rhai anfanteision. 47 00:01:51,080 --> 00:01:53,110 Beth amrywiaeth beidio â gwneud yn hawdd iawn? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Beth sydd ddim yn dda? 50 00:01:57,170 --> 00:01:58,810 >> MYFYRIWR: [Anghlywadwy]. 51 00:01:58,810 --> 00:01:59,860 >> SIARADWR 1: Beth sy'n bod? 52 00:01:59,860 --> 00:02:00,530 >> MYFYRIWR: [Anghlywadwy]. 53 00:02:00,530 --> 00:02:01,460 >> SIARADWR 1: Ehangu o ran maint. 54 00:02:01,460 --> 00:02:04,800 Felly anfanteision y rhesi yn union y gwrthwyneb i'r hyn y mae'r 55 00:02:04,800 --> 00:02:05,540 upsides yn cael eu. 56 00:02:05,540 --> 00:02:07,610 Felly, un o anfanteision yn ei fod yn faint penodol. 57 00:02:07,610 --> 00:02:09,400 Felly, ni allwch gynyddu. 58 00:02:09,400 --> 00:02:13,510 Gallwch ailddyrannu mwy darn o cof, ac yna symud yr hen elfennau 59 00:02:13,510 --> 00:02:14,460 yn y casgliad newydd. 60 00:02:14,460 --> 00:02:18,060 Ac yna ddim yr hen amrywiaeth, ar gyfer enghraifft, trwy ddefnyddio malloc neu debyg 61 00:02:18,060 --> 00:02:21,180 swyddogaeth o'r enw realloc, sy'n ailddyrannu cof. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, wrth fynd heibio, yn ceisio rhoi i chi cof sy'n nesaf at y casgliad 63 00:02:25,490 --> 00:02:26,610 sydd gennych yn barod. 64 00:02:26,610 --> 00:02:28,740 Ond gallai symud pethau amgylch yn gyfan gwbl. 65 00:02:28,740 --> 00:02:30,710 Ond yn fyr, mae hynny'n ddrud, dde? 66 00:02:30,710 --> 00:02:33,440 Oherwydd os oes gennych darn o cof am maint hwn, ond ydych wir eisiau un 67 00:02:33,440 --> 00:02:36,710 o'r maint hwn, ac rydych am i gadw yr elfennau gwreiddiol, mae gennych 68 00:02:36,710 --> 00:02:40,510 fras broses copïo amser llinol sydd angen i ddigwydd o 69 00:02:40,510 --> 00:02:41,900 hen amrywiaeth i newydd. 70 00:02:41,900 --> 00:02:44,630 Ac mae'r realiti yn gofyn i'r gweithredu system eto ac eto ac 71 00:02:44,630 --> 00:02:48,340 eto am y gall darnau mawr o gof yn dechrau i gostio i chi rhywfaint o amser yn ogystal. 72 00:02:48,340 --> 00:02:52,250 Felly mae'n yn fendith ac yn felltith mewn cuddio'r, y ffaith bod arrays hyn 73 00:02:52,250 --> 00:02:53,860 o faint penodol. 74 00:02:53,860 --> 00:02:56,790 Ond os ydym yn cyflwyno rhywbeth yn lle hynny fel hyn, yr ydym yn a elwir yn gysylltiedig 75 00:02:56,790 --> 00:03:00,580 rhestr, rydym yn cael ychydig o upsides a ychydig o anfanteision yma hefyd. 76 00:03:00,580 --> 00:03:05,780 >> Felly restr cysylltiedig yn unig yw ddata strwythur sy'n cynnwys structs C yn y 77 00:03:05,780 --> 00:03:09,850 achos, lle mae strwythur, galw i gof, yn unig cynhwysydd ar gyfer un neu fwy penodol 78 00:03:09,850 --> 00:03:11,100 mathau o newidynnau. 79 00:03:11,100 --> 00:03:16,110 Yn yr achos hwn, beth yn gwneud y mathau o ddata ymddangos i fod y tu mewn i'r strwythur y 80 00:03:16,110 --> 00:03:17,600 tro diwethaf i ni a elwir yn nod? 81 00:03:17,600 --> 00:03:19,380 Mae pob un o'r petryalau hyn yn nod. 82 00:03:19,380 --> 00:03:22,660 A phob un o'r petryalau llai tu mewn iddo yn fath data. 83 00:03:22,660 --> 00:03:25,300 Pa fathau wnaethom ni ddweud eu bod ar ddydd Llun? 84 00:03:25,300 --> 00:03:26,478 Yeah? 85 00:03:26,478 --> 00:03:27,870 >> MYFYRIWR: [Anghlywadwy]. 86 00:03:27,870 --> 00:03:30,721 >> SIARADWR 1: amrywiol a pwyntydd, neu yn fwy penodol, yn int, ar gyfer n, 87 00:03:30,721 --> 00:03:32,180 a pwyntydd ar y gwaelod. 88 00:03:32,180 --> 00:03:35,360 Mae'r ddau o'r rheiny yn digwydd i fod yn 32 darnau, yn leiaf ar gyfrifiadur fel hyn CS50 89 00:03:35,360 --> 00:03:37,980 Offer, ac felly eu bod yn tynnu yn gyfartal o ran maint. 90 00:03:37,980 --> 00:03:42,260 >> Felly, beth yn defnyddio'r pwyntydd er bod ar gyfer pob golwg? 91 00:03:42,260 --> 00:03:47,690 Pam ychwanegu saeth hwn yn awr pan fydd araeau oedd mor neis ac yn lân ac yn syml? 92 00:03:47,690 --> 00:03:50,460 Beth yw y pwyntydd wneud dros i ni ym mhob un o'r nodau hyn? 93 00:03:50,460 --> 00:03:52,160 >> MYFYRIWR: [Anghlywadwy]. 94 00:03:52,160 --> 00:03:52,465 >> SIARADWR 1: Yn union. 95 00:03:52,465 --> 00:03:54,120 Mae'n dweud wrthych lle yr un nesaf. 96 00:03:54,120 --> 00:03:57,350 Felly yr wyf yn fath o ddefnyddio'r gyfatebiaeth o defnyddio edau i ddatrys y 97 00:03:57,350 --> 00:03:59,180 edafu nodau hyn gyda'i gilydd. 98 00:03:59,180 --> 00:04:01,760 A dyna'n union yr hyn rydym yn ei wneud gyda awgrymiadau gan fod pob un o'r rhain 99 00:04:01,760 --> 00:04:06,360 darnau o gof efallai na all neu fod yn cydgyffwrdd, gefn wrth gefn wrth gefn 100 00:04:06,360 --> 00:04:09,500 tu mewn RAM, oherwydd bod gan bob tro y byddwch yn ffoniwch malloc dweud, yn rhoi digon i mi 101 00:04:09,500 --> 00:04:12,510 bytes am nod newydd, y gallai fod yma neu gallai fod yma. 102 00:04:12,510 --> 00:04:13,120 Efallai ei fod yma. 103 00:04:13,120 --> 00:04:13,730 Efallai ei fod yma. 104 00:04:13,730 --> 00:04:14,640 Dim ond nad ydych yn gwybod. 105 00:04:14,640 --> 00:04:17,880 >> Ond yn defnyddio arwyddion yn y cyfeiriadau nodau hynny, gallwch pwyth iddynt 106 00:04:17,880 --> 00:04:22,370 at ei gilydd mewn ffordd sy'n edrych ar eu golwg fel rhestr hyd yn oed os yw'r pethau hyn yn 107 00:04:22,370 --> 00:04:26,770 pob gwasgaru drwy gydol eich un neu eich dau neu eich bedwar gigabeit o RAM 108 00:04:26,770 --> 00:04:28,760 tu mewn i'ch cyfrifiadur eich hun. 109 00:04:28,760 --> 00:04:33,230 >> Felly mae'r anfantais, yna, wrth restr cysylltiedig yw beth? 110 00:04:33,230 --> 00:04:34,670 Beth yw pris rydym yn yn ôl pob golwg yn talu? 111 00:04:34,670 --> 00:04:36,010 >> MYFYRIWR: [Anghlywadwy]. 112 00:04:36,010 --> 00:04:36,920 >> SIARADWR 1: Mwy o le, dde? 113 00:04:36,920 --> 00:04:39,340 Rydym wedi, yn yr achos hwn, dyblu y swm o le oherwydd ein bod wedi mynd 114 00:04:39,340 --> 00:04:43,500 o 32 ddarnau ar gyfer pob nod, ar gyfer pob int, felly, yn awr 64 o ddarnau oherwydd bod yn rhaid i 115 00:04:43,500 --> 00:04:45,050 cadw o amgylch pwyntydd hefyd. 116 00:04:45,050 --> 00:04:48,860 Byddwch yn cael mwy effeithlon os yw eich strwythur yn fwy na hyn peth syml. 117 00:04:48,860 --> 00:04:52,020 Os ydych chi mewn gwirionedd yn cael fyfyriwr y tu mewn un ohonynt yn ychydig o linynnau ar gyfer 118 00:04:52,020 --> 00:04:55,430 enw a thy, efallai rhif adnabod, efallai rhai meysydd eraill yn gyfan gwbl. 119 00:04:55,430 --> 00:04:59,000 >> Felly, os oes gennych strwythur ddigon mawr, yna efallai cost y pwyntydd yn 120 00:04:59,000 --> 00:05:00,010 Nid yw mor bwysig â hynny. 121 00:05:00,010 --> 00:05:03,570 Mae hwn yn dipyn o achos cornel yn y rydym yn storio cyntefig mor syml 122 00:05:03,570 --> 00:05:04,760 tu mewn i'r rhestr cysylltiedig. 123 00:05:04,760 --> 00:05:05,790 Ond y pwynt yw yr un fath. 124 00:05:05,790 --> 00:05:08,230 Rydych yn sicr yn gwario mwy cof, ond eich bod yn cael 125 00:05:08,230 --> 00:05:08,990 hyblygrwydd. 126 00:05:08,990 --> 00:05:12,280 Oherwydd erbyn hyn os ydw i eisiau ychwanegu elfen ar ddechrau'r y rhestr hon, 127 00:05:12,280 --> 00:05:14,340 Rhaid i mi ddyrannu nod newydd. 128 00:05:14,340 --> 00:05:17,180 Ac mae'n rhaid i mi jyst diweddaru rhai saethau rywsut at jyst yn symud 129 00:05:17,180 --> 00:05:17,980 rhai awgrymiadau o gwmpas. 130 00:05:17,980 --> 00:05:20,580 >> Os ydw i eisiau rhoi rhywbeth i mewn i'r nghanol y rhestr, nid oes rhaid i mi 131 00:05:20,580 --> 00:05:24,410 gwthio pawb o'r neilltu fel y gwnaethom yn wythnos diwethaf gyda'n gwirfoddolwyr sy'n 132 00:05:24,410 --> 00:05:25,700 yn cynrychioli amrywiaeth. 133 00:05:25,700 --> 00:05:29,470 Gall Fi jyst dyrannu nod newydd ac yna dim ond dangos y saethau mewn 134 00:05:29,470 --> 00:05:32,290 cyfarwyddiadau wahanol oherwydd nad yw'n rhaid i chi aros yn wirioneddol 135 00:05:32,290 --> 00:05:35,670 cof linell wir fy mod wedi tynnu yma ar y sgrin. 136 00:05:35,670 --> 00:05:38,400 >> Ac yna yn olaf, os ydych am i fewnosod rhywbeth ar ddiwedd y rhestr, mae'n 137 00:05:38,400 --> 00:05:39,210 hyd yn oed yn haws. 138 00:05:39,210 --> 00:05:43,320 Mae hyn yn fath o nodiant mympwyol, ond mae pwyntydd 34, yn cymryd dyfalu. 139 00:05:43,320 --> 00:05:46,710 Beth yw gwerth ei pwyntydd y rhan fwyaf o math tynnu tebygol fel hen 140 00:05:46,710 --> 00:05:47,700 antena ysgol yno? 141 00:05:47,700 --> 00:05:48,920 >> MYFYRIWR: [Anghlywadwy]. 142 00:05:48,920 --> 00:05:49,900 >> SIARADWR 1: Mae'n debyg null. 143 00:05:49,900 --> 00:05:52,710 Ac yn wir dyna un awdur cynrychiolaeth o null. 144 00:05:52,710 --> 00:05:56,310 Ac mae'n null oherwydd eich bod yn hollol angen i ni wybod ble ddiwedd cysylltiedig 145 00:05:56,310 --> 00:06:00,050 rhestr yw, rhag eich bod yn cadw canlynol ac dilyn ac yn dilyn y saethau hyn 146 00:06:00,050 --> 00:06:01,170 i ryw werth garbage. 147 00:06:01,170 --> 00:06:06,230 Felly bydd null arwydd nad oes unrhyw mwy o nodau i'r dde o'r rhif 34, 148 00:06:06,230 --> 00:06:07,200 yn yr achos hwn. 149 00:06:07,200 --> 00:06:10,270 >> Felly, rydym yn cynnig ein bod yn gallu gweithredu nod hwn mewn cod. 150 00:06:10,270 --> 00:06:12,130 Ac rydym wedi gweld y math hwn ar gystrawen blaen. 151 00:06:12,130 --> 00:06:15,090 Typedef yn unig yn diffinio math newydd ar gyfer ni, yn rhoi gyfystyr ni fel 152 00:06:15,090 --> 00:06:17,100 llinyn oedd torgoch *. 153 00:06:17,100 --> 00:06:21,030 Yn yr achos hwn, mae'n mynd i roi i ni nodiant llaw-fer fel bod strwythur nod 154 00:06:21,030 --> 00:06:24,010 Gellir hytrach dim ond ei ysgrifennu fel nod, sydd yn llawer glanach. 155 00:06:24,010 --> 00:06:25,360 Mae'n llawer llai verbose. 156 00:06:25,360 --> 00:06:30,080 >> Y tu mewn o nod yn ôl pob golwg yn int n galw, ac yna strwythur nod * 157 00:06:30,080 --> 00:06:34,670 sy'n golygu yn union yr hyn yr ydym am i'r saethau i olygu, pwyntydd i un arall 158 00:06:34,670 --> 00:06:36,940 nod y math data union un fath. 159 00:06:36,940 --> 00:06:40,300 Ac yr wyf yn cynnig y gallem gweithredu swyddogaeth chwilio fel hyn, sydd ar hyn o 160 00:06:40,300 --> 00:06:41,890 Efallai yr olwg gyntaf yn ymddangos ychydig o gymhleth. 161 00:06:41,890 --> 00:06:43,330 Ond gadewch i ni ei weld yn y cyd-destun. 162 00:06:43,330 --> 00:06:45,480 >> Gadewch i mi fynd draw at y peiriant yma. 163 00:06:45,480 --> 00:06:48,460 Gadewch i mi agor ffeil o'r enw rhestr sero dot h. 164 00:06:48,460 --> 00:06:53,950 Ac mai dim ond yn cynnwys y diffiniad yr ydym jyst yn gweld funud yn ôl am y data hwn 165 00:06:53,950 --> 00:06:55,390 math a elwir yn nod. 166 00:06:55,390 --> 00:06:57,350 Felly, rydym wedi rhoi bod i mewn i ffeil h dot. 167 00:06:57,350 --> 00:07:01,430 >> Ac wrth fynd heibio, er bod hyn rhaglen eich bod chi ar fin ei weld yw 168 00:07:01,430 --> 00:07:05,410 nid bob un sy'n gymhleth, mae'n wir confensiwn wrth ysgrifennu rhaglen i 169 00:07:05,410 --> 00:07:10,270 rhoi pethau fel mathau o ddata, i dynnu cysonion weithiau, y tu mewn eich 170 00:07:10,270 --> 00:07:13,210 ffeil flaen ac nid o reidrwydd yn eich ffeil C, yn sicr pan fydd eich 171 00:07:13,210 --> 00:07:17,370 rhaglenni fynd yn fwy ac yn fwy, fel y eich bod yn gwybod ble i chwilio ar gyfer 172 00:07:17,370 --> 00:07:20,840 dogfennau mewn rhai achosion, neu ar gyfer nwyddau sylfaenol fel hyn, mae'r 173 00:07:20,840 --> 00:07:22,360 diffiniad o ryw fath. 174 00:07:22,360 --> 00:07:25,680 >> Os wyf yn awr yn agor rhestr sero dot c, sylwi ar ychydig o bethau. 175 00:07:25,680 --> 00:07:29,090 Mae'n cynnwys ychydig o ffeiliau pennawd, y rhan fwyaf o yr ydym wedi ei weld o'r blaen. 176 00:07:29,090 --> 00:07:31,980 Mae'n cynnwys ei ffeil flaen ei hun. 177 00:07:31,980 --> 00:07:35,200 >> Ac wrth fynd heibio, pam mae hynny'n ddwbl dyfyniadau yma, yn hytrach na'r ongl 178 00:07:35,200 --> 00:07:38,340 cromfachau ar y llinell sy'n Rwyf wedi tynnu sylw yno? 179 00:07:38,340 --> 00:07:39,180 >> MYFYRIWR: [Anghlywadwy]. 180 00:07:39,180 --> 00:07:40,460 >> SIARADWR 1: Yeah felly mae'n ffeil lleol. 181 00:07:40,460 --> 00:07:44,300 Felly, os yw'n ffeil lleol eich hunain yma on line 15, er enghraifft, byddwch yn defnyddio 182 00:07:44,300 --> 00:07:46,570 y dyfyniadau dwbl yn lle hynny y cromfachau onglog. 183 00:07:46,570 --> 00:07:48,270 >> Nawr mae hyn yn fath o ddiddorol. 184 00:07:48,270 --> 00:07:51,830 Hysbysu fy mod wedi datgan byd-eang amrywiol yn y rhaglen hon ar-lein 18 185 00:07:51,830 --> 00:07:55,910 a elwir yn gyntaf, y syniad yw hyn yn mynd i fod yn pwyntydd i'r gyntaf 186 00:07:55,910 --> 00:07:59,190 nod yn fy rhestr gysylltiedig, ac rwyf wedi ymgychwyn iddo null, gan fy mod i wedi 187 00:07:59,190 --> 00:08:02,310 heb ei dyrannu unrhyw ostyngiad gwirioneddol nodau eto. 188 00:08:02,310 --> 00:08:07,570 >> Felly, mae hyn yn cynrychioli, ar ffurf lluniau, yr hyn yr ydym Gwelodd funud yn ôl yn y llun fel 189 00:08:07,570 --> 00:08:10,090 y pwyntydd ar y graddau y gadael ochr llaw. 190 00:08:10,090 --> 00:08:12,260 Felly, ar hyn o bryd, y pwyntydd Nid oes gan saeth. 191 00:08:12,260 --> 00:08:14,590 Mae'n lle hynny yn unig null. 192 00:08:14,590 --> 00:08:17,880 Ond mae'n cynrychioli beth fydd y chyfeiriad y gwir cyntaf 193 00:08:17,880 --> 00:08:19,480 nod yn y rhestr hon. 194 00:08:19,480 --> 00:08:22,120 Felly, yr wyf wedi rhoi ar waith ei fod yn fyd-eang oherwydd, fel y gwelwch, hyn i gyd 195 00:08:22,120 --> 00:08:25,310 mewn bywyd rhaglen yn ei wneud yw gweithredu rhestr gysylltu i mi. 196 00:08:25,310 --> 00:08:27,050 >> Nawr mae gen i ychydig o prototeipiau yma. 197 00:08:27,050 --> 00:08:31,190 Penderfynais i weithredu nodweddion fel dileu, mewnosod, chwilio, a 198 00:08:31,190 --> 00:08:31,740 llwybro - 199 00:08:31,740 --> 00:08:35,210 y daith olaf dim ond bod ar draws y rhestr, argraffu ei elfennau. 200 00:08:35,210 --> 00:08:36,750 Ac yn awr dyma fy mhrif arferol. 201 00:08:36,750 --> 00:08:39,890 Ac ni fyddwn yn treulio gormod o amser ar hyn gan fod hyn yn fath o, gobeithio 202 00:08:39,890 --> 00:08:41,780 hen het erbyn hyn. 203 00:08:41,780 --> 00:08:45,370 >> Rydw i'n mynd i wneud y canlynol, tra bod y defnyddiwr yn cydweithio. 204 00:08:45,370 --> 00:08:47,300 Felly un, yr wyf i'n mynd i argraffu ar y fwydlen. 205 00:08:47,300 --> 00:08:49,420 Ac yr wyf wedi fformatio fel lân ag y gallwn. 206 00:08:49,420 --> 00:08:52,240 Os mathau y defnyddiwr mewn un, mae hynny'n golygu maent am ei ddileu rhywbeth. 207 00:08:52,240 --> 00:08:54,560 Os mathau y defnyddiwr mewn dau, mae hynny'n golygu maent am i fewnosod rhywbeth. 208 00:08:54,560 --> 00:08:55,930 Ac yn y blaen. 209 00:08:55,930 --> 00:08:58,270 Rydw i'n mynd i wedyn yn ysgogi yna am orchymyn. 210 00:08:58,270 --> 00:08:59,300 Ac yna dwi'n mynd i ddefnyddio GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Felly, mae hwn yn menuing syml iawn rhyngwynebu lle os oes gen ti i deipio 212 00:09:02,790 --> 00:09:05,270 rhif mapio i un o orchmynion hynny. 213 00:09:05,270 --> 00:09:08,730 Ac yn awr yr wyf wedi switsh glân 'n glws datganiad sy'n mynd i newid ar 214 00:09:08,730 --> 00:09:10,090 beth bynnag y defnyddiwr deipio i mewn 215 00:09:10,090 --> 00:09:12,180 Ac os ydynt yn teipio un, byddaf yn ffoniwch dileu a thorri. 216 00:09:12,180 --> 00:09:14,380 Os ydynt yn teipio ddau, byddaf ffoniwch mewnosod a torri. 217 00:09:14,380 --> 00:09:16,490 >> Ac yn awr rhybudd rwyf wedi rhoi pob y rhain ar yr un llinell. 218 00:09:16,490 --> 00:09:18,360 Penderfyniad arddull yn unig yw hwn. 219 00:09:18,360 --> 00:09:20,210 Fel arfer, rydym wedi gweld rhywbeth fel hyn. 220 00:09:20,210 --> 00:09:23,260 Ond Fi jyst benderfynu, a dweud y gwir, fy rhaglen edrych yn fwy darllenadwy oherwydd 221 00:09:23,260 --> 00:09:25,980 dim ond pedwar achos i dim ond rhestru fel hyn. 222 00:09:25,980 --> 00:09:28,360 Defnydd gwbl gyfreithlon o arddull. 223 00:09:28,360 --> 00:09:31,480 Ac yr wyf i'n mynd i wneud hyn cyhyd ag y Nid yw'r defnyddiwr wedi teipio ddim, yr wyf yn 224 00:09:31,480 --> 00:09:33,910 penderfynu y byddant yn golygu eu bod eisiau rhoi'r gorau iddi. 225 00:09:33,910 --> 00:09:36,630 >> Felly sylwi ar beth dw i'n mynd i'w wneud yma. 226 00:09:36,630 --> 00:09:38,650 Rydw i'n mynd i ryddhau y rhestr yn ôl pob golwg. 227 00:09:38,650 --> 00:09:40,230 Ond mwy am hynny mewn dim ond hyn o bryd. 228 00:09:40,230 --> 00:09:41,640 Gadewch i ni yn gyntaf yn rhedeg y rhaglen hon. 229 00:09:41,640 --> 00:09:45,250 Felly, gadewch i mi wneud mwy o derfynell ffenestr, dot rhestr slaes 0. 230 00:09:45,250 --> 00:09:49,510 Rydw i'n mynd i fynd yn ei flaen ac yn mewnosod gan teipio dau, mae nifer tebyg i 50, ac yn awr 231 00:09:49,510 --> 00:09:51,590 byddwch yn gweld y rhestr yn awr yn 50. 232 00:09:51,590 --> 00:09:53,380 Ac mae fy testun yn unig sgrolio i fyny ychydig. 233 00:09:53,380 --> 00:09:55,940 Felly, erbyn hyn yn sylwi ar y rhestr hon yn cynnwys y rhif 50. 234 00:09:55,940 --> 00:09:58,220 >> Gadewch i ni wneud mewnosoder arall drwy gymryd dau. 235 00:09:58,220 --> 00:10:01,630 Gadewch i deipio yn y nifer fel un. 236 00:10:01,630 --> 00:10:03,940 Rhestr bellach yn un, ac yna 50. 237 00:10:03,940 --> 00:10:06,020 Felly cynrychiolaeth testunol hyn yn unig y rhestr. 238 00:10:06,020 --> 00:10:10,550 A gadewch i ni ychwanegu un yn fwy rhif, er enghraifft y rhif 42, sy'n gobeithio 239 00:10:10,550 --> 00:10:14,620 yn mynd i roi diwedd ar i fyny yn y canol, gan fod rhaglen hon yn fath arbennig, 240 00:10:14,620 --> 00:10:16,320 elfennau y mae'n mewnosod nhw. 241 00:10:16,320 --> 00:10:17,220 Felly mae gennym. 242 00:10:17,220 --> 00:10:20,730 Rhaglen syml super a allai gwbl wedi defnyddio amrywiaeth, ond yr wyf yn 243 00:10:20,730 --> 00:10:23,280 digwydd bod yn defnyddio rhestr gysylltiedig yn union fel y gallaf ddeinamig 244 00:10:23,280 --> 00:10:24,610 tyfu ac yn crebachu ei. 245 00:10:24,610 --> 00:10:28,470 >> Felly, gadewch i ni edrych ar gyfer chwilio, os wyf rhedeg gorchymyn tri, yr wyf am i chwilio 246 00:10:28,470 --> 00:10:31,040 am, dyweder, y rhif 43. 247 00:10:31,040 --> 00:10:34,190 A dim byd Daethpwyd o hyd yn ôl pob golwg, oherwydd fy mod yn cael unrhyw ymateb yn ôl. 248 00:10:34,190 --> 00:10:35,010 Felly, gadewch i ni wneud hyn eto. 249 00:10:35,010 --> 00:10:35,690 Chwilio. 250 00:10:35,690 --> 00:10:39,520 Gadewch i ni chwilio am 50, neu yn hytrach chwilio am 42, sydd â 'n glws 251 00:10:39,520 --> 00:10:40,850 ychydig o ystyr cynnil. 252 00:10:40,850 --> 00:10:42,610 Ac yr wyf yn dod o hyd i'r ystyr bywyd yno. 253 00:10:42,610 --> 00:10:44,990 Rhif 42, os nad ydych yn gwybod y cyfeiriad, Google. 254 00:10:44,990 --> 00:10:45,350 Mae pob hawl. 255 00:10:45,350 --> 00:10:47,130 Felly, beth mae hyn rhaglen wneud i mi? 256 00:10:47,130 --> 00:10:50,660 'I' jyst fy ngalluogi i fewnosod a thrwy hynny bell ac yn chwilio am elfennau. 257 00:10:50,660 --> 00:10:53,650 >> Gadewch i ni yn gyflym ymlaen, yna, er mwyn swyddogaeth honno rydym yn bwrw golwg ar 258 00:10:53,650 --> 00:10:55,360 ar ddydd Llun fel ymlid. 259 00:10:55,360 --> 00:10:59,620 Felly swyddogaeth hon, yr wyf yn gwneud cais, chwilio am elfen yn y rhestr gan gyntaf 260 00:10:59,620 --> 00:11:03,830 un, gan annog y defnyddiwr ac yna galw GetInt i gael int gwirioneddol 261 00:11:03,830 --> 00:11:05,060 eich bod am chwilio am. 262 00:11:05,060 --> 00:11:06,460 >> Yna sylwi ar hyn. 263 00:11:06,460 --> 00:11:10,690 Rydw i'n mynd i greu newidyn dros dro yn unol 188 enw pwyntydd - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 gallai fod wedi ei alw unrhyw beth. 266 00:11:12,440 --> 00:11:16,140 Ac mae'n pwyntydd i nod oherwydd dywedais nod * yno. 267 00:11:16,140 --> 00:11:19,900 A dwi'n ymgychwyn i fod yn hafal i yn gyntaf er mwyn i mi gael fy effeithiol 268 00:11:19,900 --> 00:11:22,860 bys, fel petai, ar yr union Elfen gyntaf y rhestr. 269 00:11:22,860 --> 00:11:27,460 Felly, os bydd fy llaw dde yma yw PTR rwy'n pwyntio at yr un peth yn gyntaf 270 00:11:27,460 --> 00:11:28,670 yn pwyntio at. 271 00:11:28,670 --> 00:11:31,430 >> Felly, bellach yn ôl mewn cod, beth sy'n digwydd nesaf - 272 00:11:31,430 --> 00:11:35,070 mae hwn yn batrwm cyffredin wrth ailadrodd dros strwythur fel 273 00:11:35,070 --> 00:11:35,970 restr cysylltiedig. 274 00:11:35,970 --> 00:11:40,410 Rydw i'n mynd i wneud y canlynol wrth Nid pwyntydd yn hafal i null Felly, er 275 00:11:40,410 --> 00:11:47,530 Nid yw fy bys yn pwyntio ar ryw null gwerth, os pwyntydd saeth n hafal n. 276 00:11:47,530 --> 00:11:52,290 Byddwn yn sylwi gyntaf y n yw yr hyn y mae'r defnyddiwr deipio yn y GetInts galw yma. 277 00:11:52,290 --> 00:11:54,280 >> Ac pwyntydd saeth n golygu beth? 278 00:11:54,280 --> 00:11:59,020 Wel, os ydym yn mynd yn ôl at y llun yma, os oes gen i bys bwyntio at 279 00:11:59,020 --> 00:12:02,960 y nod cyntaf yn cynnwys naw, y saeth yn ei hanfod yn golygu mynd i'r 280 00:12:02,960 --> 00:12:08,860 nod a chrafangia 'r gwerth yn y lleoliad n, yn yr achos hwn, roedd y maes data a elwir yn n. 281 00:12:08,860 --> 00:12:14,120 >> Fel o'r neilltu - ac yr ydym yn gweld hyn cwpl o wythnosau yn ôl pan ofynnir i rywun - 282 00:12:14,120 --> 00:12:18,840 chystrawen hyn yn newydd, ond nid yw'n yn rhoi pwerau i ni ein bod yn 283 00:12:18,840 --> 00:12:20,040 Nid oedd wedi gwneud hynny'n barod. 284 00:12:20,040 --> 00:12:25,325 Beth oedd hyn yn ymadrodd sy'n cyfateb i ddefnyddio dot nodiant a seren cwpl 285 00:12:25,325 --> 00:12:29,490 o wythnosau yn ôl pan fyddwn yn plicio yn ôl haen hwn ychydig cyn pryd? 286 00:12:29,490 --> 00:12:31,780 >> MYFYRIWR: [Anghlywadwy]. 287 00:12:31,780 --> 00:12:38,880 >> SIARADWR 1: Yn union, roedd yn seren, ac yna roedd seren dot n, gyda 288 00:12:38,880 --> 00:12:41,930 cromfachau yma, sy'n edrych, dweud y gwir, yr wyf yn credu bod llawer 289 00:12:41,930 --> 00:12:43,320 mwy cryptig i ddarllen. 290 00:12:43,320 --> 00:12:46,270 Ond seren pwyntydd, fel bob amser, modd mynd yno. 291 00:12:46,270 --> 00:12:49,090 Ac unwaith y byddwch chi yno, pa ddata maes yn ydych chi am gael mynediad? 292 00:12:49,090 --> 00:12:52,730 Dda yr ydych yn defnyddio'r nodiant dot i gael mynediad at maes data structs, ac yr wyf yn 293 00:12:52,730 --> 00:12:54,140 benodol eisiau n. 294 00:12:54,140 --> 00:12:56,240 >> Dweud y gwir, byddwn yn dadlau hyn yn unig yn fwy anodd i'w darllen. 295 00:12:56,240 --> 00:12:58,080 Mae'n anoddach i gofio lle yn y cromfachau mynd, y 296 00:12:58,080 --> 00:12:59,030 seren a hynny i gyd. 297 00:12:59,030 --> 00:13:02,150 Felly, yn y byd mabwysiadu rhai cystrawennol siwgr, fel petai. 298 00:13:02,150 --> 00:13:04,740 Dim ond ffordd sexy o ddweud, mae hyn yn gyfwerth, a 299 00:13:04,740 --> 00:13:05,970 efallai yn fwy 'n athrylithgar. 300 00:13:05,970 --> 00:13:09,600 Os pwyntydd yn wir yn pwyntydd, y arrow nodiant yn golygu mynd yno ac yn dod o hyd i 301 00:13:09,600 --> 00:13:11,890 maes yn yr achos hwn a elwir yn n. 302 00:13:11,890 --> 00:13:13,660 >> Felly os wyf yn ei chael yn, sylwi ar yr hyn yr wyf yn ei wneud. 303 00:13:13,660 --> 00:13:17,430 Yr wyf yn syml argraffu, yr wyf yn dod o hyd cant i, llenwi yn y gwerth ar gyfer y int. 304 00:13:17,430 --> 00:13:20,730 Galwaf cysgu am un eiliad yn unig i fath o bethau oedi ar y sgrin i 305 00:13:20,730 --> 00:13:22,900 rhoi'r defnyddiwr yn ail i amsugno beth yn union ddigwyddodd. 306 00:13:22,900 --> 00:13:24,290 Ac yna mi dorri. 307 00:13:24,290 --> 00:13:26,330 Fel arall, beth ddylwn i ei wneud? 308 00:13:26,330 --> 00:13:30,960 Byddaf yn diweddaru'r pwyntydd i gyfleoedd cyfartal arrow pwyntydd nesaf. 309 00:13:30,960 --> 00:13:35,840 >> Felly, dim ond i fod yn glir, mae hyn yn golygu mynd yno, gan ddefnyddio fy hen nodiant-ysgol. 310 00:13:35,840 --> 00:13:39,580 Felly mae hyn yn unig yn golygu i fynd i ba bynnag eich bod yn tynnu sylw at, sydd yn yr union 311 00:13:39,580 --> 00:13:43,660 achos cyntaf yw i ddim yn pwyntio at y strwythur gyda naw ynddo. 312 00:13:43,660 --> 00:13:44,510 Felly, yr wyf wedi mynd yno. 313 00:13:44,510 --> 00:13:47,880 Ac yna y nodiant dot yn golygu, cael y gwerth arno nesaf. 314 00:13:47,880 --> 00:13:50,470 >> Ond mae'r werth, hyd yn oed er ei fod yn tynnu fel gul, yn unig yw rhif. 315 00:13:50,470 --> 00:13:51,720 Mae'n cyfeiriad rhifol. 316 00:13:51,720 --> 00:13:55,670 Felly, un llinell o god hwn, p'un a ysgrifenedig fel hyn, y mwyaf cryptig 317 00:13:55,670 --> 00:14:00,190 ffordd, neu fel hyn, mae ychydig yn fwy ffordd sythweledol, yn unig yn golygu symud fy llaw 318 00:14:00,190 --> 00:14:03,460 oddi wrth y nod cyntaf i'r un nesaf, ac yna yr un nesaf, ac yna 319 00:14:03,460 --> 00:14:05,320 un nesaf, ac yn y blaen. 320 00:14:05,320 --> 00:14:09,920 >> Felly, ni fyddwn yn trigo ar y llaw arall gweithrediadau o mewnosod a dileu 321 00:14:09,920 --> 00:14:14,030 a llwybro, y ddau gyntaf sydd yn ymwneud yn deg. 322 00:14:14,030 --> 00:14:17,010 Ac yr wyf yn meddwl ei fod yn eithaf hawdd i gael colli wrth wneud hynny ar lafar. 323 00:14:17,010 --> 00:14:19,890 Ond beth y gallwn ei wneud yma yw ceisio penderfynu sut 324 00:14:19,890 --> 00:14:21,640 orau o wneud hyn ar eu golwg. 325 00:14:21,640 --> 00:14:24,800 Oherwydd byddwn yn cynnig, os ydym yn eisiau i fewnosod elfennau i mewn i hyn 326 00:14:24,800 --> 00:14:26,680 rhestr bresennol, sy'n Mae pum elfen - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, a 33 - 328 00:14:29,530 --> 00:14:33,300 os wyf yn mynd i roi hyn ar waith yn cod, angen i mi ystyried sut i fynd 329 00:14:33,300 --> 00:14:34,160 am wneud hyn. 330 00:14:34,160 --> 00:14:37,720 >> A byddwn yn cynnig cymryd camau babi lle, yn yr achos hwn yr wyf yn golygu, beth yw'r 331 00:14:37,720 --> 00:14:41,090 y senarios posibl ein bod yn allai ddod ar eu traws yn gyffredinol? 332 00:14:41,090 --> 00:14:44,120 Wrth weithredu mewnosoder ar gyfer cysylltiedig rhestr, mae hyn yn unig fydd yn digwydd i fod yn 333 00:14:44,120 --> 00:14:46,090 enghraifft benodol o faint bump. 334 00:14:46,090 --> 00:14:50,420 Wel, os ydych am osod nifer, yn hoffi dweud y rhif un, ac 335 00:14:50,420 --> 00:14:53,380 cadw trefn didoli, lle amlwg â nifer angen un 336 00:14:53,380 --> 00:14:55,686 mynd yn yr enghraifft benodol? 337 00:14:55,686 --> 00:14:56,840 Fel ar y dechrau. 338 00:14:56,840 --> 00:15:00,030 >> Ond yr hyn sy'n ddiddorol yw bod yna os ydych am i fewnosod un i mewn i hyn 339 00:15:00,030 --> 00:15:04,100 rhestr, mae angen yr hyn y pwyntydd arbennig i gael ei diweddaru yn ôl pob golwg? 340 00:15:04,100 --> 00:15:04,610 Yn gyntaf. 341 00:15:04,610 --> 00:15:07,830 Felly, byddwn yn dadlau, mae hyn yn yr achos cyntaf y byddem efallai am ystyried, a 342 00:15:07,830 --> 00:15:11,140 senario sy'n cynnwys mewnosod ar ddechrau'r rhestr. 343 00:15:11,140 --> 00:15:15,400 >> Gadewch i ni tyn i ffwrdd efallai mae mor hawdd neu hyd yn oed achos yn haws, yn gymharol siarad. 344 00:15:15,400 --> 00:15:18,110 Gadewch i ni dybio Yr wyf am i mewnosoder y rhif 35 er mwyn didoli. 345 00:15:18,110 --> 00:15:20,600 Mae'n amlwg yn perthyn dros yno. 346 00:15:20,600 --> 00:15:25,320 Felly, yr hyn y pwyntydd yn amlwg yn mynd i rhaid ei ddiweddaru yn y sefyllfa honno? 347 00:15:25,320 --> 00:15:30,060 Pwyntydd 34 yn dod yn Nid null ond y cyfeiriad y strwythur 348 00:15:30,060 --> 00:15:31,800 yn cynnwys y rhif 35. 349 00:15:31,800 --> 00:15:32,750 Felly dyna achos dau. 350 00:15:32,750 --> 00:15:36,190 Hynny eisoes, rwy'n fath o quantizing faint o waith rhaid i mi ei wneud yma. 351 00:15:36,190 --> 00:15:39,880 >> Ac yn olaf, yr achos canol amlwg yw yn wir, yn y canol, os wyf am 352 00:15:39,880 --> 00:15:45,870 mewnosod rhywbeth fel dweud 23, sy'n mynd rhwng y 23 a'r 26, ond 353 00:15:45,870 --> 00:15:48,680 nawr pethau'n mynd ychydig yn fwy cymryd rhan oherwydd yr hyn 354 00:15:48,680 --> 00:15:52,800 angen newid awgrymiadau? 355 00:15:52,800 --> 00:15:56,680 Felly 22 yn amlwg angen ei newid oherwydd ni all bwyntio at 26 anymore. 356 00:15:56,680 --> 00:16:00,320 Mae angen i dynnu sylw at y nod newydd sy'n Bydd rhaid i mi ddyrannu drwy ffonio 357 00:16:00,320 --> 00:16:01,770 malloc neu ryw cyfwerth. 358 00:16:01,770 --> 00:16:05,990 >> Ond yna yr wyf hefyd angen i nod newydd, 23 yn yr achos hwn, i gael ei pwyntydd 359 00:16:05,990 --> 00:16:07,870 pwyntio at bwy? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 Ac mae mynd i fod yn trefn y gweithrediadau yma. 362 00:16:10,380 --> 00:16:13,410 Oherwydd os wyf yn gwneud hyn yn ffôl, ac yr wyf yn er enghraifft, cychwyn ar ddechrau 363 00:16:13,410 --> 00:16:16,040 y rhestr, a fy nod yw gosod 23. 364 00:16:16,040 --> 00:16:18,610 Ac yr wyf yn gwirio, a yw'n perthyn yma, ger naw? 365 00:16:18,610 --> 00:16:18,950 Rhif 366 00:16:18,950 --> 00:16:20,670 A yw'n perthyn yma, y ​​drws nesaf i 17? 367 00:16:20,670 --> 00:16:20,940 Rhif 368 00:16:20,940 --> 00:16:22,530 A yw'n perthyn yma nesaf i 22? 369 00:16:22,530 --> 00:16:23,300 Ydw. 370 00:16:23,300 --> 00:16:26,400 >> Nawr, os ydw i'n ffôl yma, ac nid meddwl hyn drwy, efallai y byddaf 371 00:16:26,400 --> 00:16:28,320 ddyrannu fy nod newydd ar gyfer 23. 372 00:16:28,320 --> 00:16:32,080 Efallai fy mod yn diweddaru'r pwyntydd o y nod a elwir yn 22, pwyntio 373 00:16:32,080 --> 00:16:33,080 hynny ar y nod newydd. 374 00:16:33,080 --> 00:16:36,140 Ac yna beth sy'n rhaid i mi ei ddiweddaru pwyntydd y nod newydd i fod? 375 00:16:36,140 --> 00:16:38,120 >> MYFYRIWR: [Anghlywadwy]. 376 00:16:38,120 --> 00:16:38,385 >> SIARADWR 1: Yn union. 377 00:16:38,385 --> 00:16:39,710 Pwyntio at 26. 378 00:16:39,710 --> 00:16:45,590 Ond dammit os nad oeddwn yn diweddaru eisoes Pwyntydd 22 i bwyntio at y boi, a 379 00:16:45,590 --> 00:16:48,260 nawr mae gen i blant amddifad, y gweddill y rhestr, fel petai. 380 00:16:48,260 --> 00:16:52,140 Felly, trefn y gweithrediadau yma yn mynd i fod yn bwysig. 381 00:16:52,140 --> 00:16:55,100 >> I wneud hyn y gallwn ddwyn, dyweder, chwe gwirfoddolwr. 382 00:16:55,100 --> 00:16:57,650 A gadewch i ni weld os na allwn wneud hyn weledol yn hytrach na cod-ddoeth. 383 00:16:57,650 --> 00:16:59,330 Ac mae gennym rai straen hyfryd peli i chi heddiw. 384 00:16:59,330 --> 00:17:02,510 OK, beth am un, dau, yn y yn ôl - ar y diwedd. 385 00:17:02,510 --> 00:17:04,530 tri, pedwar, y ddau ohonoch guys ar y diwedd. 386 00:17:04,530 --> 00:17:05,579 Ac pump, chwech. 387 00:17:05,579 --> 00:17:05,839 Cadarn. 388 00:17:05,839 --> 00:17:06,450 Pump a chwech. 389 00:17:06,450 --> 00:17:08,390 Mae pob hawl a byddwn yn dod i chi guys tro nesaf. 390 00:17:08,390 --> 00:17:09,640 Mae pob hawl, yn dod ar i fyny. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Mae pob hawl, gan eich bod hyd yma yn gyntaf, yr hoffech i fod yn un lletchwith 393 00:17:14,819 --> 00:17:16,119 yn Google Gwydr yma? 394 00:17:16,119 --> 00:17:19,075 Mae pob hawl, felly, OK, Gwydr, recordio fideo. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, rydych yn dda i fynd. 397 00:17:24,589 --> 00:17:27,950 >> Mae pob hawl, felly os gallwch chi guys ddod draw yma, yr wyf wedi paratoi ymlaen llaw 398 00:17:27,950 --> 00:17:30,110 rhai rhifau. 399 00:17:30,110 --> 00:17:31,240 Mae pob hawl, dewch draw yma. 400 00:17:31,240 --> 00:17:33,440 A pham nad ydych chi'n mynd ychydig ymhellach y ffordd honno. 401 00:17:33,440 --> 00:17:35,520 A gadewch i ni weld, beth yw eich enw, gyda'r Glass Google? 402 00:17:35,520 --> 00:17:35,910 >> MYFYRWYR: Ben. 403 00:17:35,910 --> 00:17:36,230 >> SIARADWR 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, byddwch yn gyntaf, yn llythrennol. 405 00:17:38,380 --> 00:17:40,580 Felly, rydym yn mynd i anfon at ddiwedd y cyfnod. 406 00:17:40,580 --> 00:17:41,670 Mae pob hawl, a bod eich enw? 407 00:17:41,670 --> 00:17:41,990 >> MYFYRWYR: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SIARADWR 1: Jason, OK wnewch chi helpu fod yn rhif naw. 409 00:17:44,530 --> 00:17:46,700 Felly, os ydych am ddilyn Ben y ffordd honno. 410 00:17:46,700 --> 00:17:47,010 >> MYFYRWYR: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SIARADWR 1: Jill, rydych yn mynd i fod yn 17, ac os byddwn i'n gwneud hyn yn fwy 412 00:17:49,630 --> 00:17:51,260 ddeallus, byddai gennyf ddechrau yn y pen arall. 413 00:17:51,260 --> 00:17:52,370 Rydych yn mynd y ffordd honno. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 A ydych chi? 416 00:17:53,670 --> 00:17:53,980 >> MYFYRWYR: Mary. 417 00:17:53,980 --> 00:17:56,130 >> SIARADWR 1: Mary, byddwch yn 22. 418 00:17:56,130 --> 00:17:58,420 A yw eich enw? 419 00:17:58,420 --> 00:17:58,810 >> MYFYRWYR: Chris. 420 00:17:58,810 --> 00:18:00,100 >> SIARADWR 1: Chris, byddwch yn 26. 421 00:18:00,100 --> 00:18:00,740 Ac yna yn olaf. 422 00:18:00,740 --> 00:18:01,400 >> MYFYRWYR: Diana. 423 00:18:01,400 --> 00:18:02,670 >> SIARADWR 1: Diana, byddwch yn 34. 424 00:18:02,670 --> 00:18:03,920 Felly, byddwch yn dod ar dros yma. 425 00:18:03,920 --> 00:18:06,360 >> Mae pob hawl, felly berffaith datrys archebu eisoes. 426 00:18:06,360 --> 00:18:09,600 A gadewch i ni fynd yn ei flaen ac yn gwneud hyn fel ein bod yn gallu mewn gwirionedd - 427 00:18:09,600 --> 00:18:11,720 Ben ydych ond yn fath o edrych allan i'r unman yno. 428 00:18:11,720 --> 00:18:15,670 Iawn, felly gadewch i ni fynd yn ei flaen ac yn darlunio hyn ddefnyddio breichiau, yn debyg iawn oeddwn i, yn union, 429 00:18:15,670 --> 00:18:16,250 beth sy'n mynd ymlaen. 430 00:18:16,250 --> 00:18:19,540 Felly, mynd yn ei flaen ac yn rhoi eich hunain a droed neu ddau rhwng eich gilydd. 431 00:18:19,540 --> 00:18:22,900 Ac yn mynd yn ei flaen ac yn pwyntio gydag un llaw i pwy bynnag dylech fod yn pwyntio at 432 00:18:22,900 --> 00:18:23,470 yn seiliedig ar hyn. 433 00:18:23,470 --> 00:18:25,890 Ac os ydych yn null dim ond tynnu sylw yn syth i lawr i'r llawr. 434 00:18:25,890 --> 00:18:27,690 Iawn, felly da. 435 00:18:27,690 --> 00:18:32,290 >> Felly nawr mae gennym restr cysylltiedig, a gadewch i mi cynnig y byddaf yn chwarae rôl y 436 00:18:32,290 --> 00:18:35,110 PTR, felly nid wyf am drafferthu cario o gwmpas hyn. 437 00:18:35,110 --> 00:18:37,830 Ac yna - rhywun confensiwn dwp - gallwch ffonio unrhyw beth rydych am yma - 438 00:18:37,830 --> 00:18:39,800 pwyntydd rhagflaenydd, pwyntydd pred - 439 00:18:39,800 --> 00:18:43,930 dim ond y llysenw roddasom yn ein cod enghreifftiol at fy llaw chwith. 440 00:18:43,930 --> 00:18:47,240 Y llaw arall fod yn mynd i gael eu cadw olrhain pwy yw pwy yn y 441 00:18:47,240 --> 00:18:48,400 dilyn senarios. 442 00:18:48,400 --> 00:18:52,390 >> Felly, mae'n debyg, yn gyntaf, yr wyf am tyn i ffwrdd yr enghraifft gyntaf o mewnosod, yn dweud 443 00:18:52,390 --> 00:18:54,330 20, i mewn i'r rhestr. 444 00:18:54,330 --> 00:18:57,160 Felly, yr wyf i'n mynd i angen rhywun i ymgorffori'r rhif 20 i ni. 445 00:18:57,160 --> 00:18:58,950 Felly mae angen i malloc rhywun rwy'n gan y gynulleidfa. 446 00:18:58,950 --> 00:18:59,380 Dewch ar i fyny. 447 00:18:59,380 --> 00:19:00,340 Beth yw eich enw? 448 00:19:00,340 --> 00:19:01,300 >> MYFYRWYR: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SIARADWR 1: Brian, popeth yn iawn, er mwyn i chi fydd y nod sy'n cynnwys 20. 450 00:19:05,270 --> 00:19:06,810 Mae pob hawl, dewch draw yma. 451 00:19:06,810 --> 00:19:10,025 Ac yn amlwg, lle mae Brian yn perthyn? 452 00:19:10,025 --> 00:19:12,190 Felly, yng nghanol - mewn gwirionedd, arhoswch funud. 453 00:19:12,190 --> 00:19:13,420 Rydym yn gwneud hyn allan o drefn. 454 00:19:13,420 --> 00:19:17,170 Rydym yn gwneud hyn yn llawer anoddach nag y mae angen iddo fod ar y dechrau. 455 00:19:17,170 --> 00:19:21,210 OK, rydym yn mynd i ddim Brian a realloc Brian â phump. 456 00:19:21,210 --> 00:19:23,680 >> Iawn, felly nawr rydym am i fewnosod Brian â phump. 457 00:19:23,680 --> 00:19:25,960 Felly dewch ar dros yma nesaf i Ben am ddim ond ennyd. 458 00:19:25,960 --> 00:19:28,250 A allwch ddweud yn ôl pob tebyg lle y stori hon yn mynd. 459 00:19:28,250 --> 00:19:30,500 Ond gadewch i ni feddwl yn ofalus am trefn y gweithrediadau. 460 00:19:30,500 --> 00:19:32,880 Ac mae'n union hyn yn weledol sy'n mynd i linell i fyny 461 00:19:32,880 --> 00:19:34,080 â'r cod enghreifftiol. 462 00:19:34,080 --> 00:19:40,120 Felly dyma rwyf wedi PTR pwyntio i ddechrau nid ar Ben, fel y cyfryw, ond ar ba bynnag 463 00:19:40,120 --> 00:19:43,245 gwerthfawrogi ei fod yn cynnwys, sydd, yn yr achos hwn yw - beth yw eich enw eto? 464 00:19:43,245 --> 00:19:43,670 >> MYFYRWYR: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SIARADWR 1: Jason, felly mae Ben a minnau yn pwyntio at Jason ar hyn o bryd. 466 00:19:47,350 --> 00:19:49,700 Felly, yn awr mae'n rhaid i mi benderfynu, ble mae Brian yn perthyn? 467 00:19:49,700 --> 00:19:53,500 Felly, yr unig beth yr wyf yn cael mynediad at ar hyn o bryd yw ei n eitem ddata. 468 00:19:53,500 --> 00:19:58,280 Felly, yr wyf i'n mynd i wirio, yn cael ei Brian llai na Jason? 469 00:19:58,280 --> 00:19:59,770 Yr ateb yn wir. 470 00:19:59,770 --> 00:20:03,680 >> Felly beth sydd angen digwydd yn awr, yn y drefn gywir? 471 00:20:03,680 --> 00:20:07,120 Mae angen i mi ddiweddaru faint o arwyddion i gyd yn y stori hon? 472 00:20:07,120 --> 00:20:10,720 Lle mae fy llaw yn dal i bwyntio at Jason, a bod eich llaw - os ydych am 473 00:20:10,720 --> 00:20:12,930 rhowch eich llaw fel, math o, yr wyf yn ddim yn gwybod, marc cwestiwn. 474 00:20:12,930 --> 00:20:14,070 OK, yn dda. 475 00:20:14,070 --> 00:20:15,670 >> Mae pob hawl, felly mae gennych ychydig o ymgeiswyr. 476 00:20:15,670 --> 00:20:20,500 Naill ai Ben neu I neu Brian neu Jason neu bawb arall, a 477 00:20:20,500 --> 00:20:21,370 Mae angen awgrymiadau i newid? 478 00:20:21,370 --> 00:20:23,260 Sawl cyfanswm o? 479 00:20:23,260 --> 00:20:24,080 >> Iawn, felly dau. 480 00:20:24,080 --> 00:20:27,090 Nid yw fy pwyntydd oes ots anymore oherwydd fy mod yn unig dros dro. 481 00:20:27,090 --> 00:20:31,370 Felly mae'n y ddau guys, yn ôl pob tebyg, ddau Ben a Brian. 482 00:20:31,370 --> 00:20:34,410 Felly, gadewch i mi cynnig ein bod yn diweddaru Ben, gan ei fod yn gyntaf. 483 00:20:34,410 --> 00:20:36,350 Yr elfen gyntaf y rhestr yn awr yn mynd i fod Brian. 484 00:20:36,350 --> 00:20:38,070 Felly Ben pwynt Brian. 485 00:20:38,070 --> 00:20:39,320 OK, yn awr beth? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Pwy sy'n cael sylw ar bwy? 488 00:20:43,460 --> 00:20:44,710 >> MYFYRIWR: [Anghlywadwy]. 489 00:20:44,710 --> 00:20:46,180 >> SIARADWR 1: Iawn felly Brian wedi bwyntio at Jason. 490 00:20:46,180 --> 00:20:48,360 Ond yr wyf wedi colli golwg ar y pwyntydd? 491 00:20:48,360 --> 00:20:49,980 Ydw i'n gwybod ble mae Jason yn? 492 00:20:49,980 --> 00:20:50,790 >> MYFYRIWR: [Anghlywadwy]. 493 00:20:50,790 --> 00:20:52,620 >> SIARADWR 1: Yr wyf yn ei wneud, gan fy mod i'n y pwyntydd dros dro. 494 00:20:52,620 --> 00:20:55,110 Ac yn ôl pob tebyg, nid wyf wedi newid bwyntio at y nod newydd. 495 00:20:55,110 --> 00:20:58,300 Felly, gallwn ni gael Brian bwynt ar bwy bynnag Rwy'n bwyntio at. 496 00:20:58,300 --> 00:20:59,000 Ac rydym yn ei wneud. 497 00:20:59,000 --> 00:21:01,890 Felly un achos, gosod yn y ddechrau'r rhestr. 498 00:21:01,890 --> 00:21:02,950 Roedd dau gam allweddol. 499 00:21:02,950 --> 00:21:06,750 Un, mae'n rhaid i ni ddiweddaru Ben, ac yna rydym hefyd wedi diweddaru Brian. 500 00:21:06,750 --> 00:21:09,230 Ac yna nid oes rhaid i mi drafferthu troedio trwy weddill y 501 00:21:09,230 --> 00:21:12,680 rhestr, gan ein bod eisoes o hyd i'w lleoliad, oherwydd ei fod yn perthyn i'r 502 00:21:12,680 --> 00:21:14,080 Gadawodd yr elfen gyntaf. 503 00:21:14,080 --> 00:21:15,400 >> Mae pob hawl, mor bert syml. 504 00:21:15,400 --> 00:21:18,110 Yn wir, yn teimlo fel ein bod bron gwneud hyn yn rhy gymhleth. 505 00:21:18,110 --> 00:21:20,240 Felly, gadewch i ni yn awr dynnaf oddi ar y diwedd y rhestr, a gweld lle 506 00:21:20,240 --> 00:21:21,380 cymhlethdod yn dechrau. 507 00:21:21,380 --> 00:21:24,560 Felly os awr, yr wyf Dyraniad gan y gynulleidfa. 508 00:21:24,560 --> 00:21:25,540 Dylai unrhyw un sydd eisiau chwarae 55? 509 00:21:25,540 --> 00:21:26,700 Mae pob hawl, gwelais eich llaw yn gyntaf. 510 00:21:26,700 --> 00:21:29,620 Dewch ar i fyny. 511 00:21:29,620 --> 00:21:30,030 Yeah. 512 00:21:30,030 --> 00:21:31,177 Beth yw eich enw? 513 00:21:31,177 --> 00:21:32,310 >> MYFYRIWR: [Anghlywadwy]. 514 00:21:32,310 --> 00:21:33,240 >> SIARADWR 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, yn dod ar i fyny. 516 00:21:33,890 --> 00:21:35,730 Byddwch yn rhif 55. 517 00:21:35,730 --> 00:21:37,820 Felly chi, wrth gwrs, yn perthyn ar ddiwedd y rhestr. 518 00:21:37,820 --> 00:21:41,850 Felly, gadewch i ni ail-chwarae yr efelychiad gyda mi sef y PTR am ddim ond ennyd. 519 00:21:41,850 --> 00:21:44,050 Felly, yr wyf i'n gyntaf yn mynd i bwyntio at beth bynnag Ben sy'n pwyntio at. 520 00:21:44,050 --> 00:21:45,900 Rydym yn ddau pwyntio nawr ar Brian. 521 00:21:45,900 --> 00:21:48,420 Felly 55 heb fod yn llai na phump. 522 00:21:48,420 --> 00:21:52,510 Felly, yr wyf i'n mynd i ddiweddaru fy hun gan pwyntio at pwyntydd nesaf Brian, a oedd 523 00:21:52,510 --> 00:21:54,450 yn awr yw, wrth gwrs, Jason. 524 00:21:54,450 --> 00:21:57,310 55 heb fod yn llai na naw, felly Rydw i'n mynd i ddiweddaru PTR. 525 00:21:57,310 --> 00:21:58,890 Rydw i'n mynd i ddiweddaru PTR. 526 00:21:58,890 --> 00:22:02,290 Rydw i'n mynd i roi'r wybodaeth ddiweddaraf PTR I'n mynd i ddiweddaru PTR. 527 00:22:02,290 --> 00:22:05,060 Ac yr wyf i'n mynd i - hmm, beth eich enw eto? 528 00:22:05,060 --> 00:22:05,560 >> MYFYRWYR: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SIARADWR 1: Diana yn pwyntio, wrth gwrs, yn null â'i llaw chwith. 530 00:22:09,190 --> 00:22:13,030 Felly, lle mae Habata mewn gwirionedd perthyn yn glir? 531 00:22:13,030 --> 00:22:15,050 I'r chwith, yma. 532 00:22:15,050 --> 00:22:19,460 Felly, sut ydw i'n gwybod i roi ei Yma Rwy'n credu fy mod i wedi sgriwio i fyny. 533 00:22:19,460 --> 00:22:22,420 Oherwydd mae'r hyn sy'n PTR celf hyn o bryd? 534 00:22:22,420 --> 00:22:23,240 NULL. 535 00:22:23,240 --> 00:22:25,580 Felly, hyd yn oed er, yn weledol, gallwn yn amlwg yn gweld pob un o'r rhain 536 00:22:25,580 --> 00:22:26,610 guys yma ar y llwyfan. 537 00:22:26,610 --> 00:22:29,680 Nid wyf wedi cadw golwg ar y flwyddyn flaenorol person yn y rhestr. 538 00:22:29,680 --> 00:22:33,210 Nid oes gennyf bys yn pwyntio allan, yn yr achos hwn, mae nifer nôd 34. 539 00:22:33,210 --> 00:22:34,760 >> Felly, gadewch i ni mewn gwirionedd yn dechrau dros y. 540 00:22:34,760 --> 00:22:37,560 Felly, yn awr yr wyf ei angen mewn gwirionedd ail newidyn lleol. 541 00:22:37,560 --> 00:22:40,980 Ac mae hyn yn yr hyn y byddwch yn ei weld yn y gwirioneddol côd sampl C, lle fel yr wyf yn mynd, 542 00:22:40,980 --> 00:22:45,860 pan fyddaf yn diweddaru fy llaw dde i bwynt Jason, gan adael y tu ôl i Brian, yr wyf yn 543 00:22:45,860 --> 00:22:51,440 well dechrau defnyddio fy llaw chwith i diweddaru lle'r oeddwn, fel bod gan fy mod yn mynd 544 00:22:51,440 --> 00:22:52,700 drwy'r rhestr hon - 545 00:22:52,700 --> 00:22:55,040 yn fwy lletchwith nag yr oeddwn yn bwriadu bellach yma ar eu golwg - 546 00:22:55,040 --> 00:22:56,740 Rydw i'n mynd i gyrraedd y ddiwedd y rhestr. 547 00:22:56,740 --> 00:23:00,020 >> Mae'r llaw yn dal yn null, sydd yn eithaf ddiwerth, ac eithrio i nodi 548 00:23:00,020 --> 00:23:02,980 Rwy'n glir ar ddiwedd y rhestr, ond erbyn hyn o leiaf yr wyf wedi hyn 549 00:23:02,980 --> 00:23:08,270 pwyntydd rhagflaenydd pwyntio yma, felly dwylo yn awr beth a beth sydd angen awgrymiadau 550 00:23:08,270 --> 00:23:10,150 i gael ei diweddaru? 551 00:23:10,150 --> 00:23:13,214 Ei law ydych chi eisiau i ad-drefnu cyntaf? 552 00:23:13,214 --> 00:23:15,190 >> MYFYRIWR: [Anghlywadwy]. 553 00:23:15,190 --> 00:23:16,220 >> SIARADWR 1: OK, felly Diana. 554 00:23:16,220 --> 00:23:21,110 Ble ydych chi eisiau i bwynt Pwyntydd chwith Diana ar? 555 00:23:21,110 --> 00:23:23,620 Yn 55, yn ôl pob tebyg, fel bod rydym wedi gosod yno. 556 00:23:23,620 --> 00:23:25,560 A lle y dylid 55 pwyntydd fynd? 557 00:23:25,560 --> 00:23:27,000 Down, yn cynrychioli null. 558 00:23:27,000 --> 00:23:28,890 Ac yn fy nwylo, ar y pwynt hwn, peidiwch bwysig oherwydd eu bod yn unig oedd 559 00:23:28,890 --> 00:23:30,070 newidynnau dros dro. 560 00:23:30,070 --> 00:23:31,030 Felly, yn awr rydym yn ei wneud. 561 00:23:31,030 --> 00:23:34,650 >> Felly, y cymhlethdod ychwanegol yno - ac nid yw mor galed i weithredu, 562 00:23:34,650 --> 00:23:38,660 ond mae angen newidyn eilaidd i wneud yn siwr bod cyn i mi symud fy hawl 563 00:23:38,660 --> 00:23:42,140 llaw, yr wyf yn diweddaru'r gwerth fy chwith llaw, pwyntydd pred yn yr achos hwn, fel y 564 00:23:42,140 --> 00:23:45,860 fod gennyf pwyntydd trailing i gadw cofnod o ble roeddwn. 565 00:23:45,860 --> 00:23:49,360 Nawr wrth fynd heibio, os ydych yn ystyried hyn drwy, mae hyn yn teimlo fel ei fod yn 566 00:23:49,360 --> 00:23:51,490 ychydig yn blino o gael i gadw golwg ar y llaw chwith. 567 00:23:51,490 --> 00:23:54,015 >> Beth fyddai ateb arall i'r broblem hon wedi bod? 568 00:23:54,015 --> 00:23:56,500 Os ydych yn cael i ailgynllunio'r data strwythur rydym yn sôn 569 00:23:56,500 --> 00:23:59,630 trwy hyn o bryd? 570 00:23:59,630 --> 00:24:02,690 Os yw hyn yn unig fath o teimlo ychydig blino i gael, fel, dau awgrymiadau 571 00:24:02,690 --> 00:24:08,430 mynd drwy'r rhestr, pwy arall a allai wedi, mewn byd delfrydol, a gynhelir 572 00:24:08,430 --> 00:24:10,160 wybodaeth sydd ei hangen ni? 573 00:24:10,160 --> 00:24:11,360 Yeah? 574 00:24:11,360 --> 00:24:12,610 >> MYFYRIWR: [Anghlywadwy]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SIARADWR 1: Yn union. 577 00:24:16,150 --> 00:24:19,130 Iawn felly mae mewn gwirionedd yn ddiddorol germ o syniad. 578 00:24:19,130 --> 00:24:22,470 Ac mae syniad hwn o pwyntydd blaenorol, pwyntio at yr elfen blaenorol. 579 00:24:22,470 --> 00:24:25,580 Beth os wyf yn unig ymgorfforodd yr tu mewn i'r rhestr ei hun? 580 00:24:25,580 --> 00:24:27,810 Ac mae'n mynd i fod yn anodd i ddelweddu hyn heb yr holl bapur 581 00:24:27,810 --> 00:24:28,830 syrthio i'r llawr. 582 00:24:28,830 --> 00:24:31,860 Ond mae'n debyg bod y rhain guys yn defnyddio'r ddwy o'u dwylo i gael blaenorol 583 00:24:31,860 --> 00:24:35,950 pwyntydd, a pwyntydd nesaf, a thrwy hynny gweithredu'r hyn y byddwn yn ei alw'n ddwbl 584 00:24:35,950 --> 00:24:36,830 restr cysylltiedig. 585 00:24:36,830 --> 00:24:41,090 Byddai hynny'n caniatáu i mi i ddatrys y rewind, llawer mwy hawdd heb mi, y 586 00:24:41,090 --> 00:24:43,800 rhaglennydd, ar ôl i gadw olrhain â llaw - 587 00:24:43,800 --> 00:24:44,980 wirioneddol llaw - 588 00:24:44,980 --> 00:24:47,280 o ble oeddwn wedi bod o'r blaen yn y rhestr. 589 00:24:47,280 --> 00:24:48,110 Felly, ni fyddwn yn gwneud hynny. 590 00:24:48,110 --> 00:24:50,950 Byddwn yn cadw pethau'n syml oherwydd dyna mynd i ddod am bris, ddwywaith yn 591 00:24:50,950 --> 00:24:53,450 llawer o le ar gyfer y pwyntiau, os ydych chi am gael ail un. 592 00:24:53,450 --> 00:24:55,760 Ond mae hynny'n wir yn gyffredin strwythur data a elwir yn 593 00:24:55,760 --> 00:24:57,410 rhestr gysylltiedig ddwbl. 594 00:24:57,410 --> 00:25:01,310 >> Gadewch i ni wneud yr enghraifft derfynol yma ac yn rhoi guys hyn allan o'u diflastod. 595 00:25:01,310 --> 00:25:03,270 Felly malloc 20. 596 00:25:03,270 --> 00:25:05,320 Dewch ar i fyny o'r eil yno. 597 00:25:05,320 --> 00:25:06,280 Mae pob hawl, beth yw eich enw? 598 00:25:06,280 --> 00:25:07,440 >> MYFYRIWR: [Anghlywadwy]. 599 00:25:07,440 --> 00:25:07,855 >> SIARADWR 1: Mae'n ddrwg gennyf? 600 00:25:07,855 --> 00:25:08,480 >> MYFYRIWR: [Anghlywadwy]. 601 00:25:08,480 --> 00:25:09,410 >> SIARADWR 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK dod ar i fyny. 603 00:25:10,230 --> 00:25:11,910 Rhaid i chi fod yn 20. 604 00:25:11,910 --> 00:25:14,720 Mae'n amlwg eich bod yn mynd i perthyn rhwng 17 a 22. 605 00:25:14,720 --> 00:25:16,150 Felly, gadewch i mi ddysgu fy ngwers. 606 00:25:16,150 --> 00:25:18,150 Dwi'n mynd i ddechrau pwyntydd pwyntio at Brian. 607 00:25:18,150 --> 00:25:21,190 Ac yr wyf i'n mynd i gael fy llaw chwith dim ond diweddaru i Brian fel yr wyf yn symud i 608 00:25:21,190 --> 00:25:23,600 Jason, gwirio yn 20 yn llai na naw? 609 00:25:23,600 --> 00:25:24,060 Rhif 610 00:25:24,060 --> 00:25:25,430 Yn 20 yn llai na 17? 611 00:25:25,430 --> 00:25:25,880 Rhif 612 00:25:25,880 --> 00:25:27,450 Yn 20 yn llai na 22? 613 00:25:27,450 --> 00:25:28,440 Ydw. 614 00:25:28,440 --> 00:25:34,070 Felly mae angen i pa awgrymiadau neu dwylo i newid lle maent yn pwyntio nawr? 615 00:25:34,070 --> 00:25:37,070 >> Felly, gallwn wneud 17 pwyntio at 20. 616 00:25:37,070 --> 00:25:37,860 Felly, mae hynny'n iawn. 617 00:25:37,860 --> 00:25:40,080 Ble ydym ni eisiau i bwynt eich pwyntydd nawr? 618 00:25:40,080 --> 00:25:41,330 Yn 22. 619 00:25:41,330 --> 00:25:45,410 Ac rydym yn gwybod lle 22, unwaith eto diolch i fy pwyntydd dros dro. 620 00:25:45,410 --> 00:25:46,760 Felly, rydym yn iawn yno. 621 00:25:46,760 --> 00:25:49,440 Felly, oherwydd storio dros dro hwn Rwyf wedi cadw golwg ar lle mae pawb yn. 622 00:25:49,440 --> 00:25:55,055 Ac yn awr y gallwch chi fynd ar eu golwg i mewn lle ydych yn perthyn, ac yn awr rydym angen 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 peli straen, a rownd o gymeradwyaeth ar gyfer 624 00:25:58,410 --> 00:25:59,770 guys hyn, os gallem. 625 00:25:59,770 --> 00:26:00,410 Gwneud 'N glws. 626 00:26:00,410 --> 00:26:05,320 >> [Cymeradwyaeth] 627 00:26:05,320 --> 00:26:06,330 >> SIARADWR 1: Pob hawl. 628 00:26:06,330 --> 00:26:09,860 Ac efallai y byddwch yn cadw'r darnau o bapur fel cofroddion. 629 00:26:09,860 --> 00:26:15,930 >> Mae pob hawl, felly, ymddiried ynof mae'n llawer yn haws i gerdded drwy hynny gyda 630 00:26:15,930 --> 00:26:17,680 bobl nag y mae gyda chod gwirioneddol. 631 00:26:17,680 --> 00:26:22,690 Ond yr hyn y byddwch yn dod o hyd yn ychydig funudau'n erbyn hyn, yw bod un fath - oh, diolch yn fawr. 632 00:26:22,690 --> 00:26:23,630 Diolch i chi - 633 00:26:23,630 --> 00:26:29,360 yw y byddwch yn dod o hyd bod yr un data strwythur, rhestr cysylltiedig, gall mewn gwirionedd 634 00:26:29,360 --> 00:26:33,200 yn cael ei ddefnyddio fel bloc adeiladu hyd yn oed yn fwy strwythurau data soffistigedig. 635 00:26:33,200 --> 00:26:37,620 >> Ac yn sylweddoli hefyd y thema yma yw bod rydym wedi cyflwyno gwbl yn fwy 636 00:26:37,620 --> 00:26:40,060 cymhlethdod ati i weithredu o algorithm hwn. 637 00:26:40,060 --> 00:26:43,940 Gosod, ac os ydym yn mynd drwyddi, dileu a chwilio, ychydig 638 00:26:43,940 --> 00:26:46,660 yn fwy cymhleth nag y mae'n ei oedd gydag amrywiaeth. 639 00:26:46,660 --> 00:26:48,040 Ond rydym yn ennill rhywfaint o egni. 640 00:26:48,040 --> 00:26:50,180 Rydym yn cael strwythur data addasol. 641 00:26:50,180 --> 00:26:54,010 >> Ond unwaith eto, rydym yn talu pris o gael rhywfaint o cymhlethdod ychwanegol, yn 642 00:26:54,010 --> 00:26:54,910 weithredu. 643 00:26:54,910 --> 00:26:56,750 Ac rydym yn rhoi'r gorau mynediad ar hap. 644 00:26:56,750 --> 00:27:00,450 Ac i fod yn onest, nid oes rhai 'n glws glân sleid gallaf ei roi i chi 645 00:27:00,450 --> 00:27:03,120 yn dweud dyma pam restr cysylltiedig yn well na arae. 646 00:27:03,120 --> 00:27:04,100 A'i adael ar hynny. 647 00:27:04,100 --> 00:27:07,520 Oherwydd bod y thema ddigwydd eto yn awr, hyd yn oed yn fwy felly yn yr wythnosau nesaf, yn 648 00:27:07,520 --> 00:27:10,200 nad oes o reidrwydd ateb cywir. 649 00:27:10,200 --> 00:27:13,830 >> Dyma pam y mae gennym yr echelin ar wahân o ddylunio ar gyfer setiau broblem. 650 00:27:13,830 --> 00:27:17,700 Bydd yn y cyd-destun sensitif iawn p'un a ydych am ddefnyddio'r data hwn 651 00:27:17,700 --> 00:27:21,750 strwythur neu bod un, a bydd yn yn dibynnu ar yr hyn sy'n bwysig i chi o ran 652 00:27:21,750 --> 00:27:24,620 o adnoddau a chymhlethdod. 653 00:27:24,620 --> 00:27:28,830 >> Ond gadewch i mi yn cynnig bod y data delfrydol strwythur, y greal sanctaidd, yn 654 00:27:28,830 --> 00:27:32,200 rhywbeth sy'n cysonyn amser, waeth faint o bethau yn 655 00:27:32,200 --> 00:27:36,940 y tu mewn iddo, ni fyddai'n wych pe bai strwythur data a ddychwelwyd atebion yn 656 00:27:36,940 --> 00:27:37,920 cysonyn amser. 657 00:27:37,920 --> 00:27:38,330 Ydw. 658 00:27:38,330 --> 00:27:40,110 Mae'r gair yn eich geiriadur enfawr. 659 00:27:40,110 --> 00:27:41,550 Neu ddim, nid yw'r gair hwn yw. 660 00:27:41,550 --> 00:27:43,270 Neu unrhyw broblem o'r fath yno. 661 00:27:43,270 --> 00:27:46,360 Wel, gadewch i ni weld os na allwn o leiaf cymryd cam tuag at hynny. 662 00:27:46,360 --> 00:27:50,190 >> Gadewch i mi yn cynnig strwythur data newydd sy'n Gellir ei ddefnyddio ar gyfer gwahanol bethau, 663 00:27:50,190 --> 00:27:52,260 yn yr achos hwn a elwir tabl hash. 664 00:27:52,260 --> 00:27:55,590 Ac felly rydym yn mewn gwirionedd yn ôl i glancing mewn amrywiaeth, yn yr achos hwn, ac 665 00:27:55,590 --> 00:28:00,550 braidd yn fympwyol, rwyf wedi tynnu hwn tabl hash fel amrywiaeth gyda'r math o 666 00:28:00,550 --> 00:28:02,810 arae dau ddimensiwn - 667 00:28:02,810 --> 00:28:05,410 neu yn hytrach ei fod yn darlunio yma fel dwy amrywiaeth dimensiwn - ond mae hyn yn unig yw 668 00:28:05,410 --> 00:28:10,770 amrywiaeth o faint 26, fel bod os ydym ffoniwch y bwrdd amrywiaeth, braced tabl 669 00:28:10,770 --> 00:28:12,440 sero yn y petryal ar y brig. 670 00:28:12,440 --> 00:28:15,090 Tabl braced 25 yw'r petryal ar y gwaelod. 671 00:28:15,090 --> 00:28:18,620 A dyma sut y gallwn dynnu data strwythur lle rwyf am i storio 672 00:28:18,620 --> 00:28:19,790 bobl enwau. 673 00:28:19,790 --> 00:28:24,370 >> Felly, er enghraifft, ac ni fyddaf yn tynnu'r holl beth yma ar y uwchben, os wyf yn 674 00:28:24,370 --> 00:28:29,160 Roedd amrywiaeth hon, ac yr wyf i'n awr yn mynd i ffoniwch tabl hash, ac mae hyn eto 675 00:28:29,160 --> 00:28:31,360 leoliad sero. 676 00:28:31,360 --> 00:28:34,840 Mae hyn dyma yw lleoliad un, ac yn y blaen. 677 00:28:34,840 --> 00:28:37,880 Yr wyf yn honni fy mod am ddefnyddio'r data hwn strwythur, er mwyn trafod, 678 00:28:37,880 --> 00:28:42,600 i storio enwau pobl, Alice a Bob a Charlie ac enwau eraill o'r fath. 679 00:28:42,600 --> 00:28:46,110 Felly, meddwl am hyn yn awr fel egin o, dyweder, geiriadur 680 00:28:46,110 --> 00:28:47,520 gyda llawer o eiriau. 681 00:28:47,520 --> 00:28:49,435 Maent yn digwydd i fod yn enwau yn ein enghraifft yma. 682 00:28:49,435 --> 00:28:52,560 Ac mae hyn i gyd yn rhy germane, efallai, i gweithredu gwirydd sillafu, wrth i ni 683 00:28:52,560 --> 00:28:54,400 Efallai ar gyfer problem gosod chwech. 684 00:28:54,400 --> 00:28:59,300 >> Felly, os oes gennym amrywiaeth o gyfanswm maint 26 fel bod hwn yn lleoliad 25ain 685 00:28:59,300 --> 00:29:03,390 ar y gwaelod, ac yr wyf yn honni bod Alice yn y gair cyntaf yn y geiriadur o 686 00:29:03,390 --> 00:29:07,260 enwau yr wyf am i fewnosod i mewn i RAM, yn y strwythur data, ble 687 00:29:07,260 --> 00:29:12,480 greddf yn dweud eich bod yn Alice yn Dylai enw fynd amrywiaeth hwn? 688 00:29:12,480 --> 00:29:13,510 >> Mae gennym 26 o opsiynau. 689 00:29:13,510 --> 00:29:14,990 Lle rydym am i roi ei? 690 00:29:14,990 --> 00:29:16,200 Rydym am iddi yn braced sero, dde? 691 00:29:16,200 --> 00:29:18,280 A i Alice, gadewch i ni alw y sero. 692 00:29:18,280 --> 00:29:20,110 A fydd B yn un, ac C yn ddau. 693 00:29:20,110 --> 00:29:22,600 Felly, rydym yn mynd i ysgrifennu Enw Alice i fyny yma. 694 00:29:22,600 --> 00:29:24,890 Os byddwn wedyn yn mewnosod Bob, ei Bydd enw ewch yma. 695 00:29:24,890 --> 00:29:27,280 Bydd Charlie ewch yma. 696 00:29:27,280 --> 00:29:30,500 Ac yn y blaen i lawr drwy y strwythur data. 697 00:29:30,500 --> 00:29:32,090 >> Mae hwn yn strwythur data gwych. 698 00:29:32,090 --> 00:29:32,730 Pam? 699 00:29:32,730 --> 00:29:37,460 Wel beth yw'r amser rhedeg mewnosod enw dynol i mewn i hyn 700 00:29:37,460 --> 00:29:39,850 data strwythur ar hyn o bryd? 701 00:29:39,850 --> 00:29:43,702 O ystyried bod y tabl hwn yn cael ei weithredu, yn wir, fel arae. 702 00:29:43,702 --> 00:29:44,940 Wel, mae'n amser cyson. 703 00:29:44,940 --> 00:29:45,800 Mae'n drefn un. 704 00:29:45,800 --> 00:29:46,360 Pam? 705 00:29:46,360 --> 00:29:48,630 >> Wel sut yr ydych yn penderfynu ar lle mae Alice yn perthyn? 706 00:29:48,630 --> 00:29:51,000 Byddwch yn edrych ar pa lythyren ei enw? 707 00:29:51,000 --> 00:29:51,490 Y cyntaf. 708 00:29:51,490 --> 00:29:54,350 A gallwch gael yno, os yw'n llinyn, at jyst yn edrych ar linyn 709 00:29:54,350 --> 00:29:55,200 braced sero. 710 00:29:55,200 --> 00:29:57,110 Felly, y cymeriad 0 y llinyn. 711 00:29:57,110 --> 00:29:57,610 Mae hynny'n hawdd. 712 00:29:57,610 --> 00:30:00,350 Gwnaethom hynny yn y crypto wythnosau aseiniad yn ôl. 713 00:30:00,350 --> 00:30:05,310 Ac yna unwaith y byddwch yn gwybod bod Alice llythyr CYFALAF A, gallwn dynnu 714 00:30:05,310 --> 00:30:08,160 oddi ar 65 oed neu gyfalaf A ei hun, sy'n rhoi i ni sero. 715 00:30:08,160 --> 00:30:10,940 Felly, rydym yn gwybod bod Alice yn perthyn yn y lleoliad sero. 716 00:30:10,940 --> 00:30:14,240 >> Ac o ystyried pwyntydd i'r data hwn strwythur, o ryw fath, pa mor hir y 717 00:30:14,240 --> 00:30:18,840 ei gymryd i mi ddod o hyd i leoliad sero mewn amrywiaeth? 718 00:30:18,840 --> 00:30:22,080 Dim ond un cam, i'r dde Mae'n amser cyson oherwydd y mynediad ar hap ydym yn 719 00:30:22,080 --> 00:30:23,780 Roedd arfaethedig yn nodwedd o fyrdd. 720 00:30:23,780 --> 00:30:28,570 Felly, yn fyr, figuring allan yr hyn y mae'r mynegai enw Alice yw, sydd, yn 721 00:30:28,570 --> 00:30:32,610 yr achos hwn, yn A, neu adael i ni dim ond datrys hynny i sero, os yw B yn un a C yn 722 00:30:32,610 --> 00:30:34,900 dau, figuring bod allan yw cysonyn amser. 723 00:30:34,900 --> 00:30:38,510 Fi jyst yn rhaid i ni edrych ar ei llythyr cyntaf, figuring gwybod ble sero yn 724 00:30:38,510 --> 00:30:40,460 amrywiaeth yn cysonyn amser hefyd. 725 00:30:40,460 --> 00:30:42,140 Felly dechnegol dyna fel dau gam yn awr. 726 00:30:42,140 --> 00:30:43,330 Ond mae hynny'n dal i fod yn gyson. 727 00:30:43,330 --> 00:30:46,880 Felly, rydym yn galw bod O fawr o un, felly rydym wedi mewnosod Alice yn y tabl hwn yn 728 00:30:46,880 --> 00:30:48,440 cysonyn amser. 729 00:30:48,440 --> 00:30:50,960 >> Ond wrth gwrs, fy mod yn cael naïf yma, dde? 730 00:30:50,960 --> 00:30:53,240 Beth os oes 'na Aaron yn y dosbarth? 731 00:30:53,240 --> 00:30:53,990 Neu Alicia? 732 00:30:53,990 --> 00:30:57,230 Neu unrhyw enwau eraill gan ddechrau gyda A. Os ydym yn mynd i roi 733 00:30:57,230 --> 00:31:00,800 y person hwnnw, dde? 734 00:31:00,800 --> 00:31:03,420 Yr wyf yn golygu, ar hyn o bryd does dim ond tri bobl ar y bwrdd, felly efallai ni 735 00:31:03,420 --> 00:31:07,490 Dylai roi Aaron yn y lleoliad sero un dau tri. 736 00:31:07,490 --> 00:31:09,480 >> Iawn, gallwn roi A yma. 737 00:31:09,480 --> 00:31:13,350 Ond yna, os ydym yn ceisio mewnosod David yn y rhestr hon, ble mae David yn mynd? 738 00:31:13,350 --> 00:31:15,170 Nawr ein system yn dechrau torri i lawr, dde? 739 00:31:15,170 --> 00:31:19,210 Oherwydd erbyn hyn yn dod i ben i fyny David yma os Aaron mewn gwirionedd yma. 740 00:31:19,210 --> 00:31:23,060 Ac felly yn awr, y cyfan syniad o gael strwythur data glân sy'n rhoi i ni 741 00:31:23,060 --> 00:31:28,010 mewnosodiadau cysonyn amser bellach yn cysonyn amser, gan fod rhaid i mi 742 00:31:28,010 --> 00:31:31,240 gwirio, oh, Damnit, rhywun yn barod yn y lleoliad Alice. 743 00:31:31,240 --> 00:31:35,320 >> Gadewch i mi ymchwilio i weddill y data hwn strwythur, yn chwilio am fan a'r lle i roi 744 00:31:35,320 --> 00:31:37,130 rhywun fel enw Aaron. 745 00:31:37,130 --> 00:31:39,390 Ac felly hynny hefyd yn dechrau i gymryd amser llinol. 746 00:31:39,390 --> 00:31:42,710 Ar ben hynny, os ydych yn awr am ddod o hyd i'r Aaron yn y strwythur data, a'ch bod yn 747 00:31:42,710 --> 00:31:45,430 gwirio, ac nid enw Aaron yma. 748 00:31:45,430 --> 00:31:47,960 Yn ddelfrydol, byddech yn dweud Aaron nid yn y strwythur data. 749 00:31:47,960 --> 00:31:51,530 Ond os ydych chi'n dechrau gwneud lle i Aaron lle y dylai fod wedi bod yn D 750 00:31:51,530 --> 00:31:55,600 neu E, gallwch chi, achos gwaethaf, mae'n rhaid i wirio y strwythur data cyfan, yn 751 00:31:55,600 --> 00:31:59,480 ac os felly ei bod yn datganoli i fod yn rhywbeth llinellol ym maint y tabl. 752 00:31:59,480 --> 00:32:00,920 >> Felly, iawn, 'n annhymerus' atgyweiria hon. 753 00:32:00,920 --> 00:32:04,200 Y broblem yma yw fy mod wedi 26 elfen yn y casgliad hwn. 754 00:32:04,200 --> 00:32:05,000 Gadewch i mi ei newid. 755 00:32:05,000 --> 00:32:06,010 Wps. 756 00:32:06,010 --> 00:32:10,600 Gadewch i mi newid fel bod yn hytrach lles maint 26 i gyd, yn sylwi ar y gwaelod 757 00:32:10,600 --> 00:32:12,720 mynegai yn mynd i newid i n minws 1. 758 00:32:12,720 --> 00:32:16,610 Os yw 26 yn amlwg yn rhy fach ar gyfer pobl ' enwau, oherwydd mae miloedd o 759 00:32:16,610 --> 00:32:20,830 enwau'r byd, gadewch i ni dim ond gwneud mewn 100 neu 1,000 neu 10,000. 760 00:32:20,830 --> 00:32:22,960 Gadewch i 'jyst dyrannu llawer mwy o le. 761 00:32:22,960 --> 00:32:27,230 >> Wel, nid yw hynny o reidrwydd yn gostwng y tebygolrwydd na fydd gennym ddwy 762 00:32:27,230 --> 00:32:31,510 pobl ag enwau gan ddechrau gyda A, a felly, yr ydych yn mynd i geisio rhoi A 763 00:32:31,510 --> 00:32:33,120 enwau ar sero lleoliad hyd. 764 00:32:33,120 --> 00:32:36,850 Maent yn dal i fynd i wrthdaro, a golygu ein bod yn dal angen ateb i roi 765 00:32:36,850 --> 00:32:41,020 Alice ac Aaron a Alicia ac eraill enwau gan ddechrau gyda A mewn mannau eraill. 766 00:32:41,020 --> 00:32:43,460 Ond faint o broblem yw hyn? 767 00:32:43,460 --> 00:32:46,870 Beth yw'r tebygolrwydd y bydd eich cael gwrthdrawiadau mewn data 768 00:32:46,870 --> 00:32:48,240 strwythur fel hyn? 769 00:32:48,240 --> 00:32:52,570 >> Wel, gadewch i mi - byddwn yn dod yn ôl i'r cwestiwn yma. 770 00:32:52,570 --> 00:32:55,530 Ac edrych ar sut y gallem datrys yn gyntaf. 771 00:32:55,530 --> 00:32:58,480 Gadewch i mi dynnu i fyny y cynnig hwn yma. 772 00:32:58,480 --> 00:33:02,020 Yr hyn yr ydym newydd ei ddisgrifio yn algorithm, a hewristig enw llinellol 773 00:33:02,020 --> 00:33:05,030 treiddgar sy'n golygu, os ydych yn ceisio rhoi'r rhywbeth yma yn y data hwn 774 00:33:05,030 --> 00:33:08,920 strwythur, a elwir tabl hash, ac nad oes lle yno, byddwch 775 00:33:08,920 --> 00:33:12,000 wirioneddol ymchwilio i'r strwythur data gwirio, a yw hyn ar gael? 776 00:33:12,000 --> 00:33:13,430 A yw hyn ar gael yw hyn ar gael? 777 00:33:13,430 --> 00:33:13,980 A yw hyn ar gael? 778 00:33:13,980 --> 00:33:17,550 A phan yn olaf yw, eich mewnosoder y enwi eich bod fwriadwyd yn wreiddiol 779 00:33:17,550 --> 00:33:19,370 mewn mannau eraill yn y lleoliad hwnnw. 780 00:33:19,370 --> 00:33:23,360 Ond yn yr achos gwaethaf, yr unig fan a'r lle a allai fod yn y waelod y data 781 00:33:23,360 --> 00:33:25,090 strwythur, y diwedd y rhesi. 782 00:33:25,090 --> 00:33:30,130 >> Felly llinol stilio, yn yr achos gwaethaf, yn datganoli i mewn i algorithm llinol lle 783 00:33:30,130 --> 00:33:34,500 Aaron, os yw'n digwydd i gael eu mewnosod ddiwethaf yn y strwythur data, fe allai 784 00:33:34,500 --> 00:33:39,540 gwrthdaro â'r lleoliad cyntaf, ond wedyn ben erbyn anlwc ar ddiwedd. 785 00:33:39,540 --> 00:33:43,940 Felly, nid yw hyn yn gyson greal sanctaidd o amser i ni. 786 00:33:43,940 --> 00:33:47,650 Mae'r dull hwn o elfennau mewnosod i mewn i strwythur data a elwir yn hash 787 00:33:47,650 --> 00:33:52,050 Nid yw'n ymddangos bod y tabl yn cysonyn amser o leiaf nid yn yr achos cyffredinol. 788 00:33:52,050 --> 00:33:54,000 Gall ddatganoli i fod yn rhywbeth llinol. 789 00:33:54,000 --> 00:33:56,970 >> Felly beth os ydym yn datrys gwrthdrawiadau ychydig yn wahanol? 790 00:33:56,970 --> 00:34:00,740 Felly dyma fwy soffistigedig tuag at yr hyn sy'n dal i fod 791 00:34:00,740 --> 00:34:02,800 a elwir yn tabl hash. 792 00:34:02,800 --> 00:34:05,890 A thrwy hash, wrth fynd heibio, yr hyn Yr wyf yn golygu y mynegai a 793 00:34:05,890 --> 00:34:07,070 Cyfeiriais ato yn gynharach. 794 00:34:07,070 --> 00:34:09,810 Gall I hash rhywbeth yn ystyried fel berf. 795 00:34:09,810 --> 00:34:13,690 >> Felly, os ydych hash Alice 'na enw, swyddogaeth hash, fel petai, 796 00:34:13,690 --> 00:34:14,710 Dylid dychwelyd rhif. 797 00:34:14,710 --> 00:34:18,199 Yn yr achos hwn yn sero os yw'n perthyn yn Lleoliad sero, un os y mae yn perthyn yn 798 00:34:18,199 --> 00:34:20,000 leoliad yn un, ac yn y blaen. 799 00:34:20,000 --> 00:34:24,360 Felly, fy swyddogaeth hash hyd yn hyn wedi bod yn super syml, dim ond yn edrych ar y 800 00:34:24,360 --> 00:34:26,159 llythyren gyntaf yn enw'r rhywun. 801 00:34:26,159 --> 00:34:29,090 Ond mae swyddogaeth hash yn cymryd fel mewnbwn rhyw darn o ddata, a 802 00:34:29,090 --> 00:34:30,210 llinyn, yn int, beth bynnag. 803 00:34:30,210 --> 00:34:32,239 Ac mae'n poeri allan fel arfer yn rhif. 804 00:34:32,239 --> 00:34:35,739 Ac mae'r nifer yn lle bod data elfen yn perthyn mewn strwythur data 805 00:34:35,739 --> 00:34:37,800 a elwir yma fel tabl hash. 806 00:34:37,800 --> 00:34:41,400 >> Felly, dim ond yn reddfol, mae hwn yn cyd-destun ychydig yn wahanol. 807 00:34:41,400 --> 00:34:44,170 Mae hyn mewn gwirionedd yn cyfeirio at enghraifft cynnwys penblwyddi, lle 808 00:34:44,170 --> 00:34:46,850 gallai fod cymaint â 31 diwrnod yn y mis. 809 00:34:46,850 --> 00:34:52,239 Ond beth oedd y person hwn benderfynu ei wneud mewn achos o wrthdrawiad? 810 00:34:52,239 --> 00:34:55,304 Cyd-destun yn awr, ac nid yn gwrthdrawiad o enwau, ond mae gwrthdrawiad pen-blwydd, 811 00:34:55,304 --> 00:35:00,760 os oes dau o bobl yr un pen-blwydd ar y 2 Hydref, er enghraifft. 812 00:35:00,760 --> 00:35:02,120 >> MYFYRIWR: [Anghlywadwy]. 813 00:35:02,120 --> 00:35:05,010 >> SIARADWR 1: Yeah, felly dyma ni wedi y leveraging rhestrau cysylltiedig. 814 00:35:05,010 --> 00:35:07,830 Felly, mae'n edrych ychydig yn wahanol nag i ni dynnu yn gynharach. 815 00:35:07,830 --> 00:35:10,790 Ond mae'n ymddangos ein bod yn rhaid i arae ar yr ochr chwith. 816 00:35:10,790 --> 00:35:13,230 Dyna un mynegai, nid ar gyfer unrhyw rheswm penodol. 817 00:35:13,230 --> 00:35:14,630 Ond mae'n dal i fod yn arae. 818 00:35:14,630 --> 00:35:16,160 Mae'n amrywiaeth o awgrymiadau. 819 00:35:16,160 --> 00:35:20,670 A phob un o'r elfennau hynny, pob un y cylchoedd neu slaes - y slaes 820 00:35:20,670 --> 00:35:23,970 cynrychioli null - pob un o'r rhain awgrymiadau yn ymddangos yn pwyntio i 821 00:35:23,970 --> 00:35:25,730 pa strwythur data? 822 00:35:25,730 --> 00:35:26,890 Mae rhestr cysylltiedig. 823 00:35:26,890 --> 00:35:30,530 >> Felly, erbyn hyn mae gennym y gallu i cod caled yn ein rhaglen 824 00:35:30,530 --> 00:35:32,010 maint y tabl. 825 00:35:32,010 --> 00:35:35,360 Yn yr achos hwn, rydym yn gwybod bod hi byth mwy na 31 diwrnod mewn mis. 826 00:35:35,360 --> 00:35:38,480 Mor galed codio gwerth fel 31 yn rhesymol yn y cyd-destun. 827 00:35:38,480 --> 00:35:42,700 Yng nghyd-destun enwau, caled codio 26 nid yw'n afresymol yw'n bobl 828 00:35:42,700 --> 00:35:46,340 enwau ond yn dechrau gydag, er enghraifft, yr wyddor yn ymwneud A drwy Z. 829 00:35:46,340 --> 00:35:50,180 >> Gall Rydym yn gwthio i gyd i mewn i'r data strwythur ar yr amod, pan fyddwn yn cael 830 00:35:50,180 --> 00:35:55,330 gwrthdrawiad, nid ydym yn rhoi'r enwau yma, rydym yn hytrach na meddwl am y celloedd hyn 831 00:35:55,330 --> 00:36:00,270 nid fel llinynnau eu hunain, ond fel y awgrymiadau, er enghraifft, Alice. 832 00:36:00,270 --> 00:36:03,660 Ac yna gall Alice gael pwyntydd arall i enw arall gan ddechrau gyda 833 00:36:03,660 --> 00:36:06,150 A. Ac Bob mewn gwirionedd yn mynd dros yma. 834 00:36:06,150 --> 00:36:10,850 >> Ac os oes enw arall dechrau gyda B, ei fod yn dod i ben i fyny dros yma. 835 00:36:10,850 --> 00:36:15,070 Ac felly mae pob un o'r elfennau hyn tabl dau, os rydym yn cynllunio hyn a 836 00:36:15,070 --> 00:36:17,350 ychydig yn fwy deallus - 837 00:36:17,350 --> 00:36:18,125 yn dod ar - 838 00:36:18,125 --> 00:36:22,950 os ydym yn cynllunio hyn ychydig yn fwy gelfydd, yn awr yn dod yn ddata addasol 839 00:36:22,950 --> 00:36:27,720 strwythur, lle nid oes terfyn caled ar faint o elfennau gallwch osod 840 00:36:27,720 --> 00:36:30,700 i mewn iddo oherwydd os oes gennych gwrthdrawiad, mae hynny'n iawn. 841 00:36:30,700 --> 00:36:34,690 Dim ond mynd yn ei flaen ac yn ei atodi i yr hyn a welsom ychydig yn ôl oedd 842 00:36:34,690 --> 00:36:38,290 a elwir yn restr cysylltiedig. 843 00:36:38,290 --> 00:36:39,690 >> Wel, gadewch i ni oedi am ychydig funud. 844 00:36:39,690 --> 00:36:42,570 Beth yw'r tebygolrwydd o gwrthdrawiad yn y lle cyntaf? 845 00:36:42,570 --> 00:36:45,480 Iawn, efallai fy mod yn meddwl dros, efallai Rydw i wrth fy peirianneg broblem hon, 846 00:36:45,480 --> 00:36:46,370 oherwydd eich bod yn gwybod beth? 847 00:36:46,370 --> 00:36:49,070 Oes, gallaf ddod o hyd mympwyol enghreifftiau oddi ar ben fy mhen fel 848 00:36:49,070 --> 00:36:52,870 Allison ac Aaron, ond mewn gwirionedd, o ystyried dosbarthiad unffurf o 849 00:36:52,870 --> 00:36:56,990 mewnbynnau, hynny yw rhai mewnosodiadau ar hap i mewn i strwythur data, beth mewn gwirionedd yw 850 00:36:56,990 --> 00:36:58,580 y tebygolrwydd o gwrthdrawiad? 851 00:36:58,580 --> 00:37:01,670 Wel yn troi allan, mae'n mewn gwirionedd yn super uchel. 852 00:37:01,670 --> 00:37:03,850 Gadewch i mi cyffredinoli hyn problem fel hyn. 853 00:37:03,850 --> 00:37:08,890 >> Felly, mewn ystafell o n CS50 fyfyrwyr, beth y tebygolrwydd bod o leiaf 854 00:37:08,890 --> 00:37:11,010 dau fyfyriwr yn yr ystafell cael yr un pen-blwydd? 855 00:37:11,010 --> 00:37:13,346 Felly mae beth. ychydig o hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 o bobl yma a nifer o cant o bobl yn y cartref heddiw. 857 00:37:16,790 --> 00:37:20,670 Felly, os ydych yn awyddus i ofyn i ni'n hunain beth sydd y tebygolrwydd o ddau o bobl 858 00:37:20,670 --> 00:37:23,930 yn yr ystafell hon yn cael yr un pen-blwydd, gallwn ffigur hyn. 859 00:37:23,930 --> 00:37:26,250 Ac yr wyf yn gwneud cais mewn gwirionedd mae dau bobl sydd â'r un pen-blwydd. 860 00:37:26,250 --> 00:37:29,560 >> Er enghraifft, a oes unrhyw un wedi pen-blwydd heddiw? 861 00:37:29,560 --> 00:37:31,340 Ddoe? 862 00:37:31,340 --> 00:37:32,590 Yfory? 863 00:37:32,590 --> 00:37:35,980 Mae pob hawl, felly mae'n teimlo fel mod i'n mynd i gael i wneud hyn 363, neu fel bod mwy 864 00:37:35,980 --> 00:37:39,500 amser i mewn gwirionedd yn chyfrif i maes os oes gennych gwrthdrawiad. 865 00:37:39,500 --> 00:37:42,350 Neu gallem dim ond gwneud hyn yn fathemategol yn hytrach na tediously 866 00:37:42,350 --> 00:37:43,200 wneud hyn. 867 00:37:43,200 --> 00:37:44,500 Ac yn cynnig y canlynol. 868 00:37:44,500 --> 00:37:48,740 >> Felly, yr wyf yn cynnig y gallem fodelu'r tebygolrwydd o ddau o bobl gael y 869 00:37:48,740 --> 00:37:55,320 un pen-blwydd fel y tebygolrwydd o 1 minws y tebygolrwydd o unrhyw un â 870 00:37:55,320 --> 00:37:56,290 yr un pen-blwydd. 871 00:37:56,290 --> 00:37:59,960 Felly, i gael hyn, ac mae hyn yn dim ond y ffordd ffansi o ysgrifennu hwn, er y 872 00:37:59,960 --> 00:38:03,090 person cyntaf yn yr ystafell, bydd ef neu hi Gall unrhyw un o'r posibl 873 00:38:03,090 --> 00:38:07,370 pen-blwydd gan dybio 365 diwrnod yn y flwyddyn, gydag ymddiheuriadau i bobl ag 874 00:38:07,370 --> 00:38:08,760 pen-blwydd 29 Chwefror. 875 00:38:08,760 --> 00:38:13,470 >> Felly, y person cyntaf yn yr ystafell hon yn rhad ac am ddim i gael unrhyw nifer o pen-blwydd 876 00:38:13,470 --> 00:38:18,280 allan o'r posibiliadau 365 fel bod byddwn yn gwneud hynny 365 wedi'i rannu â 365, 877 00:38:18,280 --> 00:38:18,990 sy'n un. 878 00:38:18,990 --> 00:38:22,700 Mae'r person nesaf yn yr ystafell, os yw'r nod yw osgoi gwrthdrawiad, dim ond 879 00:38:22,700 --> 00:38:26,460 yn cael ei ben-blwydd ar sut llawer o wahanol ddyddiau posibl? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Felly, yr ail dymor yn ymadrodd hwn yn hanfod wneud hynny cwestiwn i ni 882 00:38:31,430 --> 00:38:33,460 trwy dynnu oddi ar un diwrnod posibl. 883 00:38:33,460 --> 00:38:36,390 Ac yna y diwrnod nesaf, y diwrnod nesaf, y diwrnod nesaf i lawr at gyfanswm nifer 884 00:38:36,390 --> 00:38:38,100 o bobl yn yr ystafell. 885 00:38:38,100 --> 00:38:41,290 >> Ac os ydym yn ystyried, beth felly yw y tebygolrwydd nid pawb yn cael 886 00:38:41,290 --> 00:38:45,265 pen-blwydd unigryw, ond unwaith eto 1 llai hynny, yr hyn a gawn yn fynegiant 887 00:38:45,265 --> 00:38:47,810 y gall fancifully iawn edrych fel hyn. 888 00:38:47,810 --> 00:38:50,330 Ond mae'n fwy diddorol i edrych ar eu golwg. 889 00:38:50,330 --> 00:38:55,120 Mae hwn yn siart lle ar yr echelin-x yn y nifer o bobl yn yr ystafell, y 890 00:38:55,120 --> 00:38:56,180 nifer y pen-blwydd. 891 00:38:56,180 --> 00:38:59,840 Ar y y-echelin yw'r tebygolrwydd o wrthdrawiad, dau o bobl 892 00:38:59,840 --> 00:39:01,230 cael yr un pen-blwydd. 893 00:39:01,230 --> 00:39:05,020 >> Ac mae'r prydau parod o'r gromlin hon yn cyn gynted ag y byddwch yn dod i hoffi 40 894 00:39:05,020 --> 00:39:11,110 fyfyrwyr, rydych yn i fyny at 90% o debygolrwydd combinatorically o ddau 895 00:39:11,110 --> 00:39:13,550 bobl neu fwy yn cael yr un pen-blwydd. 896 00:39:13,550 --> 00:39:18,600 Ac ar ôl i chi ddod i hoffi 58 o bobl ei fod yn bron i 100% o gyfle y ddwy 897 00:39:18,600 --> 00:39:21,310 bobl yn yr ystafell yn mynd i gael y un pen-blwydd, er bod yna 898 00:39:21,310 --> 00:39:26,650 365 neu 366 bwcedi posibl, a dim ond 58 o bobl yn yr ystafell. 899 00:39:26,650 --> 00:39:29,900 Dim ond ystadegol rydych yn debygol o cael gwrthdrawiadau, sydd yn fyr 900 00:39:29,900 --> 00:39:31,810 cymell y drafodaeth hon. 901 00:39:31,810 --> 00:39:35,890 Hyd yn oed os ydym yn cael ffansi yma, ac dechrau cael cadwyni hyn, rydym yn dal i 902 00:39:35,890 --> 00:39:36,950 mynd i gael gwrthdrawiadau. 903 00:39:36,950 --> 00:39:42,710 >> Felly mae hynny'n codi'r cwestiwn, beth yw'r gost o wneud fewnosodiadau a dileadau 904 00:39:42,710 --> 00:39:44,850 i mewn i strwythur data fel hyn? 905 00:39:44,850 --> 00:39:46,630 Wel gadewch i mi gynnig - 906 00:39:46,630 --> 00:39:51,570 a gadewch i mi fynd yn ôl i'r sgrin dros yma - os ydym wedi n elfennau yn y 907 00:39:51,570 --> 00:39:56,330 rhestr, felly os ydym yn ceisio ei fewnosod n elfennau, ac mae gennym 908 00:39:56,330 --> 00:39:58,050 faint o gyfanswm bwcedi? 909 00:39:58,050 --> 00:40:03,450 Gadewch i ni ddweud 31 gyfanswm bwcedi yn achos pen-blwydd. 910 00:40:03,450 --> 00:40:09,240 Beth sydd hyd uchafswm o o gadwyni hyn yn bosibl? 911 00:40:09,240 --> 00:40:12,670 >> Os unwaith eto mae 31 posibl pen-blwydd mewn mis a roddir. 912 00:40:12,670 --> 00:40:14,580 Ac rydym yn unig clumping pawb - 913 00:40:14,580 --> 00:40:15,580 mewn gwirionedd mae hynny'n enghraifft dwp. 914 00:40:15,580 --> 00:40:16,960 Gadewch i ni wneud 26 yn lle hynny. 915 00:40:16,960 --> 00:40:20,890 Felly, os mewn gwirionedd yn rhaid i bobl y mae eu henwau dechrau gyda A drwy Z, gan roi 916 00:40:20,890 --> 00:40:22,780 ni 26 o bosibiliadau. 917 00:40:22,780 --> 00:40:25,920 Ac rydym yn defnyddio strwythur data fel yr un yr ydym jyst yn gweld, lle yr ydym wedi 918 00:40:25,920 --> 00:40:30,210 amrywiaeth o awgrymiadau, pob un ohonynt yn cyfeirio at restr cysylltiedig lle y 919 00:40:30,210 --> 00:40:32,360 rhestr cyntaf yw pawb gydag enw Alice. 920 00:40:32,360 --> 00:40:35,770 Mae'r ail restr yn bob â'r enwi gan ddechrau gyda A, gan ddechrau 921 00:40:35,770 --> 00:40:36,980 gyda B, ac yn y blaen. 922 00:40:36,980 --> 00:40:41,020 >> Beth sydd hyd tebygol pob un o'r rhestrau hynny os ydym yn tybio amgylchedd glân 'n glws 923 00:40:41,020 --> 00:40:45,410 dosbarthu enwau A drwy Z ar draws y strwythur data cyfan? 924 00:40:45,410 --> 00:40:50,210 Mae pobl n yn y strwythur data wedi'i rannu â 26, os ydynt yn 'n glws 925 00:40:50,210 --> 00:40:52,110 gwasgaru dros y cyfan strwythur data. 926 00:40:52,110 --> 00:40:54,970 Felly, hyd pob un o'r rhain cadwyni yn n rannu â 26. 927 00:40:54,970 --> 00:40:57,380 Ond yn O mawr nodiant, beth yw hynny? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Beth yw hynny mewn gwirionedd? 930 00:41:02,440 --> 00:41:04,150 Felly mae'n wirioneddol dim ond n, dde? 931 00:41:04,150 --> 00:41:06,620 Oherwydd ein bod wedi dweud yn y gorffennol, bod Ych chi rannu â 26. 932 00:41:06,620 --> 00:41:08,710 Ie, mewn gwirionedd yn gyflymach. 933 00:41:08,710 --> 00:41:12,720 Ond mewn egwyddor, nid yw'n sylfaenol i gyd yn gyflymach. 934 00:41:12,720 --> 00:41:16,040 >> Felly, nid yw'n ymddangos i ni fod yr holl bod llawer yn agosach at y greal sanctaidd. 935 00:41:16,040 --> 00:41:17,750 Mewn gwirionedd, mae hyn yn unig yw amser llinol. 936 00:41:17,750 --> 00:41:20,790 Heck, ar y pwynt hwn, pam nad ydym dim ond yn defnyddio un rhestr cysylltiedig enfawr? 937 00:41:20,790 --> 00:41:23,510 Pam nad ydym yn unig yn defnyddio un enfawr amrywiaeth i storio enwau 938 00:41:23,510 --> 00:41:25,010 pawb yn yr ystafell? 939 00:41:25,010 --> 00:41:28,280 Wel, a oes rhywbeth o hyd grymus am dabl hash? 940 00:41:28,280 --> 00:41:30,810 A oes yn dal rhywbeth cymhellol am strwythur data 941 00:41:30,810 --> 00:41:33,940 sy'n edrych fel hyn? 942 00:41:33,940 --> 00:41:35,182 Hwn. 943 00:41:35,182 --> 00:41:37,050 >> MYFYRIWR: [Anghlywadwy]. 944 00:41:37,050 --> 00:41:39,840 >> SIARADWR 1: Iawn, ac eto os mai dim ond algorithm amser llinol, ac mae 945 00:41:39,840 --> 00:41:42,780 strwythur data amser llinol, pam nad ydw i'n dim ond storio enw pawb mewn mawr 946 00:41:42,780 --> 00:41:44,210 amrywiaeth, neu mewn rhestr cysylltiedig mawr? 947 00:41:44,210 --> 00:41:47,010 Ac yn rhoi'r gorau i wneud CS mor llawer anoddach nag y mae angen iddo fod? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Beth yn rymus am hyn, hyd yn oed er fy mod yn crafu allan? 950 00:41:53,190 --> 00:41:54,930 >> MYFYRIWR: [Anghlywadwy]. 951 00:41:54,930 --> 00:41:57,040 >> SIARADWR 1: Nid yw mewnosodiadau chi? 952 00:41:57,040 --> 00:41:58,140 Drud anymore. 953 00:41:58,140 --> 00:42:03,390 Felly mewnosodiadau bosibl y gallai dal i o amser yn gyson, hyd yn oed os yw eich data 954 00:42:03,390 --> 00:42:07,910 strwythur yn edrych fel hyn, mae amrywiaeth o awgrymiadau, pob un ohonynt yn pwyntio at 955 00:42:07,910 --> 00:42:09,550 potensial i fod yn rhestr gysylltiedig. 956 00:42:09,550 --> 00:42:15,220 Sut y gallech ei chyrraedd yn gyson amser gosod enwau? 957 00:42:15,220 --> 00:42:16,280 Lynu yn y blaen, dde? 958 00:42:16,280 --> 00:42:19,290 >> Os byddwn yn aberthu nod dylunio o yn gynharach, lle rydym yn awyddus i gadw 959 00:42:19,290 --> 00:42:22,650 enw pawb, er enghraifft, didoli, neu bob un o'r rhifau ar y llwyfan didoli, 960 00:42:22,650 --> 00:42:25,020 Mae'n debyg bod gennym restr cysylltiedig heb eu didoli. 961 00:42:25,020 --> 00:42:29,960 Dim ond yn costio i ni yn un neu ddau gam, fel yn achos Ben a Brian 962 00:42:29,960 --> 00:42:32,750 yn gynharach, i fewnosod elfen yn ddechrau'r rhestr. 963 00:42:32,750 --> 00:42:36,090 Felly, os nad ydym yn poeni am ddatrys yr holl o enwau gan ddechrau gyda A neu bob 964 00:42:36,090 --> 00:42:39,660 yr enwau gan ddechrau gyda B, gallwn yn dal i cyflawni osod cysonyn amser. 965 00:42:39,660 --> 00:42:43,900 Awr yn edrych i fyny Alice neu Bob neu unrhyw enw yn fwy cyffredinol yn dal i beth? 966 00:42:43,900 --> 00:42:48,100 Mae'n fawr O n rannu gan 26, yn y achos delfrydol lle mae pawb yn unffurf 967 00:42:48,100 --> 00:42:51,190 dosbarthu, lle mae cymaint o A gan fod Z, ac mae'n debyg mai 968 00:42:51,190 --> 00:42:52,220 afrealistig. 969 00:42:52,220 --> 00:42:53,880 Ond mae hynny'n dal i fod yn llinol. 970 00:42:53,880 --> 00:42:57,120 >> Ond yma, rydym yn dod yn ôl at y pwynt o nodiant asymptotic yn 971 00:42:57,120 --> 00:42:58,600 ddamcaniaethol wir. 972 00:42:58,600 --> 00:43:02,960 Ond yn y byd go iawn, os wyf yn honni bod Gall fy rhaglen wneud rhywbeth 26 gwaith 973 00:43:02,960 --> 00:43:06,210 gyflymach na chi, y mae eu rhaglen ydych chi'n mynd i well defnyddio? 974 00:43:06,210 --> 00:43:09,660 Chi neu fy un i, a yw 26 gwaith yn gyflymach? 975 00:43:09,660 --> 00:43:14,320 Yn realistig, bydd y person y mae ei 26 gwaith yn gyflymach, hyd yn oed os ddamcaniaethol 976 00:43:14,320 --> 00:43:18,790 ein algorithmau yn rhedeg yn yr un asymptotic amser yn rhedeg. 977 00:43:18,790 --> 00:43:20,940 >> Gadewch i mi yn cynnig gwahanol ateb yn gyfan gwbl. 978 00:43:20,940 --> 00:43:24,380 Ac os nad yw hyn yn chwythu eich meddwl, rydym yn allan o strwythurau data. 979 00:43:24,380 --> 00:43:27,420 Felly mae hyn yn ei fod yn trie - 980 00:43:27,420 --> 00:43:28,520 math o enw dwp. 981 00:43:28,520 --> 00:43:32,880 Mae'n dod o adalwadau, a'r gair ei sillafu trie, t-r-i-e, oherwydd 982 00:43:32,880 --> 00:43:34,450 adalw cwrs yn swnio fel trie. 983 00:43:34,450 --> 00:43:36,580 Ond dyna hanes y gair trie. 984 00:43:36,580 --> 00:43:40,980 >> Felly trie yn wir rhyw fath o goeden, ac mae hefyd yn chwarae ar y gair hwnnw. 985 00:43:40,980 --> 00:43:46,330 A hyd yn oed er na allwch ei weld yn eithaf gyda delweddu hon, mae trie yn 986 00:43:46,330 --> 00:43:50,790 coeden strwythuro, fel coeden teulu gyda un hynafiad ar y brig a llawer 987 00:43:50,790 --> 00:43:54,530 o wyrion ac wyrion mawr fel yn gadael ar y gwaelod. 988 00:43:54,530 --> 00:43:58,100 Ond mae pob nod mewn trie yn arae. 989 00:43:58,100 --> 00:44:00,680 Ac mae'n mewn amrywiaeth - a gadewch i gorsymleiddio'r am eiliad - ei fod yn 990 00:44:00,680 --> 00:44:04,600 amrywiaeth, yn yr achos hwn, o faint 26, lle bob nod unwaith eto mae amrywiaeth o faint 991 00:44:04,600 --> 00:44:09,000 26, lle mae'r elfen 0 yn y amrywiaeth cynrychioli A, a'r olaf 992 00:44:09,000 --> 00:44:11,810 ym mhob elfen o'r fath amrywiaeth cynrychioli Z. 993 00:44:11,810 --> 00:44:15,520 >> Felly, yr wyf yn cynnig, felly, bod y data hwn Gall strwythur, a elwir yn trie, yn 994 00:44:15,520 --> 00:44:17,600 defnyddio hefyd i storio geiriau. 995 00:44:17,600 --> 00:44:21,740 Gwelsom funud yn ôl sut y gallem storio geiriau, neu yn yr enwau achos hwn, ac rydym yn 996 00:44:21,740 --> 00:44:25,440 welsom yn gynharach sut y gallwn storio rhifau, ond os ydym yn canolbwyntio ar enwau neu linynnau 997 00:44:25,440 --> 00:44:27,460 yma, yn sylwi ar yr hyn sy'n ddiddorol. 998 00:44:27,460 --> 00:44:32,210 Yr wyf yn honni bod yr enw Maxwell yw tu mewn y strwythur data. 999 00:44:32,210 --> 00:44:33,730 Lle ydych chi'n gweld Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> MYFYRIWR: [Anghlywadwy]. 1001 00:44:35,140 --> 00:44:36,240 >> SIARADWR 1: Ar y chwith. 1002 00:44:36,240 --> 00:44:39,910 Felly, yr hyn sy'n ddiddorol gyda data hwn strwythur yn hytrach na siop y 1003 00:44:39,910 --> 00:44:46,200 llinyn M-A-X-W-E-L-L slaes sero, pob contiguously, yr hyn yr ydych yn ei wneud yn lle hynny 1004 00:44:46,200 --> 00:44:46,890 yn dilyn. 1005 00:44:46,890 --> 00:44:50,510 Os yw hyn yn trie fel strwythur data, mae pob un o'i nodau yw eto arae, 1006 00:44:50,510 --> 00:44:54,650 ac rydych am i storio Maxwell, i chi yn gyntaf mynegai ac felly nod y gwraidd, fel 1007 00:44:54,650 --> 00:44:57,810 i siarad, y nod topmost, yn y lleoliad M, ar y dde, felly 1008 00:44:57,810 --> 00:44:59,160 fras yn y canol. 1009 00:44:59,160 --> 00:45:03,740 Ac yna oddi yno, byddwch yn dilyn pwyntydd i blentyn nodau, fel petai. 1010 00:45:03,740 --> 00:45:06,150 Felly, yn yr ystyr coeden deulu, ei ddilyn i lawr. 1011 00:45:06,150 --> 00:45:09,030 Ac mae hynny'n eich arwain at nod arall ar y chwith yno, sydd yn 1012 00:45:09,030 --> 00:45:10,540 dim ond amrywiaeth arall. 1013 00:45:10,540 --> 00:45:14,710 >> Ac yna os ydych am storio Maxwell, ddod o hyd i'r pwyntydd sy'n cynrychioli 1014 00:45:14,710 --> 00:45:16,430 A, sydd yn yr un yma yma. 1015 00:45:16,430 --> 00:45:17,840 Yna byddwch yn mynd at y nod nesaf. 1016 00:45:17,840 --> 00:45:20,100 A rhybudd - dyma pam y darlun yn ychydig yn twyllo - 1017 00:45:20,100 --> 00:45:21,990 nod hwn yn edrych super bach. 1018 00:45:21,990 --> 00:45:26,050 Ond i'r dde o hyn yw Y a Z. Mai dim ond yr awdur wedi cwtogi y 1019 00:45:26,050 --> 00:45:27,630 llun er mwyn i chi mewn gwirionedd yn gweld pethau. 1020 00:45:27,630 --> 00:45:30,400 Fel arall y llun byddai'n hynod o eang. 1021 00:45:30,400 --> 00:45:36,180 Felly, yn awr yr ydych mynegai i mewn i leoliad X, yna W, Yna E, yna i'r Ch, yna L. Yna beth sydd 1022 00:45:36,180 --> 00:45:37,380 chwilfrydedd hwn? 1023 00:45:37,380 --> 00:45:41,250 >> Wel, os ydym yn defnyddio y math hwn o newydd cymryd ar sut i storio llinyn mewn 1024 00:45:41,250 --> 00:45:44,500 strwythur data, mae angen i chi yn dal i hanfod gwirio i ffwrdd yn y data 1025 00:45:44,500 --> 00:45:47,250 strwythur y gair yn dod i ben yma. 1026 00:45:47,250 --> 00:45:50,830 Mewn geiriau eraill, pob un o'r nodau hyn rhywsut wedi i gofio ein bod yn 1027 00:45:50,830 --> 00:45:53,500 dilyn mewn gwirionedd yr holl awgrymiadau hyn ac yn gadael ychydig 1028 00:45:53,500 --> 00:45:58,370 bara briwsion ar waelod yma o hyn strwythur i ddangos M-A-X-W-E-L-L yn 1029 00:45:58,370 --> 00:46:00,230 yn wir yn y strwythur data. 1030 00:46:00,230 --> 00:46:02,040 >> Felly, efallai y byddwn yn gwneud hyn fel a ganlyn. 1031 00:46:02,040 --> 00:46:06,810 Mae pob un o'r nodau yn y llun rydym yn unig gwelodd un, amrywiaeth o faint 27. 1032 00:46:06,810 --> 00:46:10,550 Ac mae'n awr yn 27, oherwydd yn p gosod chwech, byddwn mewn gwirionedd yn rhoi collnod i chi, 1033 00:46:10,550 --> 00:46:13,590 er mwyn i ni gael enwau fel O'Reilly ac eraill sydd â collnod. 1034 00:46:13,590 --> 00:46:14,820 Ond mae un syniad. 1035 00:46:14,820 --> 00:46:17,710 Mae pob un o'r elfennau hynny yn y pwyntiau amrywiaeth i strwythur 1036 00:46:17,710 --> 00:46:19,320 nod, felly dim ond nod. 1037 00:46:19,320 --> 00:46:21,430 Felly, mae hyn yn ein hatgoffa iawn o'n rhestr gysylltiedig. 1038 00:46:21,430 --> 00:46:24,550 >> Ac yna mae gen i Boole, a byddaf ffoniwch gair, sydd yn unig yn mynd i fod yn 1039 00:46:24,550 --> 00:46:29,120 yn wir os yw gair yn dod i ben ar hyn o nod yn y goeden. 1040 00:46:29,120 --> 00:46:32,870 Mae'n effeithiol cynrychioli'r bach triongl gwelsom funud yn ôl. 1041 00:46:32,870 --> 00:46:37,190 Felly, os yw gair yn dod i ben ar y nod yn y coed, bydd y gair hwnnw maes fod yn wir, 1042 00:46:37,190 --> 00:46:41,990 sydd yn gysyniadol gwirio i ffwrdd, neu rydym yn tynnu triongl hwn, ie yno 1043 00:46:41,990 --> 00:46:44,080 yn air yma. 1044 00:46:44,080 --> 00:46:45,120 >> Felly, mae hwn yn trie. 1045 00:46:45,120 --> 00:46:48,540 Ac yn awr y cwestiwn yw, beth yn ei rhedeg amser? 1046 00:46:48,540 --> 00:46:49,930 A yw'n fawr o O n? 1047 00:46:49,930 --> 00:46:51,410 A yw'n rhywbeth arall? 1048 00:46:51,410 --> 00:46:57,330 Wel, os ydych wedi n enwau yn y data hwn strwythur, Maxwell yn un o 1049 00:46:57,330 --> 00:47:02,330 iddynt, beth yw'r amser rhedeg mewnosod neu ddod o hyd Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Beth yw'r amser yn rhedeg o mewnosod Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Os oes n enwau eraill eisoes yn y tabl? 1053 00:47:11,740 --> 00:47:12,507 Yeah? 1054 00:47:12,507 --> 00:47:15,429 >> MYFYRIWR: [Anghlywadwy]. 1055 00:47:15,429 --> 00:47:17,550 >> SIARADWR 1: Yeah, 'i' hyd yr enw, dde? 1056 00:47:17,550 --> 00:47:24,420 Felly M-a-x-w-e-l-l felly mae'n teimlo fel hyn algorithm yn fawr O o saith. 1057 00:47:24,420 --> 00:47:26,580 Yn awr, wrth gwrs, yr enw yn amrywio o ran hyd. 1058 00:47:26,580 --> 00:47:27,380 Efallai ei fod yn enw byr. 1059 00:47:27,380 --> 00:47:28,600 Efallai ei fod yn enw hirach. 1060 00:47:28,600 --> 00:47:33,390 Ond yr hyn sy'n allweddol yma yw bod mae'n nifer cyson. 1061 00:47:33,390 --> 00:47:36,810 Ac efallai nid yw'n wir yn gyson, ond duw, os realistig, mewn 1062 00:47:36,810 --> 00:47:41,570 geiriadur, mae debyg bod rhai terfyn ar y nifer o lythyrau mewn 1063 00:47:41,570 --> 00:47:43,820 enw'r person hwnnw mewn gwlad benodol. 1064 00:47:43,820 --> 00:47:46,940 >> Ac felly gallwn gymryd yn ganiataol y gwerth yn gyson. 1065 00:47:46,940 --> 00:47:47,750 Nid wyf yn gwybod beth ydyw. 1066 00:47:47,750 --> 00:47:50,440 Mae'n debyg yn fwy na'r rydym yn meddwl ei fod yn. 1067 00:47:50,440 --> 00:47:52,720 Oherwydd bod bob amser yn rhyw gornel achos gydag enw hir crazy. 1068 00:47:52,720 --> 00:47:56,360 Felly, gadewch i ni ei alw'n k, ond mae'n dal i fod yn gyson yn ôl pob tebyg, oherwydd y mae pob 1069 00:47:56,360 --> 00:48:00,190 enwi yn y byd, o leiaf mewn gwlad arbennig, yw bod hyd neu 1070 00:48:00,190 --> 00:48:01,780 byrrach, felly mae'n gyson. 1071 00:48:01,780 --> 00:48:04,490 Ond pan fyddwn wedi dweud rhywbeth yn fawr O o werth cyson, beth sy'n bod 1072 00:48:04,490 --> 00:48:07,760 sy'n cyfateb mewn gwirionedd i? 1073 00:48:07,760 --> 00:48:10,420 Mae hynny'n wir yr un peth yn dweud cysonyn amser. 1074 00:48:10,420 --> 00:48:11,530 >> Nawr rydym yn fath o dwyllo, dde? 1075 00:48:11,530 --> 00:48:15,340 Rydym yn fath o ddylanwad rhywfaint o theori yma i ddweud bod trefn k yn dda, yn 1076 00:48:15,340 --> 00:48:17,450 mewn gwirionedd ond yn archebu o un, ac mae'n amser cyson. 1077 00:48:17,450 --> 00:48:18,200 Ond mae mewn gwirionedd. 1078 00:48:18,200 --> 00:48:22,550 Oherwydd bod y mewnwelediad allweddol yma yw bod os ydym wedi n enwau eisoes yn hyn o 1079 00:48:22,550 --> 00:48:26,010 strwythur data, ac yr ydym mewnosoder Maxwell, yw faint o amser mae'n ei gymryd i ni 1080 00:48:26,010 --> 00:48:29,530 mewnosoder Maxwell o gwbl yr effeithir arnynt gan faint o bobl eraill 1081 00:48:29,530 --> 00:48:31,100 yn y strwythur data? 1082 00:48:31,100 --> 00:48:31,670 Nid yw'n ymddangos i fod. 1083 00:48:31,670 --> 00:48:36,280 Os bu'n rhaid i mi yn fwy o biliwn elfen i hyn trie, ac yna rhowch Maxwell, yn cael ei 1084 00:48:36,280 --> 00:48:38,650 ef yn mhob heffeithio? 1085 00:48:38,650 --> 00:48:39,050 Rhif 1086 00:48:39,050 --> 00:48:42,950 A dyna wahanol i unrhyw o'r data diwrnod strwythurau rydym wedi gweld hyd yn hyn, lle 1087 00:48:42,950 --> 00:48:46,820 yr amser yn rhedeg eich algorithm yn gwbl annibynnol ar faint o 1088 00:48:46,820 --> 00:48:51,430 pethau ai peidio eisoes yn y strwythur data. 1089 00:48:51,430 --> 00:48:54,650 >> Ac felly gyda hyn yn ei roi i chi yn awr yn cyfle i p set chwech, a fydd yn 1090 00:48:54,650 --> 00:48:58,310 unwaith eto yn golygu gweithredu eich hun gwiriwr sillafu, darllen yn 150,000 1091 00:48:58,310 --> 00:49:01,050 geiriau, y ffordd orau i storio'r Nid yw o reidrwydd yn amlwg. 1092 00:49:01,050 --> 00:49:04,030 Ac er fy mod i wedi dyheu am ddod o hyd i y greal sanctaidd, nid wyf yn 1093 00:49:04,030 --> 00:49:05,330 honni bod trie yn. 1094 00:49:05,330 --> 00:49:09,810 Yn wir, efallai y tabl hash yn dda iawn yn profi i fod yn llawer mwy effeithlon. 1095 00:49:09,810 --> 00:49:10,830 Ond y rhai yn unig - 1096 00:49:10,830 --> 00:49:14,620 mai dim ond un o'r penderfyniadau dylunio bydd yn rhaid i chi ei wneud. 1097 00:49:14,620 --> 00:49:18,920 >> Ond yn cau gadewch i ni gymryd 50 neu lai eiliad i gymryd cipolwg ar yr hyn sydd 1098 00:49:18,920 --> 00:49:22,190 blaen yr wythnos nesaf a thu hwnt yn pontio o'r llinell orchymyn 1099 00:49:22,190 --> 00:49:26,220 os yw rhaglenni byd C i bethau ar y we yn seiliedig ac ieithoedd fel PHP a 1100 00:49:26,220 --> 00:49:30,350 JavaScript a'r rhyngrwyd ei hun, protocolau fel HTTP, a ydych wedi 1101 00:49:30,350 --> 00:49:32,870 gymryd yn ganiataol ar gyfer y blynyddoedd nawr, ac yn y rhan fwyaf o teipio pob 1102 00:49:32,870 --> 00:49:34,440 dydd, efallai, neu weld. 1103 00:49:34,440 --> 00:49:37,420 A byddwn yn dechrau croen yn ôl y haenau o'r hyn sydd ar y rhyngrwyd. 1104 00:49:37,420 --> 00:49:40,650 A beth yw'r cod y wrth wraidd offer heddiw. 1105 00:49:40,650 --> 00:49:43,230 Felly, 50 eiliad o ymlid hwn yma. 1106 00:49:43,230 --> 00:49:46,570 Rwy'n rhoi Warriors o'r Net i chi. 1107 00:49:46,570 --> 00:49:51,370 >> [VIDEO Playback] 1108 00:49:51,370 --> 00:49:56,764 >> -Daeth gyda neges. 1109 00:49:56,764 --> 00:50:00,687 Gyda protocol ei holl hun. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Daeth i fyd o waliau tân creulon, llwybryddion di-hid, a pheryglon yn hyn 1112 00:50:19,780 --> 00:50:22,600 yn waeth na marwolaeth. 1113 00:50:22,600 --> 00:50:23,590 Mae'n gyflym. 1114 00:50:23,590 --> 00:50:25,300 Mae'n gryf. 1115 00:50:25,300 --> 00:50:27,700 Mae'n TCPIP. 1116 00:50:27,700 --> 00:50:30,420 Ac mae wedi cael eich cyfeiriad. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Rhyfelwyr y Net. 1119 00:50:34,590 --> 00:50:35,290 >> [VIDEO END Playback] 1120 00:50:35,290 --> 00:50:38,070 >> SIARADWR 1: Dyna sut y rhyngrwyd Bydd gweithio fel yr wythnos nesaf. 1121 00:50:38,070 --> 00:50:40,406