1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Pob hawl. 3 00:00:12,250 --> 00:00:13,860 Croeso yn ôl i CS50. 4 00:00:13,860 --> 00:00:16,190 Mae hyn yn dechrau'r wythnos 8. 5 00:00:16,190 --> 00:00:21,320 A dwyn i gof bod problem set 5 a ddaeth i ben gydag ychydig o her. 6 00:00:21,320 --> 00:00:25,210 Felly, gan dybio eich bod adennill eich holl Cymrodyr addysgu a ffotograffau CA yn 7 00:00:25,210 --> 00:00:30,480 yn y ffeil card.raw, rydych yn gymwys yn hyn ddod o hyd pob un o'r bobl hynny, a 8 00:00:30,480 --> 00:00:34,510 Bydd un enillydd lwcus cerdded adref gydag un o'r pethau hyn, y cynnig naid 9 00:00:34,510 --> 00:00:37,450 ddyfais y gallwch eu defnyddio ar gyfer derfynol prosiectau, er enghraifft. 10 00:00:37,450 --> 00:00:39,860 >> Mae hyn, bob blwyddyn, yn arwain at ychydig o creepiness. 11 00:00:39,860 --> 00:00:43,480 Ac felly yr hyn yr wyf yn meddwl y byddwn i'n ei wneud yw rhannu gyda chi rai o'r nodiadau sydd wedi 12 00:00:43,480 --> 00:00:47,370 mynd yn ôl ac ymlaen dros y rhestr staff yn ddiweddar. 13 00:00:47,370 --> 00:00:51,110 Er enghraifft, dim ond neithiwr, dyfyniad unquote, gan un o'r staff 14 00:00:51,110 --> 00:00:55,000 aelodau, "Rwyf newydd gael cnoc fyfyrwyr ar fy drws i gymryd llun gyda mi. 15 00:00:55,000 --> 00:00:59,020 Llech, yr wyf yn dweud wrthych. "Wedi ei eithaf disgrifiadol ac yna rydym yn symud 16 00:00:59,020 --> 00:01:02,830 ymlaen i, awr neu ddwy yn ddiweddarach, "Roedd gen i myfyriwr yn aros i mi ar ôl adran 17 00:01:02,830 --> 00:01:06,080 ac yr oedd ganddo ein holl enwau a lluniau ar rai dalennau o bapur. "Mae pob hawl. 18 00:01:06,080 --> 00:01:09,230 Felly, trefnu, ond nid bob un sy'n creepy eto. 19 00:01:09,230 --> 00:01:12,520 >> Yna, "Roeddwn yn tu allan i'r dref dros y penwythnos, a pan fyddaf yn mynd yn ôl, roedd un o bob 20 00:01:12,520 --> 00:01:12,630 fy 21 00:01:12,630 --> 00:01:16,740 ystafell wely. "[Chwerthin] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: dyfyniad nesaf o staff aelod, "Daeth myfyriwr i fy ty yn 23 00:01:20,410 --> 00:01:25,330 Somerville am 04:00 y bore. "Next staff, "Cefais i fy gwesty yn San 24 00:01:25,330 --> 00:01:30,016 Francisco a myfyriwr yn aros am mi yn y cyntedd gyda thri DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Math o camera. 26 00:01:31,510 --> 00:01:34,980 "Dydw i ddim hyd yn oed ar staff semester hwn, ond torrodd yn fyfyriwr yn fy nhŷ hwn 27 00:01:34,980 --> 00:01:40,480 bore a chofnodi yr holl beth gyda Google Glass. "Ac yna yn olaf, 28 00:01:40,480 --> 00:01:43,650 "O leiaf 12 o bobl yn eiddgar disgwyl i mi pan fyddaf yn mynd allan o fy 29 00:01:43,650 --> 00:01:44,800 limo, ac yna yr 30 00:01:44,800 --> 00:01:46,970 ddeffro. "Mae pob hawl. 31 00:01:46,970 --> 00:01:57,690 Felly, ymysg y lluniau, fel y gall galw i gof, yn cyd-hyn yma, pwy ydych chi 32 00:01:57,690 --> 00:02:01,850 Gallai gwybod fel Milo Banana, sy'n byw gyda Lauren Carvalho, ein prif 33 00:02:01,850 --> 00:02:02,905 Cymrawd addysgu. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, dod yma bachgen. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Cofiwch chi, mae'n gwisgo Google Glass, felly byddwn yn dangos i chi hyn i gyd ar ôl. 38 00:02:12,230 --> 00:02:16,190 Felly, mae hyn yn Milo os hoffech chi dynnu llun gydag ef wedyn. 39 00:02:16,190 --> 00:02:18,240 Os hoffech chi i chwilio at y gynulleidfa yno. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Dyna ffilm da. 42 00:02:20,200 --> 00:02:22,556 Wel, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 O, peidiwch â gwneud hynny. 44 00:02:23,941 --> 00:02:29,020 >> [Chwerthin] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Felly gair ac yna ar yr hyn sydd o'n blaenau, oherwydd wrth i ni ddechrau pontio, 47 00:02:34,550 --> 00:02:38,410 yr wythnos hon yn benodol, o C mewn amgylchedd llinell gorchymyn i PHP a 48 00:02:38,410 --> 00:02:42,720 JavaScript a SQL ac HTML a CSS mewn amgylchedd ar y we, byddwn yn 49 00:02:42,720 --> 00:02:44,490 eich arfogi â'r holl mwy o wybodaeth ar gyfer 50 00:02:44,490 --> 00:02:46,010 prosiectau terfynol posibl. 51 00:02:46,010 --> 00:02:49,240 Toward perwyl hwnnw, mae'r cwrs yn traddodiad o gynnal seminarau a 52 00:02:49,240 --> 00:02:50,950 ar bynciau ymylol i'r cwrs. 53 00:02:50,950 --> 00:02:54,330 Llawer iawn yn ymwneud â rhaglenni ac i datblygu app ac yn y blaen, ond 54 00:02:54,330 --> 00:02:57,010 Nid yw o reidrwydd harchwilio gan maes llafur y cwrs ei hun. 55 00:02:57,010 --> 00:03:00,250 >> Felly, os y gallech fod â diddordeb mewn un neu fwy o'r seminarau eleni, 56 00:03:00,250 --> 00:03:02,530 gofrestru yn cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Mae seminarau hŷn ar cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Ac ar y rhestr hyd yn hyn ar gyfer y flwyddyn yn Apps We Amazing gyda Ruby ar 59 00:03:10,620 --> 00:03:13,580 Rails, a wneir yn lle'r iaith PHP. 60 00:03:13,580 --> 00:03:14,900 Ieithyddiaeth Chyfrifiadurol. 61 00:03:14,900 --> 00:03:18,710 Cyflwyniad i iOS, sef y lwyfan sy'n cael ei ddefnyddio ar gyfer iPhone a 62 00:03:18,710 --> 00:03:19,850 datblygiad iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript ar gyfer Apps We, byddwn yn ymdrin hynny, ond yn y seminar hwn, byddwch yn mynd 64 00:03:22,890 --> 00:03:24,070 rhoi mwy o fanylion. 65 00:03:24,070 --> 00:03:27,390 >> Naid Motion, felly byddwn mewn gwirionedd yn cael rhywfaint o o'n ffrindiau o Gynnig Leap, 66 00:03:27,390 --> 00:03:29,160 y cwmni ei hun, ymuno â ni. 67 00:03:29,160 --> 00:03:31,800 Yfory, mewn gwirionedd, er mwyn darparu yn ymarferol seminar, os 68 00:03:31,800 --> 00:03:33,320 o ddiddordeb i chi. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, techneg arall ar gyfer defnyddio JavaScript nid mewn porwr, 70 00:03:38,770 --> 00:03:39,970 ond ar weinydd. 71 00:03:39,970 --> 00:03:42,110 Node.js, sydd yn fawr iawn yn yr un modd hefyd. 72 00:03:42,110 --> 00:03:43,650 'N llyfn Android Design. 73 00:03:43,650 --> 00:03:46,990 Android fod yn amgen poblogaidd iawn i iOS a Ffenestri Ffôn 74 00:03:46,990 --> 00:03:48,790 a llwyfannau symudol eraill. 75 00:03:48,790 --> 00:03:51,180 Ac Web Diogelwch Defense Active. 76 00:03:51,180 --> 00:03:54,590 >> Felly, mewn gwirionedd, os hoffech i gymryd rhan yn hyn, gadewch i mi 77 00:03:54,590 --> 00:03:55,840 gwneud nodyn o hyn. 78 00:03:55,840 --> 00:03:57,790 Rydym yn hapus iawn i ddweud bod ein ffrindiau yn Leap 79 00:03:57,790 --> 00:03:59,140 Motion, sydd yn startup - 80 00:03:59,140 --> 00:04:01,300 ddyfais hon mewn gwirionedd dim ond daeth allan ychydig fisoedd yn ôl - 81 00:04:01,300 --> 00:04:05,960 wedi rhoi 30 ddyfeisiadau o'r fath rasol i'r dosbarth am gymaint o lawer o fyfyrwyr, os 82 00:04:05,960 --> 00:04:08,670 hoffech chi fenthyg y caledwedd tua diwedd semester a'i ddefnyddio ar gyfer 83 00:04:08,670 --> 00:04:10,390 prosiect terfynol gwirioneddol. 84 00:04:10,390 --> 00:04:11,890 Maent yn cefnogi nifer o ieithoedd. 85 00:04:11,890 --> 00:04:16,040 Nid oedd yr un ohonynt C, nid oes yr un ohonynt PHP, felly gwireddu un neu fwy o'r seminarau hyn 86 00:04:16,040 --> 00:04:16,899 gallai fod o ddiddordeb. 87 00:04:16,899 --> 00:04:19,730 A bydd pob un ohonynt yn cael ei ffilmio yn Os nad ydych yn gallu 88 00:04:19,730 --> 00:04:21,380 i fod yn bresennol yn bersonol. 89 00:04:21,380 --> 00:04:25,000 Mae'r amserlen yn cael eu cyhoeddi drwy e-bost wrth i ni galedu ystafelloedd. 90 00:04:25,000 --> 00:04:28,460 >> Ac yn olaf, os ydych yn mynd i projects.cs.50.net, mae hwn yn wefan 91 00:04:28,460 --> 00:04:31,450 rydym yn cynnal bob blwyddyn yr ydym yn gwahodd Folks o'r gymuned, cyfadran, 92 00:04:31,450 --> 00:04:36,420 adrannau, staff, ac mae'r ddau mewn y tu allan i CS50 i 93 00:04:36,420 --> 00:04:37,730 cynnig syniadau ar gyfer prosiectau. 94 00:04:37,730 --> 00:04:39,050 Pethau sydd o ddiddordeb i grwpiau myfyrwyr. 95 00:04:39,050 --> 00:04:40,600 Pethau sydd o ddiddordeb i adrannau. 96 00:04:40,600 --> 00:04:43,990 Felly, yn troi yno os ydych yn cael trafferth gydag ansicrwydd o ran yr hyn yr ydych 97 00:04:43,990 --> 00:04:46,700 Byddai eich hun yn hoffi i fynd i'r afael. 98 00:04:46,700 --> 00:04:51,760 >> Felly, y tro diwethaf a gyflwynwyd gennym yn dadlau strwythur data mwy cymhleth nag y byddem 99 00:04:51,760 --> 00:04:53,300 welwyd yn ystod yr wythnosau diwethaf. 100 00:04:53,300 --> 00:04:56,550 Roedden ni wedi bod yn defnyddio araeau 'n bert hapus yn ddefnyddiol os 101 00:04:56,550 --> 00:04:58,160 strwythur data syml. 102 00:04:58,160 --> 00:05:00,570 Yna rydym yn cyflwyno hyn, sy'n wrth gwrs, yn gysylltiedig rhestrau. 103 00:05:00,570 --> 00:05:05,470 A beth oedd yn un o'r cymhellion ar gyfer gyflwyno'r strwythur data? 104 00:05:05,470 --> 00:05:06,930 Yeah? 105 00:05:06,930 --> 00:05:07,250 Beth sy'n bod? 106 00:05:07,250 --> 00:05:08,080 >> GYNULLEIDFA: faint Dynamic. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: faint Dynamic. 108 00:05:09,040 --> 00:05:11,890 Felly, tra yn amrywiaeth, rhaid i chi gwybod beth yw ei faint ymlaen llaw pan 109 00:05:11,890 --> 00:05:12,740 byddwch yn dyrannu ei. 110 00:05:12,740 --> 00:05:14,380 Yn restr cysylltiedig, nad ydych yn rhaid i chi wybod hynny. 111 00:05:14,380 --> 00:05:17,610 Gallwch dim ond malloc, neu'n fwy cyffredinol, dyrannu ychwanegol 112 00:05:17,610 --> 00:05:20,720 nod, fel petai, unrhyw tro y byddwch yn eisiau i fewnosod mwy o ddata. 113 00:05:20,720 --> 00:05:22,670 Ac nod ddim wedi bennwyd ymlaen llaw ystyr. 114 00:05:22,670 --> 00:05:25,580 Dim ond yn derm generig sy'n disgrifio rhyw fath o gynhwysydd ein bod ni'n 115 00:05:25,580 --> 00:05:29,610 defnyddio yn ein strwythur data i storio rhywfaint o eitem o ddiddordeb, sydd yn yr 116 00:05:29,610 --> 00:05:31,750 achos yn digwydd bod yn cyfanrifau. 117 00:05:31,750 --> 00:05:33,160 >> Ond mae tradeoff bob amser. 118 00:05:33,160 --> 00:05:38,070 Felly, rydym yn cael meintiau deinamig y data strwythur, ond yr hyn y pris yr ydym yn talu? 119 00:05:38,070 --> 00:05:40,040 Beth yw'r anfanteision o restrau cysylltiedig? 120 00:05:40,040 --> 00:05:41,006 Yeah? 121 00:05:41,006 --> 00:05:41,980 >> GYNULLEIDFA: Angen mwy o gof. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: Mae angen mwy o cof, sut yn union? 123 00:05:44,240 --> 00:05:46,440 >> GYNULLEIDFA: [Anghlywadwy]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Yn union. 125 00:05:47,050 --> 00:05:50,460 Felly, erbyn hyn rydym wedi awgrymiadau cymryd cof ychwanegol gennym yn flaenorol 126 00:05:50,460 --> 00:05:53,040 nad oedd angen, gan fod y fantais o fyrdd, wrth gwrs, yw bod 127 00:05:53,040 --> 00:05:54,860 popeth yn cydgyffwrdd, yn ôl wrth gefn wrth gefn, sy'n 128 00:05:54,860 --> 00:05:56,380 yn rhoi mynediad ar hap i chi. 129 00:05:56,380 --> 00:06:00,710 Oherwydd dim ond drwy ddefnyddio braced sgwâr nodiant, neu yn fwy technegol pwyntydd 130 00:06:00,710 --> 00:06:03,580 rhifyddeg, adio syml iawn, gallwch gael mynediad i unrhyw 131 00:06:03,580 --> 00:06:05,700 elfennau mewn amser cyson. 132 00:06:05,700 --> 00:06:08,975 Ac yn wir, dyna fath o hinting ar pris arall yr ydym yn talu gyda 133 00:06:08,975 --> 00:06:09,760 restr cysylltiedig. 134 00:06:09,760 --> 00:06:13,890 >> Beth fydd yn digwydd i'r amser yn rhedeg o rhywbeth fel Chwilio, os wyf am 135 00:06:13,890 --> 00:06:17,270 ddod o hyd i werth ac y tu mewn o restr cysylltiedig? 136 00:06:17,270 --> 00:06:20,290 Beth mae fy amser yn rhedeg dod? 137 00:06:20,290 --> 00:06:21,560 O Big n. 138 00:06:21,560 --> 00:06:24,060 Os caiff ei datrys i? 139 00:06:24,060 --> 00:06:25,440 Beth os yw'r strwythur data ei datrys? 140 00:06:25,440 --> 00:06:28,640 A allaf wneud yn well na mawr O n ar gyfer chwilio? 141 00:06:28,640 --> 00:06:31,700 Na, oherwydd yn yr achos gwaethaf y gallai yn dda iawn eu datrys, ond mae nifer 142 00:06:31,700 --> 00:06:32,950 ydych yn chwilio am a allai fod yn fawr. 143 00:06:32,950 --> 00:06:35,370 Gallai fod yn y rhif 100, sy'n allai ddigwydd i fod yn holl 144 00:06:35,370 --> 00:06:36,410 y ffordd ar y diwedd. 145 00:06:36,410 --> 00:06:39,950 Ac oherwydd gallwch gael mynediad at cysylltiedig rhestr yn y gweithredu gan y 146 00:06:39,950 --> 00:06:42,690 ffordd ei nod cyntaf, rydych yn yn dal math o allan o lwc. 147 00:06:42,690 --> 00:06:47,450 Mae'n rhaid i chi deithio ar draws yr holl beth o gyntaf i bara er mwyn dod o hyd i 148 00:06:47,450 --> 00:06:49,150 bod gwerth mawr fel 100. 149 00:06:49,150 --> 00:06:51,350 Neu i benderfynu os yw'n Nid yw hyd yn oed yno. 150 00:06:51,350 --> 00:06:55,960 >> Felly, ni allwn wneud yr hyn algorithm mewn data strwythur sy'n edrych fel hyn? 151 00:06:55,960 --> 00:06:59,460 Ni allwn wneud chwiliad deuaidd, oherwydd chwiliad deuaidd ofynnol ein bod wedi 152 00:06:59,460 --> 00:07:00,740 mynediad ar hap. 153 00:07:00,740 --> 00:07:04,500 Gallai Rydym yn unig neidio o leoliad i leoliad heb orfod dilyn 154 00:07:04,500 --> 00:07:07,080 hyn briwsion bara yn y ffurflen yr holl awgrymiadau hyn. 155 00:07:07,080 --> 00:07:08,300 >> Nawr, sut oedd yn gweithredu'r hyn? 156 00:07:08,300 --> 00:07:12,830 Wel, os ydym yn mynd i'r sgrin yma, os gallwn reimplement data hyn yn gyflym 157 00:07:12,830 --> 00:07:13,440 Strwythur - 158 00:07:13,440 --> 00:07:15,670 Nid yw fy llawysgrifen i gyd y gwych yma, ond byddwn yn ceisio. 159 00:07:15,670 --> 00:07:22,030 Strwythur Felly typedef, a'r hyn a wnes i eisiau i alw y peth hyn i fyny yma? 160 00:07:22,030 --> 00:07:22,960 Nôd. 161 00:07:22,960 --> 00:07:24,580 Felly, byddaf yn cael i ni ddechrau. 162 00:07:24,580 --> 00:07:27,860 Ac yn awr, beth sydd angen i fod tu mewn strwythur y data ar gyfer y unigol 163 00:07:27,860 --> 00:07:28,430 restr cysylltiedig? 164 00:07:28,430 --> 00:07:29,950 Faint o feysydd? 165 00:07:29,950 --> 00:07:30,450 >> Felly ddau. 166 00:07:30,450 --> 00:07:31,570 Mae un yn eithaf hawdd. 167 00:07:31,570 --> 00:07:33,050 Felly int n. 168 00:07:33,050 --> 00:07:35,930 A gallai rydym yn galw n unrhyw beth yr ydym am ei gael, ond dylai fod yn int os ydym yn 169 00:07:35,930 --> 00:07:37,660 gweithredu cysylltiedig ar gyfer rhestr ints. 170 00:07:37,660 --> 00:07:41,920 Ac yn awr beth mae'r ail rhaid i maes i fod? 171 00:07:41,920 --> 00:07:43,460 Strwythur nod *. 172 00:07:43,460 --> 00:07:50,570 Felly, os wyf yn gwneud strwythur nod *, ac yna yr Gellir galw hyn hefyd yn beth bynnag rwyf eisiau, 173 00:07:50,570 --> 00:07:53,510 ond dim ond i fod yn glir 'n annhymerus' galw yn nesaf, fel yr ydym wedi bod yn ei wneud. 174 00:07:53,510 --> 00:07:55,270 Ac yna bydd cau fy braces cyrliog I. 175 00:07:55,270 --> 00:08:00,700 >> Ac yn awr, fel y tro diwethaf, Yr wyf yn rhoi nod i lawr yma. 176 00:08:00,700 --> 00:08:03,830 Ond os wyf yn datgan hyn fel nod, pam wnes i drafferthu fod mor 177 00:08:03,830 --> 00:08:07,320 verbose yma yn datgan strwythur nod * nesaf, yn hytrach na 178 00:08:07,320 --> 00:08:09,210 i ddim ond nod * nesaf? 179 00:08:09,210 --> 00:08:09,904 Yeah? 180 00:08:09,904 --> 00:08:12,810 >> GYNULLEIDFA: [Anghlywadwy]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Yn union. 182 00:08:14,050 --> 00:08:14,530 Yn union. 183 00:08:14,530 --> 00:08:18,320 Oherwydd C wir yn mynd â chi yn llythrennol ac yn Dim ond yn gweld y diffiniad o nod 184 00:08:18,320 --> 00:08:21,230 ffordd i lawr yma, ni allwch cyfeirio at i fyny yma. 185 00:08:21,230 --> 00:08:24,760 Felly, rydym yn cael y math hwn o preemptive datganiad yma, sydd yn cyfaddef 186 00:08:24,760 --> 00:08:25,390 mwy verbose. 187 00:08:25,390 --> 00:08:27,810 Strwythur nod, mae hynny'n golygu gallwn yn awr gael mynediad iddo 188 00:08:27,810 --> 00:08:29,760 tu mewn i'r strwythur data. 189 00:08:29,760 --> 00:08:33,370 >> Ac wrth fynd heibio, gan fod hyn yn dod yn ychydig yn fwy goddrychol yn awr, 190 00:08:33,370 --> 00:08:36,230 Gall y seren dechnegol fynd yma, gall fynd fan hyn, gall 191 00:08:36,230 --> 00:08:37,179 hyd yn oed fynd yn y canol. 192 00:08:37,179 --> 00:08:39,890 Rydym wedi mabwysiadu, yn y canllaw arddull ar gyfer y cwrs, y confensiwn o roi 193 00:08:39,890 --> 00:08:42,299 y seren dde nesaf at y data math, sydd, yn yr achos hwn, 194 00:08:42,299 --> 00:08:43,460 fyddai strwythur nod. 195 00:08:43,460 --> 00:08:46,620 Ond yn sylweddoli mewn llawer o werslyfrau a cyfeiriadau ar-lein, byddwch efallai yn wir 196 00:08:46,620 --> 00:08:48,450 weld ar yr ochr arall. 197 00:08:48,450 --> 00:08:52,200 Ond dim ond yn sylweddoli y bydd y ddau mewn gwirionedd gweithio a dylech yn syml fod 198 00:08:52,200 --> 00:08:52,970 gyson. 199 00:08:52,970 --> 00:08:53,580 >> Mae pob hawl. 200 00:08:53,580 --> 00:08:55,630 Felly dyna oedd ein datganiad o strwythur nod. 201 00:08:55,630 --> 00:08:59,430 Ond yna rydym yn dechrau gwneud mwy pethau soffistigedig. 202 00:08:59,430 --> 00:09:03,410 Er enghraifft, rydym yn penderfynu cyflwyno rhywbeth fel tabl hash. 203 00:09:03,410 --> 00:09:08,160 Felly dyma mae tabl hash o faint n, mynegeio o 0 ar y top chwith i'r n 204 00:09:08,160 --> 00:09:09,690 minws 1 ar y gwaelod ar y chwith. 205 00:09:09,690 --> 00:09:11,640 Gallai hyn fod yn hash bwrdd ar gyfer unrhyw beth. 206 00:09:11,640 --> 00:09:15,340 Ond pa fathau o bethau y gwnaethom siarad am ddefnyddio tabl hash amdano? 207 00:09:15,340 --> 00:09:18,370 Storio beth? 208 00:09:18,370 --> 00:09:18,800 >> Enwau. 209 00:09:18,800 --> 00:09:20,870 Gallem wneud enwau fel rydym yn gwneud y tro diwethaf. 210 00:09:20,870 --> 00:09:22,200 Ac yn wir, gallwch storio unrhyw beth. 211 00:09:22,200 --> 00:09:24,640 A byddwn yn gweld hyn eto yn PHP a JavaScript. 212 00:09:24,640 --> 00:09:28,550 Mae tabl hash yn fath o 'n glws Swistir Cyllell fyddin sy'n eich galluogi i storio 213 00:09:28,550 --> 00:09:33,690 'n bert lawer beth bynnag yr ydych ei eisiau tu mewn iddo gan gysylltu allweddi gyda gwerthoedd. 214 00:09:33,690 --> 00:09:34,770 Allweddi â gwerthoedd. 215 00:09:34,770 --> 00:09:37,800 >> Nawr yn yr achos syml, mae ein allweddi rhifau yn unig. 216 00:09:37,800 --> 00:09:40,380 Rydym yn gweithredu hash bwrdd fel arae. 217 00:09:40,380 --> 00:09:43,500 Ac felly yr allweddi yn 0, 1, 2, ac yn y blaen. 218 00:09:43,500 --> 00:09:47,200 Ac felly yr ydym ni, fel bodau dynol, penderfynodd ddiwethaf eich wythnos bod yn gwybod beth, os ydym yn 219 00:09:47,200 --> 00:09:50,410 mynd i enwau storio, gadewch i ni yn unig fympwyol, ond 'n bert yn rhesymol, 220 00:09:50,410 --> 00:09:54,680 cymryd yn ganiataol bod Alice, A enw, fydd yn unig yn cael ei fynegeio i 0. 221 00:09:54,680 --> 00:09:58,030 A bydd Bob, enw B, yn cael ei fynegeio yn 1, ac yn y blaen. 222 00:09:58,030 --> 00:10:02,490 Felly cawsom mapio rhwng mewnbynnau, sydd yn llinynnau, ac mae'r hash 223 00:10:02,490 --> 00:10:04,560 lleoliadau, sef rhifau. 224 00:10:04,560 --> 00:10:07,740 >> Felly, y broses sy'n cael ei adnabod yn gyffredinol fel swyddogaeth hash, a gallwch wirioneddol 225 00:10:07,740 --> 00:10:09,130 gweithredu mewn cod. 226 00:10:09,130 --> 00:10:12,080 Os wyf yn awyddus i weithredu swyddogaeth hash sy'n gwneud yn union yr hyn yr ydym 227 00:10:12,080 --> 00:10:17,070 a ddisgrifir yn unig o tro diwethaf, efallai y byddaf datgan swyddogaeth sy'n digwydd, fel y 228 00:10:17,070 --> 00:10:18,330 mewnbwn er enghraifft - 229 00:10:18,330 --> 00:10:22,190 a gadewch i ni wneud hyn ar hyn sgrin dros yma. 230 00:10:22,190 --> 00:10:26,180 Os wyf yn awyddus i weithredu hash swyddogaeth, efallai y byddwn yn dweud 231 00:10:26,180 --> 00:10:27,410 rhywbeth fel hyn. 232 00:10:27,410 --> 00:10:29,030 >> Mae'n mynd i ddychwelyd int. 233 00:10:29,030 --> 00:10:33,600 Mae'n mynd i gael ei alw hash, ac mae'n mynd i dderbyn fel dadl yn 234 00:10:33,600 --> 00:10:38,920 llinyn, neu gallwn fod yn fwy priodol yn awr, a dweud torgoch *, byddwn yn ei alw'n s. 235 00:10:38,920 --> 00:10:43,840 Ac yna yr holl swyddogaeth hon wedi ei wneud, yn y pen draw, yn cael ei dychwelyd int. 236 00:10:43,840 --> 00:10:45,990 Nawr, sut y mae'n ei wneud a allai â bod mor glir. 237 00:10:45,990 --> 00:10:49,510 Rydw i'n mynd i roi hyn ar waith heb unrhyw fath o gamgymeriad gwirio ar hyn o bryd. 238 00:10:49,510 --> 00:10:55,740 Im 'jyst yn mynd i ddweud ddall, yn dychwelyd beth bynnag sydd yn s braced 0, minws, 239 00:10:55,740 --> 00:10:58,850 gadewch i ni ddweud, cyfalaf A colon. 240 00:10:58,850 --> 00:10:59,960 >> Torri yn llwyr. 241 00:10:59,960 --> 00:11:02,620 Dyw hi ddim yn berffaith, oherwydd un, beth os yw null? 242 00:11:02,620 --> 00:11:04,000 Pethau drwg yn mynd i ddigwydd. 243 00:11:04,000 --> 00:11:07,940 Dau, beth os y llythyr cyntaf yn y Nid enw yw llythyr cyfalaf? 244 00:11:07,940 --> 00:11:09,860 Dyw hynny ddim yn mynd i droi allan yn dda naill ai. 245 00:11:09,860 --> 00:11:11,970 Gallai fod yn llythyr llythrennau bach neu beidio llythyr o gwbl. 246 00:11:11,970 --> 00:11:15,520 Felly gwbl lle i wella yma, ond mae hyn yn syniad sylfaenol. 247 00:11:15,520 --> 00:11:19,010 >> Beth rydym yn disgrifio yr wythnos diwethaf ar lafar fel dim ond proses o fapio Alice i 248 00:11:19,010 --> 00:11:23,360 Gall 0 a Bob i 1 gael eu mynegi yn sicr yn fwy formulaically fel C 249 00:11:23,360 --> 00:11:24,320 gweithredu yma. 250 00:11:24,320 --> 00:11:28,630 A elwir eto hash, yn cymryd llinyn fel mewnbwn, ac yna rhywsut yn gwneud rhywbeth 251 00:11:28,630 --> 00:11:31,020 gyda'r mewnbwn i gynhyrchu allbwn. 252 00:11:31,020 --> 00:11:34,130 Nid annhebyg ein disgrifiad blwch du ein bod wedi ei wneud o hyd. 253 00:11:34,130 --> 00:11:36,550 Nid wyf yn gwybod sut y gallai hyn fod yn gweithio o dan y cwfl. 254 00:11:36,550 --> 00:11:40,120 >> Ar gyfer problem set 6, un o'r heriau Chi sydd i benderfynu beth 255 00:11:40,120 --> 00:11:41,920 Bydd eich swyddogaeth hash fod? 256 00:11:41,920 --> 00:11:45,760 Beth sy'n mynd i fod yn y tu mewn y du bocs, ac yn ôl pob tebyg, mae'n bydd yn 257 00:11:45,760 --> 00:11:50,380 ychydig yn fwy diddorol na hyn, a bendant yn fwy agored i gamgymeriadau 258 00:11:50,380 --> 00:11:53,180 gwirio na hyn penodol gweithredu. 259 00:11:53,180 --> 00:11:54,580 >> Ond gall problemau godi, dde? 260 00:11:54,580 --> 00:11:57,760 Os oes gennym strwythur data fel hyn un, beth un o'r problemau 261 00:11:57,760 --> 00:12:01,600 gallwch rhedeg i mewn dros gyfnod o amser wrth i chi fewnosod mwy a mwy o enwau i mewn i'r 262 00:12:01,600 --> 00:12:02,880 tabl hash? 263 00:12:02,880 --> 00:12:04,630 Byddwch yn cael gwrthdrawiadau, dde? 264 00:12:04,630 --> 00:12:07,560 Beth os oes gennych Alice ac Aaron, dau o bobl y mae eu henwau yn digwydd 265 00:12:07,560 --> 00:12:08,190 i ddechrau gyda A? 266 00:12:08,190 --> 00:12:11,660 Mae hynny'n codi'r cwestiwn, lle rydych yn rhoi'r ail fath Mae enw? 267 00:12:11,660 --> 00:12:15,050 >> Wel, efallai y byddwch yn ddiniwed yn unig ei roi lle mae Bob yn perthyn, ond yna Bob yn 268 00:12:15,050 --> 00:12:17,300 math o sgriwio os ydych yn ceisio rhowch ei enw nesaf ac 269 00:12:17,300 --> 00:12:18,240 does dim lle ar ei gyfer. 270 00:12:18,240 --> 00:12:21,400 Felly efallai y byddwch yn rhoi Bob lle Charlie yw, a gallwch ddychmygu hyn yn gyflym iawn 271 00:12:21,400 --> 00:12:23,020 datganoli i mewn i dipyn o lanast. 272 00:12:23,020 --> 00:12:25,600 Rhywbeth llinol yn y diwedd, lle rydych yn yn rhaid i chwilio'r holl beth 273 00:12:25,600 --> 00:12:28,190 chwilio am Alice neu Bob neu Aaron neu Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Felly, yn lle hynny rydym yn cynnig, yn hytrach na dim ond llinol holi am fannau agored 275 00:12:33,230 --> 00:12:36,450 a plopping enwau yno, rydym yn cynnig dull ffansi. 276 00:12:36,450 --> 00:12:41,740 Mae tabl hash gweithredu'n dal i fod gyda amrywiaeth o fynegeion, ond y math data o 277 00:12:41,740 --> 00:12:44,500 mynegeion hynny yn awr yn awgrymiadau. 278 00:12:44,500 --> 00:12:47,360 Awgrymiadau ar gyfer beth? 279 00:12:47,360 --> 00:12:48,730 Pointers i restrau cysylltiedig. 280 00:12:48,730 --> 00:12:53,330 >> Gan fod galw i gof bod rhestr cysylltiedig yn gwirionedd dim ond pwyntydd i nod, a 281 00:12:53,330 --> 00:12:57,110 y nod Mae cae nesaf, a bod y nod Mae cae nesaf, ac yn y blaen. 282 00:12:57,110 --> 00:13:00,690 Felly, gallwch yn awr feddwl am amrywiaeth hwn ar yr ochr chwith tabl hash fel 283 00:13:00,690 --> 00:13:01,820 gan arwain at restr cysylltiedig. 284 00:13:01,820 --> 00:13:07,000 Y fantais o'r rhain yw os ydych yn cael gwrthdrawiad rhwng Alice ac Aaron, 285 00:13:07,000 --> 00:13:09,300 beth ydych chi'n ei wneud gyda'r ail berson o'r fath? 286 00:13:09,300 --> 00:13:14,150 Rydych yn unig atodi iddo ef neu hi i'r ben, neu hyd yn oed y dechrau 287 00:13:14,150 --> 00:13:15,490 ar y rhestr honno cysylltiedig. 288 00:13:15,490 --> 00:13:17,340 >> Ac mewn gwirionedd, dim ond gadewch i nwdls drwy hynny am ddim ond eiliad. 289 00:13:17,340 --> 00:13:18,640 Lle fyddai'n gwneud yr ystyr mwyaf? 290 00:13:18,640 --> 00:13:22,060 Os byddaf yn gosod Alice ac mae hi'n dod i ben i fyny ar y lleoliad cyntaf, yna yr wyf yn ceisio 291 00:13:22,060 --> 00:13:25,310 nodwch enw Aaron, ac mae amlwg yn gwrthdrawiad, dylwn i roi 292 00:13:25,310 --> 00:13:27,400 ef ar y dechrau y rhestr cysylltiedig? 293 00:13:27,400 --> 00:13:30,944 Dyna yn y lleoliad hwnnw yn gyntaf, neu ar y diwedd? 294 00:13:30,944 --> 00:13:31,440 >> GYNULLEIDFA: [Anghlywadwy]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Clywais dechrau. 297 00:13:32,490 --> 00:13:33,903 Pam ar y dechrau? 298 00:13:33,903 --> 00:13:34,750 >> GYNULLEIDFA: [Anghlywadwy]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Mae'n wyddor, felly dyna 'n glws. 301 00:13:36,520 --> 00:13:37,330 Dyna eiddo da. 302 00:13:37,330 --> 00:13:39,335 Bydd yn arbed amser o bosibl i mi. 303 00:13:39,335 --> 00:13:43,290 Ni fydd yn gadael i mi wneud chwiliad deuaidd, ond yr wyf yn gallai o leiaf fod yn gallu torri allan 304 00:13:43,290 --> 00:13:47,340 o dolen os wyf yn sylweddoli, yn dda, rwy'n ffordd Byddai gorffennol yn Aaron fod yn y 305 00:13:47,340 --> 00:13:48,310 datrys rhestr gysylltiedig. 306 00:13:48,310 --> 00:13:50,360 Nid oes yn rhaid i mi gwastraffu fy amser yn edrych yr holl ffordd at y diwedd. 307 00:13:50,360 --> 00:13:51,530 Felly, mae hynny'n rhesymol. 308 00:13:51,530 --> 00:13:54,710 Pam arall efallai y byddwch am i fewnosod yr enw gwrthdaro yn y 309 00:13:54,710 --> 00:13:56,660 ddechrau y rhestr? 310 00:13:56,660 --> 00:13:57,397 Beth sy'n bod? 311 00:13:57,397 --> 00:13:58,680 >> GYNULLEIDFA: [Anghlywadwy]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Gallai gymryd amser hir i gyrraedd y diwedd y rhestr. 313 00:14:00,820 --> 00:14:02,490 Ac yn wir, yn hirach ac yn hirach. 314 00:14:02,490 --> 00:14:04,920 Mae mwy o enwau i chi fewnosod y dechrau gyda A, po hwyaf y bydd 315 00:14:04,920 --> 00:14:06,280 gadwyn yn mynd i gael. 316 00:14:06,280 --> 00:14:07,890 Po hiraf a oedd yn cysylltu rhestr yn mynd i gael. 317 00:14:07,890 --> 00:14:09,420 Felly, rydych yn wirioneddol yn unig gwastraffu eich amser. 318 00:14:09,420 --> 00:14:14,070 Efallai eich bod yn well eich byd cynnal amser gosod yn gyson, mawr O o 1, 319 00:14:14,070 --> 00:14:18,470 gan bob amser roi'r enw gwrthdaro yn ddechrau'r rhestr cysylltiedig, 320 00:14:18,470 --> 00:14:21,230 ac nid yn poeni cymaint am didoli. 321 00:14:21,230 --> 00:14:22,600 >> Beth yw'r ateb gorau? 322 00:14:22,600 --> 00:14:23,320 Mae'n aneglur. 323 00:14:23,320 --> 00:14:26,140 Mae'n fath o yn dibynnu ar yr hyn y mae'r dosbarthiad yw, beth yw'r patrwm 324 00:14:26,140 --> 00:14:27,850 o'r enwau rydych yn mewnosod. 325 00:14:27,850 --> 00:14:29,430 Dyw hi ddim o reidrwydd yn ateb amlwg. 326 00:14:29,430 --> 00:14:33,100 Ond yma, unwaith eto, yn cyfle dylunio. 327 00:14:33,100 --> 00:14:37,220 >> Felly, byddwn wedyn yn edrych ar y peth hyn, a mewn gwirionedd y cyfle mawr eraill 328 00:14:37,220 --> 00:14:38,180 ar gyfer p-set 6. 329 00:14:38,180 --> 00:14:41,770 Ac yn sylweddoli, os nad ydych wedi gwneud hynny'n barod, Zamyla deifio i ddau o'r rhain, hash 330 00:14:41,770 --> 00:14:43,260 tablau a chais, yn fwy manwl. 331 00:14:43,260 --> 00:14:45,630 Ac mae'r walkthrough fideo gwreiddio yn p-set fanyleb. 332 00:14:45,630 --> 00:14:46,590 Roedd hyn yn trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. A beth oedd yn ddiddorol am hyn oedd bod yr amser yn rhedeg 334 00:14:51,670 --> 00:14:59,510 o chwilio am enw, fel Maxwell y tro diwethaf, roedd mawr O o beth? 335 00:14:59,510 --> 00:15:01,040 Beth sy'n bod? 336 00:15:01,040 --> 00:15:01,920 >> GYNULLEIDFA: Mae nifer o lythyrau. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Nifer y llythyrau. 338 00:15:02,550 --> 00:15:03,210 Clywais ddau beth. 339 00:15:03,210 --> 00:15:04,630 Nifer o lythyrau ac amser cyson. 340 00:15:04,630 --> 00:15:05,540 Felly, gadewch i ni fynd â hynny yn gyntaf. 341 00:15:05,540 --> 00:15:06,410 Mae nifer o lythyrau. 342 00:15:06,410 --> 00:15:10,195 Wel, y strwythur data, galw i gof, yn fel coeden, coeden deulu, pob un 343 00:15:10,195 --> 00:15:12,860 y mae eu nodau wedi eu gwneud o araeau. 344 00:15:12,860 --> 00:15:16,300 A rhesi hynny yn arwydd o nodau eraill o'r fath, neu unrhyw eraill 345 00:15:16,300 --> 00:15:17,670 araeau yn y goeden. 346 00:15:17,670 --> 00:15:22,890 >> Felly, os oeddem am benderfynu wedyn boed Maxwell yn i mewn yma, efallai y byddwn yn mynd 347 00:15:22,890 --> 00:15:26,890 at y casgliad cyntaf, ar frig y y goeden, y gwraidd fel y'i gelwir, ben 348 00:15:26,890 --> 00:15:30,521 y trie, ac yna dilyn y m pwyntydd, yna bydd y pwyntydd yn, yna x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Ac yna pan fyddaf yn gweld rhai symbol arbennig, dynodi yma fel triongl. 351 00:15:34,910 --> 00:15:38,480 Mewn cod fe welwch rydym yn cynnig eich bod gweithredu fel bool, dim ond dweud ie 352 00:15:38,480 --> 00:15:40,540 neu ddim, gair yn dod i ben yma. 353 00:15:40,540 --> 00:15:45,270 >> Wel, unwaith y byddwn wedi mynd i M-A-X-W-E-L-L, teimlo fel saith, efallai 354 00:15:45,270 --> 00:15:48,910 wyth os ydym yn mynd un heibio iddo, wyth camau i ddod o hyd i Maxwell. 355 00:15:48,910 --> 00:15:53,050 Neu beth am alw K. Ond cofio ddiwethaf amser, yr wyf yn dadlau, os oes 356 00:15:53,050 --> 00:15:57,540 realistig o hyd ar y mwyaf ar gair, fel cymeriadau 40-rhai-od, a 357 00:15:57,540 --> 00:16:00,810 uchafswm hyd awgrymu gwerth cyson. 358 00:16:00,810 --> 00:16:05,770 Felly mewn gwirionedd, ie, 'i' O dechnegol fawr o 8 neu 7, neu O fawr iawn o K. Ond 359 00:16:05,770 --> 00:16:09,420 os oes cap cyfyngedig ar yr hyn Gallai K fod, mae'n gyson. 360 00:16:09,420 --> 00:16:12,080 Ac felly mae'n fawr O 1 yn ar ddiwedd y dydd. 361 00:16:12,080 --> 00:16:13,040 >> Nid yn y byd go iawn. 362 00:16:13,040 --> 00:16:15,960 Nid pan fyddwch mewn gwirionedd yn dechrau gwylio eich cloc yn rhedeg eich rhaglen. 363 00:16:15,960 --> 00:16:20,690 Mae'n gwbl yn mynd i fod ychydig yn arafach nag wirioneddol gyson 364 00:16:20,690 --> 00:16:21,840 amser gydag un cam. 365 00:16:21,840 --> 00:16:25,540 Mae'n mynd i fod yn saith neu wyth cam, ond yn dal i fod yn llawer, llawer gwell 366 00:16:25,540 --> 00:16:30,080 na algorithm fel mawr O n bod yn dibynnu ar faint yr hyn sydd yn y 367 00:16:30,080 --> 00:16:31,220 strwythur data. 368 00:16:31,220 --> 00:16:34,970 >> Sylwch ar y upside yma yw y gallwn osod miliwn mwy o enwau i mewn i hyn 369 00:16:34,970 --> 00:16:38,170 strwythur data, ond faint yn fwy o gamau mae'n mynd i fynd â ni i ddod o hyd i 370 00:16:38,170 --> 00:16:40,480 Maxwell yn yr achos? 371 00:16:40,480 --> 00:16:40,780 Dim. 372 00:16:40,780 --> 00:16:41,820 Mae'n effeithio. 373 00:16:41,820 --> 00:16:45,480 A hyd yma, nid wyf yn credu ein bod wedi gweld enghraifft o strwythur data neu 374 00:16:45,480 --> 00:16:48,560 algorithm a oedd yn gwbl heffeithio gan allanol 375 00:16:48,560 --> 00:16:50,040 ymddygiadau fel 'na. 376 00:16:50,040 --> 00:16:51,160 Ond ni all hyn fod yn anhygoel. 377 00:16:51,160 --> 00:16:52,900 Ni all hyn fod yr unig ateb ar gyfer y p-set 378 00:16:52,900 --> 00:16:53,570 >> Ac nid yw'n. 379 00:16:53,570 --> 00:16:55,980 Nid yw hyn o reidrwydd y data strwythur dylech tueddu i, 380 00:16:55,980 --> 00:16:58,220 oherwydd fel tablau hash, tradeoff. 381 00:16:58,220 --> 00:17:00,500 Beth yw'r pris a dalwch yma? 382 00:17:00,500 --> 00:17:00,940 Cof. 383 00:17:00,940 --> 00:17:02,890 Yr wyf yn golygu, mae hyn yn erchyll faint o gof. 384 00:17:02,890 --> 00:17:05,569 Ac ni allwch eithaf ei weld yma oherwydd awdur y darlun hwn 385 00:17:05,569 --> 00:17:09,420 amlwg cwtogi holl arrays, ac nid ydym yn gweld llawer o A a 386 00:17:09,420 --> 00:17:12,700 B a C a Q ac Y. a Z yn araeau hyn. 387 00:17:12,700 --> 00:17:13,630 Ond maen nhw yno. 388 00:17:13,630 --> 00:17:17,660 >> Mae pob un o'r nodau hyn yw amrywiaeth cyfan o ryw 26 neu fwy o bytes, pob un 389 00:17:17,660 --> 00:17:19,170 sy'n cynrychioli llythyr. 390 00:17:19,170 --> 00:17:22,920 27 yn ein hachos ni, fel y gallwn gefnogi collnod yn y broblem a osodwyd. 391 00:17:22,920 --> 00:17:27,030 Felly, y strwythur data yn wirioneddol, iawn trwchus a llydan. 392 00:17:27,030 --> 00:17:30,880 Ac y gallai ei ben ei hun yn y pen draw arafu pethau i lawr, neu o leiaf gostio i chi 393 00:17:30,880 --> 00:17:32,240 llawer mwy o le. 394 00:17:32,240 --> 00:17:34,020 Ond unwaith eto, gallwn dynnu cymariaethau yma. 395 00:17:34,020 --> 00:17:39,190 >> Dwyn i gof ychydig yn ôl, rydym yn cyflawni llawer amser yn rhedeg yn fwy cyffrous i ddatrys 396 00:17:39,190 --> 00:17:42,880 pan fyddwn yn defnyddio uno fath, ond mae'r pris rydym yn talu i gyflawni n mewngofnodi n ar gyfer uno 397 00:17:42,880 --> 00:17:46,930 math sy'n ofynnol ein bod yn gwario mwy pa adnoddau? 398 00:17:46,930 --> 00:17:47,690 Mwy o le. 399 00:17:47,690 --> 00:17:50,530 Rydym angen amrywiaeth uwchradd i copïo pobl i mewn, yn union fel 400 00:17:50,530 --> 00:17:51,620 wnaethom yma ar y llwyfan. 401 00:17:51,620 --> 00:17:55,880 Felly, unwaith eto, nid oes unrhyw enillwyr clir, ond dim ond dylunio goddrychol 402 00:17:55,880 --> 00:17:57,710 i benderfyniadau gael eu gwneud. 403 00:17:57,710 --> 00:17:58,060 >> Mae pob hawl. 404 00:17:58,060 --> 00:17:59,130 Felly beth am hyn? 405 00:17:59,130 --> 00:18:02,050 Gall unrhyw un adnabod pa D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Felly tri ohonom yn ei wneud. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Felly mae hyn yn ar gyfer bwyta Mather yn. 410 00:18:05,070 --> 00:18:09,650 'N annhymerus' bet holl neuaddau bwyta wedi pentyrrau o hambyrddau fel hyn. 411 00:18:09,650 --> 00:18:11,950 Ac mae hyn mewn gwirionedd yn cynrychioli o rywbeth rydym wedi 412 00:18:11,950 --> 00:18:13,050 yn amlwg yn gweld yn barod. 413 00:18:13,050 --> 00:18:14,850 Byddem ni'n ei alw yn llythrennol pentwr. 414 00:18:14,850 --> 00:18:18,970 Ac y simnai, o ran eich cof cyfrifiadur, yw lle mae data yn mynd 415 00:18:18,970 --> 00:18:20,460 tra bod swyddogaethau yn cael eu galw. 416 00:18:20,460 --> 00:18:23,410 >> Er enghraifft, pa fathau o bethau yn mynd ar y pentwr o ran y 417 00:18:23,410 --> 00:18:27,420 cynllun cof rydym wedi trafod yn yr wythnosau diwethaf? 418 00:18:27,420 --> 00:18:28,736 Beth sy'n bod? 419 00:18:28,736 --> 00:18:29,670 >> GYNULLEIDFA: galwadau i swyddogaethau. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Mae'n ddrwg gen i. 421 00:18:30,260 --> 00:18:31,210 >> GYNULLEIDFA: galwadau i swyddogaethau. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: galwadau i swyddogaethau, ond yn benodol, beth sydd y tu mewn o bob un o'r 423 00:18:33,590 --> 00:18:35,340 fframiau hynny? 424 00:18:35,340 --> 00:18:37,220 Pa fath o bethau? 425 00:18:37,220 --> 00:18:37,460 Yeah. 426 00:18:37,460 --> 00:18:38,500 Felly newidynnau lleol. 427 00:18:38,500 --> 00:18:43,080 Anytime rydym angen rhywfaint o storio lleol, fel dadl, neu int I, neu int 428 00:18:43,080 --> 00:18:45,940 dros dro, neu beth bynnag y leol amrywiol yw, rydym wedi bod yn 429 00:18:45,940 --> 00:18:47,210 rhoi hwnnw ar y pentwr. 430 00:18:47,210 --> 00:18:49,610 Ac rydym yn galw ei fod yn pentwr oherwydd o'r syniad haenu. 431 00:18:49,610 --> 00:18:52,940 Dim ond math o gemau i fyny â realiti, y cysyniad ohono. 432 00:18:52,940 --> 00:18:56,650 >> Ond mae'n troi allan y gall pentwr hefyd ei weld fel strwythur data, mae 433 00:18:56,650 --> 00:19:00,110 amgen i amrywiaeth, dewis arall i restr cysylltiedig. 434 00:19:00,110 --> 00:19:02,770 Rhywbeth gysyniadol yn fwy diddorol y gall pethau fod 435 00:19:02,770 --> 00:19:06,030 gweithredu gan ddefnyddio naill neu'r llall o'r bethau, ond mae'n fath gwahanol o 436 00:19:06,030 --> 00:19:09,140 strwythur data ategol, mewn gwirionedd, dim ond dau gweithrediadau. 437 00:19:09,140 --> 00:19:11,000 Ond gallwch ychwanegu ffansi nodweddion na'r rhai hyn. 438 00:19:11,000 --> 00:19:12,180 Ond mae'r rhain yn y pethau sylfaenol - 439 00:19:12,180 --> 00:19:13,510 gwthio a pop. 440 00:19:13,510 --> 00:19:19,240 >> Ac mae'r syniad gyda stac yw os wyf yn gennym yma, gyda neu heb Annenberg 441 00:19:19,240 --> 00:19:22,880 gwybod, hambwrdd o ddrws nesaf gyda'r rhif 9 arno. 442 00:19:22,880 --> 00:19:23,870 Felly, dim ond int. 443 00:19:23,870 --> 00:19:26,990 Ac yr wyf yn awyddus i wthio hyn ar y data strwythur, sydd ar hyn o bryd yn wag. 444 00:19:26,990 --> 00:19:28,790 Ystyriwch hyn ar waelod y pentwr. 445 00:19:28,790 --> 00:19:33,150 Byddwn yn gwthio nifer hwn 9 ar y stacio, ac yn awr ei fod yn iawn yno. 446 00:19:33,150 --> 00:19:36,040 >> Ond y peth diddorol am pentwr yw os wyf yn awr am wthio 447 00:19:36,040 --> 00:19:40,210 rhywfaint o werth arall, fel 17, ac yr wyf yn gwthio hyn ar y pentwr, dw i'n mynd i wneud 448 00:19:40,210 --> 00:19:43,290 yr unig beth 'n athrylithgar, Im' jyst yn mynd i unioni'r sefyllfa lle rydym yn bodau dynol 449 00:19:43,290 --> 00:19:45,180 yn cael eu tueddu i roi, ar ei ben. 450 00:19:45,180 --> 00:19:48,850 Ond yr hyn sy'n ddiddorol yn awr yw, sut ydw i'n gael o 9? 451 00:19:48,850 --> 00:19:50,670 Rydych yn gwybod, nid wyf yn ei wneud heb rhywfaint o ymdrech. 452 00:19:50,670 --> 00:19:54,070 >> Felly, yr hyn sy'n ddiddorol am pentwr yw y dylunio, 453 00:19:54,070 --> 00:19:56,330 mae'n strwythur data LIFO. 454 00:19:56,330 --> 00:19:59,680 Silly ffordd o ddisgrifio olaf i mewn, cyntaf allan. 455 00:19:59,680 --> 00:20:03,280 Felly, y rhif olaf yn ar hyn o bryd oedd 17. 456 00:20:03,280 --> 00:20:07,540 Felly, os wyf am i pop rhywbeth oddi ar o'r pentwr, gall dim ond 17. 457 00:20:07,540 --> 00:20:11,890 Felly mae yna orchymyn mandadol gweithrediadau yma, lle yr eitem olaf 458 00:20:11,890 --> 00:20:14,260 yn rhaid iddo fod yn yr un cyntaf allan. 459 00:20:14,260 --> 00:20:16,440 Felly, mae'r acronym, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Felly, pam y gallai hyn fod yn ddefnyddiol? 461 00:20:19,160 --> 00:20:22,690 A yw eu cyd-destunau lle byddech eisiau strwythur data fel hyn? 462 00:20:22,690 --> 00:20:24,810 Wel, mae wedi bod yn ddefnyddiol yn sicr tu mewn i gyfrifiadur. 463 00:20:24,810 --> 00:20:29,050 Felly systemau gweithredu ddefnyddio hyn yn glir math o strwythur data ar gyfer staciau. 464 00:20:29,050 --> 00:20:32,800 Byddwn hefyd yn gweld yr un syniad pan ddaw i dudalennau gwe. 465 00:20:32,800 --> 00:20:35,890 Felly, yr wythnos hon a'r wythnos nesaf a thu hwnt, ac wrth i chi ddechrau gweithredu ar y we 466 00:20:35,890 --> 00:20:39,490 tudalennau mewn iaith o'r enw HTML, gallwch mewn gwirionedd yn defnyddio strwythur data fel 467 00:20:39,490 --> 00:20:42,690 hwn i benderfynu a yw'r dudalen wedi'i fformadu'n gywir. 468 00:20:42,690 --> 00:20:47,170 Oherwydd byddwn yn gweld yr holl dudalennau gwe yn dilyn rhyw fath o hierarchaeth, yn bant 469 00:20:47,170 --> 00:20:52,030 a fydd, ar ddiwedd y dydd, fod yn strwythur coeden o dan y cwfl. 470 00:20:52,030 --> 00:20:53,620 Felly mwy am hynny mewn dim ond ychydig. 471 00:20:53,620 --> 00:20:56,560 >> Ond am y tro, gadewch i ni yn cynnig am hyn o bryd, sut y gallem fynd ati i 472 00:20:56,560 --> 00:20:58,830 gynrychioli beth yw pentwr yw? 473 00:20:58,830 --> 00:21:03,370 Gadewch i mi cynnig ein bod yn gweithredu stac â'r cod fel hyn. 474 00:21:03,370 --> 00:21:07,990 Felly pentwr yn mynd i gael y tu mewn ohono ddau beth, amrywiaeth, a elwir yn hambyrddau, 475 00:21:07,990 --> 00:21:09,510 dim ond i fod yn gyson â'r demo. 476 00:21:09,510 --> 00:21:12,660 A phob un o'r eitemau yn y casgliad yn mynd i fod yn int fath. 477 00:21:12,660 --> 00:21:14,740 A gallu yn ôl pob tebyg beth? 478 00:21:14,740 --> 00:21:18,796 Gan nad wyf wedi ysgrifennu y diffiniad llawn yma. 479 00:21:18,796 --> 00:21:21,535 >> Mae'n debyg mai dyma'r mwyaf maint y rhesi. 480 00:21:21,535 --> 00:21:25,150 Ac mae'n debyg datgan fel miniog diffinio ar ben y ffeil, rhai 481 00:21:25,150 --> 00:21:28,450 math o gyson fel yr awgrymir gan y cyfalafu yn unig. 482 00:21:28,450 --> 00:21:32,250 Felly rhywle gallu ei ddiffinio fel y maint mwyaf posibl. 483 00:21:32,250 --> 00:21:35,590 Yn y cyfamser, y tu mewn i'r strwythur data a elwir yn pentwr bydd yna 484 00:21:35,590 --> 00:21:38,630 fod yn gyfanrif hysbys yn unig syml fel maint. 485 00:21:38,630 --> 00:21:43,400 >> Felly, pe bawn i gynrychioli'r hyn yn awr lluniau, gadewch i ni dybio bod hyn yn 486 00:21:43,400 --> 00:21:48,070 blwch du cyfan yn cynrychioli fy pentwr. 487 00:21:48,070 --> 00:21:50,070 Tu mewn iddo yw dau newidyn. 488 00:21:50,070 --> 00:21:54,780 Felly, yr wyf i'n mynd i dynnu un cyntaf fel maint. 489 00:21:54,780 --> 00:21:57,420 A'r ail un yr wyf i'n mynd i dynnu fel arae. 490 00:21:57,420 --> 00:22:01,060 >> Ond dim ond er mwyn cadw pethau'n drefnus, Fel arfer, byddwn yn tynnu amrywiaeth fel 491 00:22:01,060 --> 00:22:04,910 hyn, ond ei fod yn fath o 'n glws os ydym yn cyd-fynd â realiti, neu 492 00:22:04,910 --> 00:22:06,230 cyd-fynd â'r model meddwl. 493 00:22:06,230 --> 00:22:12,880 Felly, gadewch i mi yn lle tynnu amrywiaeth fertigol, sydd ychydig, unwaith eto, 494 00:22:12,880 --> 00:22:13,840 rendition artist. 495 00:22:13,840 --> 00:22:16,610 Nid yw'n wir bwys yr hyn y mae'n yw o dan y cwfl. 496 00:22:16,610 --> 00:22:20,350 A byddwn yn dweud bod, yn ddiofyn, gallu yn mynd i fod yn dri. 497 00:22:20,350 --> 00:22:23,480 Felly, bydd hyn yn lleoliad 0, mae hyn yn Bydd yn lleoliad 1, mae hyn yn 498 00:22:23,480 --> 00:22:25,740 Bydd yn lleoliad 2. 499 00:22:25,740 --> 00:22:29,330 >> Os byddaf yn llwgrwobrwyo gyda phêl straen, byddai rhywun yn hoffi i ddod i fyny ac yn rhedeg y 500 00:22:29,330 --> 00:22:30,870 bwrdd yma am ddim ond hyn o bryd? 501 00:22:30,870 --> 00:22:31,960 OK, gwelodd eich llaw yn gyntaf. 502 00:22:31,960 --> 00:22:33,950 Dewch ar i fyny. 503 00:22:33,950 --> 00:22:36,500 Mae pob hawl. 504 00:22:36,500 --> 00:22:38,760 Felly yr wyf yn credu ei fod yn Steven. 505 00:22:38,760 --> 00:22:40,035 Dewch ar i fyny. 506 00:22:40,035 --> 00:22:40,770 Mae pob hawl. 507 00:22:40,770 --> 00:22:46,760 >> Ond Tybiwch nawr rydym ailddirwyn i'r gychwynnol cyflwr y byd lle rwyf 508 00:22:46,760 --> 00:22:52,180 newydd datgan pentwr, ac mae'n yn mynd i fod o gapasiti tri. 509 00:22:52,180 --> 00:22:54,470 Ond nid yw maint wedi ei benderfynu eto. 510 00:22:54,470 --> 00:22:56,100 Nid yw hambyrddau wedi ei benderfynu eto. 511 00:22:56,100 --> 00:22:57,300 Felly, ychydig o gwestiynau yn gyntaf. 512 00:22:57,300 --> 00:23:01,310 A gadewch i mi yn rhoi meic i chi fel y gallwch cymryd rhan fwy gweithredol yn hyn. 513 00:23:01,310 --> 00:23:05,190 >> Felly, beth sydd y tu mewn o faint ar hyn o bryd mewn pryd os bydd yr holl wyf wedi ei wneud yw 514 00:23:05,190 --> 00:23:09,340 datgan stac gyda un llinell o god? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Dim llawer. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, dim llawer. 517 00:23:12,080 --> 00:23:14,410 A ydym yn gwybod beth sydd y tu mewn maint, ydym yn gwybod beth sydd y tu mewn 518 00:23:14,410 --> 00:23:16,330 y casgliad yma? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Dim ond cod ar hap, dde? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Yeah, yr wyf i'n mynd i alw cod, ond ar hap - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Pethau. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Pethau fel hap 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: darnau. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: darnau, dde? 526 00:23:29,530 --> 00:23:31,190 Felly gwerthoedd garbage, dde? 527 00:23:31,190 --> 00:23:33,470 Felly gyfnewidiadau o 0 ac 1 yn. 528 00:23:33,470 --> 00:23:35,920 Mae olion o usages blaenorol y cof hwn. 529 00:23:35,920 --> 00:23:38,150 Ac nid ydym yn wir yn gwybod beth yw'r gwerthoedd yn cael eu, felly rydym fel arfer yn tynnu eu 530 00:23:38,150 --> 00:23:38,930 fel marciau cwestiwn. 531 00:23:38,930 --> 00:23:41,990 >> Felly, y peth cyntaf i ni yn ôl pob tebyg mynd i eisiau ei wneud yma - 532 00:23:41,990 --> 00:23:46,630 a gadewch i mi roi y maes hwn y tu mewn o yna enw - hambyrddau. 533 00:23:46,630 --> 00:23:49,540 Beth ddylem ni yn ôl pob tebyg ymgychwyn maint os ydym am 534 00:23:49,540 --> 00:23:51,040 dechrau defnyddio pentwr hwn? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Hambwrdd yn is 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Felly, OK. 537 00:23:53,910 --> 00:23:56,710 I fod yn glir, gallu cael ei ddatgan mewn mannau eraill â thri. 538 00:23:56,710 --> 00:23:58,570 A dyna beth rwyf wedi defnyddio i ddyrannu y rhesi. 539 00:23:58,570 --> 00:24:03,535 Maint yn mynd i gyfeirio at faint o hambyrddau ar hyn o bryd ar y pentwr. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Felly dylai fod yn sero. 542 00:24:04,460 --> 00:24:07,760 Felly, mynd yn ei flaen, a gydag unrhyw bys, tynnu sero o ran maint. 543 00:24:07,760 --> 00:24:08,440 Mae pob hawl. 544 00:24:08,440 --> 00:24:10,920 Felly nawr, beth sydd y tu mewn o hyn yma, nid ydym yn gwybod. 545 00:24:10,920 --> 00:24:12,160 Mae'r rhain yn wir werthoedd garbage yn unig. 546 00:24:12,160 --> 00:24:14,800 Felly, gallem dynnu marciau cwestiwn, ond gadewch i ni gadw'r bwrdd yn lân ar hyn o bryd 547 00:24:14,800 --> 00:24:16,300 am nad yw o bwys beth sydd yno. 548 00:24:16,300 --> 00:24:19,130 Nid oes angen inni i ymgychwyn y rhesi i unrhyw beth, oherwydd os ydym yn gwybod bod 549 00:24:19,130 --> 00:24:23,100 maint y pentwr yn sero, yn dda, rydym yn Ni ddylid edrych ar unrhyw beth yn 550 00:24:23,100 --> 00:24:25,590 amrywiaeth hwn beth bynnag yn hyn o bryd. 551 00:24:25,590 --> 00:24:29,970 >> Felly nawr mae'n debyg fy mod yn gwthio y rhif 9 ar y pentwr. 552 00:24:29,970 --> 00:24:33,750 Sut ddylem ni ddiweddaru'r strwythur data tu mewn y blwch du? 553 00:24:33,750 --> 00:24:35,540 Pa werthoedd angen newid? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: O fewn - 555 00:24:36,200 --> 00:24:37,400 maint? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Dylai maint yn dod yn beth? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Byddai maint fod yn un. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Felly dylai maint ddod yn un. 561 00:24:41,110 --> 00:24:42,540 Felly, gallwch wneud hyn mewn cwpl o ffyrdd. 562 00:24:42,540 --> 00:24:46,920 Gadewch i mi roi i chi, nawr eich bys yn rhwbiwr. 563 00:24:46,920 --> 00:24:47,260 Mae pob hawl. 564 00:24:47,260 --> 00:24:49,960 Yna, nawr eich bys yn brwsh. 565 00:24:49,960 --> 00:24:50,330 Mae pob hawl. 566 00:24:50,330 --> 00:24:52,820 Ac yn awr beth arall wedi newid, yn amlwg, yn y strwythur data? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Rydym yn mynd o gwaelod i fyny i 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 Iawn, Da. 570 00:24:58,420 --> 00:25:01,550 Felly, yn dal yn ots beth sydd yn y lleoliad un neu ddau oherwydd eu bod yn 571 00:25:01,550 --> 00:25:04,520 gwerthoedd garbage, ond ni ddylem drafferthu edrych yno oherwydd maint yn 572 00:25:04,520 --> 00:25:07,540 dweud wrthym mai dim ond yr elfen gyntaf mewn gwirionedd yn gyfreithlon. 573 00:25:07,540 --> 00:25:10,400 Felly, yn awr yr wyf wthio 17 ar y rhestr. 574 00:25:10,400 --> 00:25:11,830 Beth sy'n digwydd i'r darlun hwn? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Felly faint yn mynd i fynd i ddau. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Rydych yn rhwbiwr - 578 00:25:16,070 --> 00:25:16,810 wps. 579 00:25:16,810 --> 00:25:18,026 Rydych chi'n rwber. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Rydych chi'n brwsh. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 A beth arall? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Ac yna rydym yn - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Yr ydym yn gwthio 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Rydym yn cadw 17 ar ben, felly - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, yn dda. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - gollwng i lawr. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Pob hawl. 591 00:25:27,530 --> 00:25:27,940 Mae'n mynd yn hawdd. 592 00:25:27,940 --> 00:25:29,300 Dydw i ddim yn mynd i helpu chi y tro hwn. 593 00:25:29,300 --> 00:25:30,510 Gwthiwch 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Done. 595 00:25:31,720 --> 00:25:34,870 Dod yn rhwbiwr. 596 00:25:34,870 --> 00:25:37,340 Rwy'n dod yn brwsh. 597 00:25:37,340 --> 00:25:39,340 Ac yna yr wyf yn rhoi 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Ardderchog. 600 00:25:40,620 --> 00:25:41,380 Felly, un yn fwy o amser. 601 00:25:41,380 --> 00:25:44,280 Rwyf nawr yn mynd i wthio ar y pentwr 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh diar. 604 00:25:50,278 --> 00:25:52,520 Rydych yn wir yn dal fi oddi ar wyliadwrus. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: Nid ydych yn gwneud gweld hyn yn dod? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Doeddwn i ddim yn gweld hyn yn dod. 607 00:25:55,930 --> 00:25:58,756 Gallem gallu ail-cychwynnol? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: Mae hynny'n gwestiwn da. 609 00:25:59,790 --> 00:26:02,360 Felly, rydym wedi math o beintio ein hunain mewn cornel yma. 610 00:26:02,360 --> 00:26:06,740 Yn wir, dim allan da i Steven oherwydd ein bod wedi dyrannu amrywiaeth hwn 611 00:26:06,740 --> 00:26:09,130 llonydd, fel petai, y tu mewn y strwythur data. 612 00:26:09,130 --> 00:26:12,170 Ac rydym wedi codio hanfod galed ei fod o faint tri. 613 00:26:12,170 --> 00:26:14,170 Felly, ni allwn mewn gwirionedd ei ailddyrannu. 614 00:26:14,170 --> 00:26:20,020 >> Gallem os ydym yn mynd yn ôl i mewn, rydym yn ailddiffinio hambyrddau i fod yn pwyntydd y 615 00:26:20,020 --> 00:26:22,300 Yna, rydym yn defnyddio malloc i gof llaw i. 616 00:26:22,300 --> 00:26:25,050 Oherwydd os ydym yn cael y cof o'r y domen drwy malloc, rydym yn 617 00:26:25,050 --> 00:26:26,430 yna gellid rhyddhau ei. 618 00:26:26,430 --> 00:26:29,630 Ond cyn ei ryddhau, gallem ailddyrannu fwy darn o gof, 619 00:26:29,630 --> 00:26:31,330 diweddaru'r pwyntydd, ac yn y blaen. 620 00:26:31,330 --> 00:26:33,500 Ond ar hyn o bryd, mae hyn yn wir y gorau y gallwn ei wneud. 621 00:26:33,500 --> 00:26:36,360 Gwthio a pop yn mynd yn ôl pob tebyg i gael i ddangos rhyw wall. 622 00:26:36,360 --> 00:26:40,270 >> Felly, er enghraifft, mae ein gweithredu o Gallai gwthio dychwelyd bool sy'n 623 00:26:40,270 --> 00:26:42,390 dychwelyd yn flaenorol yn wir, yn wir, yn wir. 624 00:26:42,390 --> 00:26:48,390 Ond y pedwerydd tro, mae'n mynd i gael dychwelyd ffug, er enghraifft. 625 00:26:48,390 --> 00:26:48,540 Mae pob hawl. 626 00:26:48,540 --> 00:26:49,540 Gwneud yn dda iawn. 627 00:26:49,540 --> 00:26:50,060 Llongyfarchiadau. 628 00:26:50,060 --> 00:26:52,160 Rydych chi wedi ennill eich pêl straen heddiw. 629 00:26:52,160 --> 00:26:53,110 >> [Cymeradwyaeth] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Diolch yn fawr. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Diolch yn fawr. 632 00:26:55,680 --> 00:26:59,740 Iawn, felly mae hyn yn ymddangos i fod dim llawer o yn gam ymlaen, dde? 633 00:26:59,740 --> 00:27:01,410 Rydym yn disgrifio hyn strwythur data. 634 00:27:01,410 --> 00:27:02,320 Mae wedi bod yn gymhellol, dde? 635 00:27:02,320 --> 00:27:03,200 Systemau gweithredu ei hoffi. 636 00:27:03,200 --> 00:27:06,360 Mae'n debyg y gall y we yn gwneud defnydd o hyn, a cheisiadau eraill yn dal. 637 00:27:06,360 --> 00:27:10,870 Ond beth yw cyfyngiad dwp ein bod ni'n yn ôl i'r math o wythnos dau terfynau 638 00:27:10,870 --> 00:27:12,880 lle rydym wedi sefydlog araeau maint. 639 00:27:12,880 --> 00:27:15,010 >> Felly, mae yna wir un neu ddau o ffyrdd y gallem ddatrys hyn. 640 00:27:15,010 --> 00:27:18,750 Gallai ddynamig yn dyrannu'r amrywiaeth, nid gan codio galed gan fy mod i wedi 641 00:27:18,750 --> 00:27:22,600 wneud yma, ond yn hytrach ail-ddatgan hyn, dim ond i fod yn glir, fel y 642 00:27:22,600 --> 00:27:23,830 rhywbeth fel hyn. 643 00:27:23,830 --> 00:27:29,040 * Hambyrddau int, nid penderfynu ar y gallu eto. 644 00:27:29,040 --> 00:27:35,460 Ond pan fyddaf yn datgan bod y pentwr mewn man arall yn fy cod, gallwn wedyn alw malloc, 645 00:27:35,460 --> 00:27:38,250 gael y cyfeiriad o darn o cof, a gallwn neilltuo 646 00:27:38,250 --> 00:27:39,980 y cyfeiriad hwnnw i hambyrddau. 647 00:27:39,980 --> 00:27:43,340 >> Ac yna, oherwydd mai dim ond darn o cof, gallwn barhau i ddefnyddio sgwâr 648 00:27:43,340 --> 00:27:45,450 nodiant braced yn y ffordd arferol. 649 00:27:45,450 --> 00:27:49,020 Oherwydd unwaith eto, mae hyn yn fath o cyfateb swyddogaethol araeau a 650 00:27:49,020 --> 00:27:50,820 darnau o gof sy'n dod yn ôl o malloc. 651 00:27:50,820 --> 00:27:53,090 Gallwn drin un fel y llall defnyddio rhifyddeg pwyntydd neu 652 00:27:53,090 --> 00:27:54,440 nodiant braced sgwâr. 653 00:27:54,440 --> 00:27:55,660 Felly, dyna un dull o weithredu. 654 00:27:55,660 --> 00:28:00,120 >> Ond sut arall y gallwn roi hyn ar waith strwythur data un fath, o bosibl? 655 00:28:00,120 --> 00:28:00,280 Iawn? 656 00:28:00,280 --> 00:28:04,530 Rwy'n teimlo fel ni ond datrys hyn problem fel wythnos yn ôl. 657 00:28:04,530 --> 00:28:08,860 Beth oedd yr ateb i'r broblem hon Steven bod yn rhedeg i mewn? 658 00:28:08,860 --> 00:28:10,370 Rhestrau Felly cysylltiedig, ar y dde. 659 00:28:10,370 --> 00:28:13,410 >> Os yw'r broblem yn ein bod yn paentio ein hunain i mewn i gornel trwy ddyrannu 660 00:28:13,410 --> 00:28:17,580 ymlaen llaw yn rhy fach cof ein bod yn Yna, wedi i rhywsut ddelio â nhw, yn dda, 661 00:28:17,580 --> 00:28:19,880 pam na dim ond osgoi hynny cyhoeddi yn gyfan gwbl? 662 00:28:19,880 --> 00:28:26,170 Pam nid dim ond datgan hambyrddau i fod yn pwyntydd i nod, ergo restr cysylltiedig, 663 00:28:26,170 --> 00:28:30,740 ac yna dim ond dyrannu nodau newydd bob amser sydd ei angen Steven i osod 664 00:28:30,740 --> 00:28:32,400 nifer yn y strwythur data. 665 00:28:32,400 --> 00:28:34,200 >> Felly, byddai'n rhaid i'r llun i newid. 666 00:28:34,200 --> 00:28:38,220 Dyw hi ddim yn mynd i fod mor lân ac fel syml â dim ond casgliad o dri ints. 667 00:28:38,220 --> 00:28:42,970 Nawr, mae'n mynd i fod yn pwyntydd i strwythur, a bod y strwythur yn mynd i 668 00:28:42,970 --> 00:28:44,830 cael int a pwyntydd nesaf. 669 00:28:44,830 --> 00:28:47,670 Mae'n mynd i arwain trwy gyfrwng y pwyntydd i strwythur arall o'r fath i 670 00:28:47,670 --> 00:28:48,600 strwythur arall o'r fath. 671 00:28:48,600 --> 00:28:50,560 Felly, byddai'r darlun mewn gwirionedd cael braidd yn anniben. 672 00:28:50,560 --> 00:28:52,950 A byddem yn wedi saethau glymu popeth at ei gilydd. 673 00:28:52,950 --> 00:28:55,280 >> Ond mae hynny'n iawn, iawn, oherwydd rydym wedi gweld sut i wneud hyn. 674 00:28:55,280 --> 00:28:58,180 Ac unwaith y byddwch yn gyfforddus weithredu rhywbeth fel cysylltiedig 675 00:28:58,180 --> 00:29:01,450 rhestr, a bydd rhaid i chi ei wneud os ydych yn ddewis gweithredu tabl hash gyda 676 00:29:01,450 --> 00:29:05,120 gadwyno ar wahân ar gyfer p-set 6, gallwch ei ddefnyddio fel bloc adeiladu, neu 677 00:29:05,120 --> 00:29:08,870 cynhwysyn, neu mewn Scratch siarad, a weithdrefn, rhywbeth yr ydych yn ei roi, i chi 678 00:29:08,870 --> 00:29:12,560 creu eich darn pos eich hun y gallwch wedyn ailddefnyddio. 679 00:29:12,560 --> 00:29:17,090 Cyfaddawdu hynny, ond atebion posibl yr ydym wedi gweld mewn gwirionedd o'r blaen. 680 00:29:17,090 --> 00:29:20,560 >> Felly, yn aml iawn, byddwch yn gweld hyn bob blwyddyn neu ddau pan Datganiadau Apple 681 00:29:20,560 --> 00:29:23,060 rhywbeth newydd, a'r holl bobl crazy llinell i fyny y tu allan i'r Apple 682 00:29:23,060 --> 00:29:27,050 storio i brynu eu ymylol uwchraddio ar galedwedd. 683 00:29:27,050 --> 00:29:30,420 Yr wyf yn dweud hyn, mae'n iawn, gan fod Yr wyf yn un o'r bobl hynny. 684 00:29:30,420 --> 00:29:35,140 Felly, pa fath o strwythur data allai gynrychioli realiti hwn? 685 00:29:35,140 --> 00:29:36,980 >> Wel, gadewch i ni ei alw yn ciw, llinell. 686 00:29:36,980 --> 00:29:40,270 Felly, byddai Prydain yn galw fel arfer yn ciw beth bynnag, felly mae'n enw 'n glws. 687 00:29:40,270 --> 00:29:44,960 A'r ddau gweithrediadau y ciw Bydd cefnogi byddwn yn galw enqueue 688 00:29:44,960 --> 00:29:48,900 gweithredu a gweithrediad dequeue, sy'n debyg o ran 689 00:29:48,900 --> 00:29:50,120 ysbryd i gwthio a pop. 690 00:29:50,120 --> 00:29:54,060 'I' jyst fath o wahanol confensiwn, yr hyn rydym yn galw hyn. 691 00:29:54,060 --> 00:29:57,680 Ond i enqueue rhywbeth olygu i ychwanegu neu rhowch i'r strwythur data. 692 00:29:57,680 --> 00:29:59,570 I dequeue olygu i symud oddi yno. 693 00:29:59,570 --> 00:30:05,170 Ond tra bod pentwr oedd data LIFO strwythur, ciw yn i mewn yn gyntaf, 694 00:30:05,170 --> 00:30:06,740 cyntaf allan strwythur data. 695 00:30:06,740 --> 00:30:10,050 >> Os mai chi yw'r person cyntaf yn unol, chi fydd y person cyntaf i gael 696 00:30:10,050 --> 00:30:12,420 allan o linell a phrynu eich dyfais newydd. 697 00:30:12,420 --> 00:30:18,070 Dychmygwch pa mor ofidus fyddai'r bobl hyn yn os Apple yn hytrach na defnyddio stac, er 698 00:30:18,070 --> 00:30:21,250 enghraifft, i weithredu'r casglu cynnwys eich tegan newydd. 699 00:30:21,250 --> 00:30:24,310 Felly ciwiau yn gwneud synnwyr, yn sicr, a gallwn ni feddwl am bob math o 700 00:30:24,310 --> 00:30:27,480 ceisiadau, yn ôl pob tebyg, ar gyfer ciwiau, yn enwedig pan ydych eisiau tegwch. 701 00:30:27,480 --> 00:30:30,040 Felly, sut y byddwn yn gweithredu'r fel strwythur data? 702 00:30:30,040 --> 00:30:33,680 >> Wel, yr wyf yn cynnig ein bod yn gallai angen iddynt ei wneud fel hyn. 703 00:30:33,680 --> 00:30:35,225 Felly, yr wyf i'n mynd i awr rhifau. 704 00:30:35,225 --> 00:30:38,190 Felly, byddwn yn ei gadw'n syml ac nid reidrwydd yn siarad yn nhermau hambyrddau. 705 00:30:38,190 --> 00:30:40,220 Dim ond nifer fod pobl o gotten. 706 00:30:40,220 --> 00:30:43,760 Gallu yn mynd i, unwaith eto, atgyweiria 'r cyfanswm nifer y bobl sy'n gallu fod mewn 707 00:30:43,760 --> 00:30:46,900 y llinell hon, fel tri neu beth bynnag werth arall. 708 00:30:46,900 --> 00:30:50,760 >> Ond yr wyf yn cynnig bod angen i mi gadw golwg nid yn unig o faint y 709 00:30:50,760 --> 00:30:52,370 ciw, faint o bethau o blaid hyn. 710 00:30:52,370 --> 00:30:56,310 Felly, faint yw maint, capasiti cyfredol yn uchafswm maint. 711 00:30:56,310 --> 00:30:58,540 Dim ond eto, enwau drwy gonfensiwn. 712 00:30:58,540 --> 00:31:03,680 Pam mae angen int ychwanegol y tu mewn i o ciw i gadw cofnod o bwy sydd yn 713 00:31:03,680 --> 00:31:05,365 flaen y llinell? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Pam mae angen i mi wneud hynny yn yr achos hwn? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Wel, sut mae hyn ddarlun mynd i newid? 718 00:31:16,190 --> 00:31:19,280 Mae'n debyg y gallaf ailddefnyddio fwyaf y darlun hwn. 719 00:31:19,280 --> 00:31:21,480 Gadewch i mi fynd yn ei flaen ac yn dileu yr hyn sydd yma. 720 00:31:21,480 --> 00:31:24,580 Byddwn yn rhoi hyn ychydig yn enw gwahanol i fyny yma. 721 00:31:24,580 --> 00:31:28,930 Gadewch i ni gael gwared ar y 17, gadewch i ni gael gwared o'r 9, gadewch i ni gael gwared ar y 3. 722 00:31:28,930 --> 00:31:30,410 A gadewch i ni ychwanegu un peth arall. 723 00:31:30,410 --> 00:31:34,710 Cynigiaf fod angen i mi gadw golwg ar flaen y rhestr, sydd ychydig 724 00:31:34,710 --> 00:31:35,570 mynd i fod yn int hefyd. 725 00:31:35,570 --> 00:31:36,550 Ac rydym yn mynd i gadw pethau'n syml. 726 00:31:36,550 --> 00:31:37,740 Dim rhestr gysylltu am y tro. 727 00:31:37,740 --> 00:31:40,900 >> Byddwn yn cyfaddef ein bod yn mynd i daro i fyny yn erbyn y terfyn hwn. 728 00:31:40,900 --> 00:31:43,720 Ond beth ydw i eisiau gweld digwydd y tro hwn? 729 00:31:43,720 --> 00:31:47,240 Felly, mae'n debyg i fynd ymlaen a'r cyntaf person yn dod i fyny yn unol, ac 730 00:31:47,240 --> 00:31:48,560 'i' y rhif 9. 731 00:31:48,560 --> 00:31:49,680 Oes gennym peli straen. 732 00:31:49,680 --> 00:31:51,330 A allaf ddwyn, dyweder, dau neu dri o bobl? 733 00:31:51,330 --> 00:31:52,690 Un, dau, tri? 734 00:31:52,690 --> 00:31:53,120 Dewch ar i fyny. 735 00:31:53,120 --> 00:31:56,022 O'r blaen, oherwydd byddwn yn gwneud hyn yn un cyflym. 736 00:31:56,022 --> 00:31:59,415 >> Mae pob un ohonoch yn awr yn mynd i fod yn bachgen fan yn unol yn Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Ni fyddwch yn derbyn Apple caledwedd ar ddiwedd y er. 739 00:32:06,210 --> 00:32:06,500 Mae pob hawl. 740 00:32:06,500 --> 00:32:09,430 Felly rydych yn rhif 9, rydych yn rhif 17, rhif 22. 741 00:32:09,430 --> 00:32:12,130 Mae'r rhain yn niferoedd fympwyol, fel myfyriwr IDs neu whatnot. 742 00:32:12,130 --> 00:32:14,550 Ac mewn dim ond hyn o bryd, gadewch i ni ddechrau i ddechrau ychwanegu pethau. 743 00:32:14,550 --> 00:32:16,000 A byddaf yn rhedeg y bwrdd yma y tro hwn. 744 00:32:16,000 --> 00:32:19,570 >> Felly, yn yr achos hwn, rwyf wedi ymgychwyn y blaen i fod - 745 00:32:19,570 --> 00:32:22,380 Nid wyf mewn gwirionedd yn wir yn poeni beth y blaen yw, oherwydd bod y maint yn sero. 746 00:32:22,380 --> 00:32:24,480 Felly, efallai yn ogystal dim ond hyn fod yn farc cwestiwn. 747 00:32:24,480 --> 00:32:26,170 Mae'r rhain i gyd yn farciau cwestiwn. 748 00:32:26,170 --> 00:32:29,880 Felly nawr byddwn yn dechrau mewn gwirionedd yn gweld rhai pobl yn leinin i fyny yn y siop. 749 00:32:29,880 --> 00:32:33,320 >> Felly, os rhif 9, chi yw'r un cyntaf yno am 05:00, mynd yn ei flaen ac yn llinell i fyny, 750 00:32:33,320 --> 00:32:34,210 neu y noson cynt. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Felly nawr 9 yma. 753 00:32:35,940 --> 00:32:37,940 Felly 9 yn y flaen y rhestr. 754 00:32:37,940 --> 00:32:41,440 Felly, yr wyf i'n mynd i fynd yn ei flaen a diweddaru maint y data cyfredol 755 00:32:41,440 --> 00:32:44,740 strwythur i beidio â fod yn 0 anymore, ond i fod yn 1. 756 00:32:44,740 --> 00:32:47,630 Rydw i'n mynd i roi 9 yn y flaen y rhestr. 757 00:32:47,630 --> 00:32:51,020 Gadewch i mi fynd yn ei flaen ac yn toggle y sgrin fel y gallwn weld y gorffennol ni yma. 758 00:32:51,020 --> 00:32:53,220 >> Ac yn awr beth ddylwn i ei eisiau i roi o flaen? 759 00:32:53,220 --> 00:32:56,240 Rydw i'n mynd i gadw golwg ar y flaen y ciw ar hyn o bryd 760 00:32:56,240 --> 00:32:58,570 ar leoliad 0. 761 00:32:58,570 --> 00:33:00,510 Oherwydd yr hyn sy'n nesaf yn mynd i ddigwydd? 762 00:33:00,510 --> 00:33:03,000 Wel, mae'n debyg yn awr yr wyf enqueue 17 hefyd. 763 00:33:03,000 --> 00:33:04,510 Felly hop yn unol yno. 764 00:33:04,510 --> 00:33:07,060 Ac eto, y math o ddrws i siop yn mynd i fod yma. 765 00:33:07,060 --> 00:33:08,700 Felly, yn awr yr wyf wedi ychwanegu 17. 766 00:33:08,700 --> 00:33:10,810 A hyd yn oed er bod guys hyn yn cael eu blocio y sgrin, mae hynny'n iawn, 767 00:33:10,810 --> 00:33:12,300 oherwydd gallwn weld i fyny yma. 768 00:33:12,300 --> 00:33:12,910 Mae'n ddrwg gennym. 769 00:33:12,910 --> 00:33:13,810 >> GYNULLEIDFA: Gallwn symud - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Na, mae hynny'n iawn. 771 00:33:14,660 --> 00:33:16,000 Mae'n enfawr i fyny yno. 772 00:33:16,000 --> 00:33:18,580 Felly 17 yn bellach y tu mewn y ciw. 773 00:33:18,580 --> 00:33:21,332 Angen i mi ddiweddaru a caeau nawr er bod? 774 00:33:21,332 --> 00:33:23,210 OK, yn bendant faint. 775 00:33:23,210 --> 00:33:26,430 A beth am flaen? 776 00:33:26,430 --> 00:33:27,040 OK, dim. 777 00:33:27,040 --> 00:33:30,200 Ni ddylai Front newid, oherwydd yn wahanol i stac, rydym yn 778 00:33:30,200 --> 00:33:31,370 am gynnal tegwch. 779 00:33:31,370 --> 00:33:35,150 Felly, os 9 yn dod i mewn yn gyntaf, yr ydym am 9 i fod y cyntaf allan o'r llinell 780 00:33:35,150 --> 00:33:36,420 ac i mewn i'r siop. 781 00:33:36,420 --> 00:33:37,220 >> Yn wir, gadewch i ni weld hynny. 782 00:33:37,220 --> 00:33:42,235 Cyn i ni ychwanegu 22, gadewch i ni mynd yn ei flaen a dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Beth yw eich enw eto? 784 00:33:42,970 --> 00:33:43,680 >> GYNULLEIDFA: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake yn mynd i gael dequeued awr. 786 00:33:45,440 --> 00:33:48,050 Felly, byddwch yn cael i gerdded i mewn i'r siop. 787 00:33:48,050 --> 00:33:49,880 Ac yn esgus bod y siop wedi dod i ben yno. 788 00:33:49,880 --> 00:33:51,970 Felly nawr beth sydd angen - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Beth sydd angen digwydd yn awr? 790 00:33:53,400 --> 00:33:54,490 Penderfyniad dylunio. 791 00:33:54,490 --> 00:33:56,825 Felly nid yw greddf drwg, ond - beth yw eich enw eto? 792 00:33:56,825 --> 00:33:57,090 >> GYNULLEIDFA: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Felly, yr hyn a wnaeth Dafydd yn ei wneud? 795 00:33:58,810 --> 00:34:02,590 Roedd yn ceisio datrys o ddatrys y data strwythur a symud oddi wrth ei leoliad 796 00:34:02,590 --> 00:34:04,100 i mewn i hen leoliad Jake. 797 00:34:04,100 --> 00:34:06,740 Ac mae hynny'n iawn os ydym yn barod i dderbyn hynny fel 798 00:34:06,740 --> 00:34:08,199 manylion gweithredu. 799 00:34:08,199 --> 00:34:11,100 Ond yn gyntaf, gadewch i ni roi'r wybodaeth ddiweddaraf i'r data strwythur cyn i ni wneud hynny. 800 00:34:11,100 --> 00:34:14,139 Oherwydd Dydw i ddim yn hoffi'r syniad o holl y bobl symud yn y llinell hon. 801 00:34:14,139 --> 00:34:17,360 >> Does dim llawer mawr os bydd David yn gwneud 'i ag un cam, ond unwaith eto, yn meddwl yn ôl i 802 00:34:17,360 --> 00:34:20,360 pan fyddwn wedi cael wyth o wirfoddolwyr ar y llwyfan ac rydym wedi gwneud fel gosod 803 00:34:20,360 --> 00:34:22,600 fath, lle y bu'n rhaid i ni ddechrau symud pawb o gwmpas. 804 00:34:22,600 --> 00:34:23,790 A gafodd ddrud, dde? 805 00:34:23,790 --> 00:34:28,330 Mae hynny'n gwneud i mi cringe am O mawr n, mawr O n sgwâr eto. 806 00:34:28,330 --> 00:34:30,650 Dyw hi ddim yn teimlo fel canlyniad delfrydol. 807 00:34:30,650 --> 00:34:32,080 >> Felly, gadewch i ni ddiweddaru'r. 808 00:34:32,080 --> 00:34:35,120 Felly, maint y ciw bellach 2. 809 00:34:35,120 --> 00:34:37,090 Mae'n awr yn unig 1. 810 00:34:37,090 --> 00:34:40,360 Ond gallaf nawr ddiweddaru rhywbeth Doeddwn i ddim yn diweddaru o'r blaen, mae'r 811 00:34:40,360 --> 00:34:41,130 flaen y rhestr. 812 00:34:41,130 --> 00:34:45,420 Caf fi ddweud, yw bod lleoliad 1? 813 00:34:45,420 --> 00:34:49,770 Felly, erbyn hyn mae gennym werth garbage yma, gwerth garbage yma, a David yn y 814 00:34:49,770 --> 00:34:51,469 canol y garbage hwn. 815 00:34:51,469 --> 00:34:54,980 Ond mae'r strwythur data yn dal yn gyfan. 816 00:34:54,980 --> 00:34:58,540 >> Ac yn wir, nid oes angen hyd yn oed i mi newid cyn-nifer Jake 817 00:34:58,540 --> 00:35:00,460 9, oherwydd pwy a gofalu. 818 00:35:00,460 --> 00:35:04,470 Mae gen i ddigon o wybodaeth bellach yn y maint fy mod yn gwybod oes un person yn 819 00:35:04,470 --> 00:35:05,030 ciw hwn. 820 00:35:05,030 --> 00:35:08,340 Ac yr wyf yn gwybod bod y person hwnnw yn y lleoliad 1, nid 0. 821 00:35:08,340 --> 00:35:09,760 Dydw i ddim yn cyfrif. 822 00:35:09,760 --> 00:35:11,300 Felly, 1 hefyd. 823 00:35:11,300 --> 00:35:13,410 Felly, y strwythur data yn dal i fod yn iawn. 824 00:35:13,410 --> 00:35:14,330 >> Wel, beth sy'n digwydd nesaf? 825 00:35:14,330 --> 00:35:15,010 Gadewch i ni enqueue - 826 00:35:15,010 --> 00:35:15,370 beth yw eich enw? 827 00:35:15,370 --> 00:35:16,160 >> GYNULLEIDFA: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Gadewch i ni enqueue a Callen, a 22 yn awr yn y ciw. 830 00:35:20,770 --> 00:35:22,300 Felly, yn awr yr hyn sydd wedi ei newid yma? 831 00:35:22,300 --> 00:35:24,380 Nid yw blaen yn mynd i newid, yn amlwg. 832 00:35:24,380 --> 00:35:27,160 Maint yn mynd i newid i fod yn 2 eto. 833 00:35:27,160 --> 00:35:31,590 A 22 yn dod i ben i fyny yma, 9 yn dal yn bresennol, ond mae'n effeithiol yn 834 00:35:31,590 --> 00:35:32,600 gwerth garbage awr. 835 00:35:32,600 --> 00:35:35,910 Dim ond yn weddill Jake gorffennol. 836 00:35:35,910 --> 00:35:39,200 >> Felly, yn awr beth fydd yn digwydd os Yr wyf dequeue David? 837 00:35:39,200 --> 00:35:41,560 Un gweithrediad diwethaf, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Gallem newid, ond yr wyf yn cynnig gadewch i gwneud cyn lleied o waith ag y bo modd. 839 00:35:46,070 --> 00:35:50,280 Nawr fy strwythur data yn mynd gefn o ran maint 2-1. 840 00:35:50,280 --> 00:35:53,730 Ond flaen y ciw nawr yn 2. 841 00:35:53,730 --> 00:35:56,640 Nid oes angen i mi newid y rhifau hyn eto, am eu bod yn 842 00:35:56,640 --> 00:35:58,230 gwerthoedd garbage yn unig. 843 00:35:58,230 --> 00:35:59,720 >> Ond yn awr beth sy'n digwydd? 844 00:35:59,720 --> 00:36:03,280 Gadewch i ni dybio wyf enqueue fy hun, 26? 845 00:36:03,280 --> 00:36:05,890 Rwy'n teimlo fy mod yn perthyn dros yma. 846 00:36:05,890 --> 00:36:06,890 Felly rwy'n cael enqueued. 847 00:36:06,890 --> 00:36:08,760 Felly, yr wyf yn fath o yn perthyn yma. 848 00:36:08,760 --> 00:36:11,300 A hyd yn oed er eich bod yn ei wneud ddim yn hollol gwerthfawrogi hyn weledol ar y llwyfan, 849 00:36:11,300 --> 00:36:15,075 gan fod gennym ddigon o le, dylwn Nid yn sefyll yma, pam? 850 00:36:15,075 --> 00:36:16,290 >> GYNULLEIDFA: Rydych chi allan o nerth. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Iawn. 852 00:36:16,370 --> 00:36:16,940 Rwy'n yn waharddedig. 853 00:36:16,940 --> 00:36:19,330 Rwyf wedi mynegeio y tu hwnt i'r ffiniau amrywiaeth hwn. 854 00:36:19,330 --> 00:36:23,420 Fi 'n sylweddol dylai fod yn un o'r tri lleoliad posibl. 855 00:36:23,420 --> 00:36:25,150 Nawr, ble mae'r rhan fwyaf naturiol i fynd? 856 00:36:25,150 --> 00:36:27,760 Cynigiaf ein ysgogi yr wythnos un tric. 857 00:36:27,760 --> 00:36:30,150 Mae'r gweithredwr mod, canran. 858 00:36:30,150 --> 00:36:36,850 Gan fy mod i'n dechnegol sefyll yn lleoliad 3, ond yr wyf yn 3 capasiti mod, 859 00:36:36,850 --> 00:36:40,250 hynny 3, arwydd y cant, 3 - 860 00:36:40,250 --> 00:36:40,970 capasiti yn 3. 861 00:36:40,970 --> 00:36:41,720 Beth sy'n bod? 862 00:36:41,720 --> 00:36:43,700 Beth yw'r gweddill pan rydych rhannu 3 erbyn 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Er mwyn i mi eu rhoi oedd Jake, sy'n beth da mewn gwirionedd. 865 00:36:48,140 --> 00:36:50,370 Felly, yn awr y gweithrediad y peth yn mynd i 866 00:36:50,370 --> 00:36:51,250 fod yn dipyn o gur pen. 867 00:36:51,250 --> 00:36:53,740 Mae'n wir yn un llinell yn unig o cur pen, o god. 868 00:36:53,740 --> 00:36:56,580 Ond o leiaf yn awr mae garbage gwerth yma, ond mae dau 869 00:36:56,580 --> 00:36:57,910 ints cyfreithlon yma. 870 00:36:57,910 --> 00:37:04,160 Ac yr wyf yn honni bod yn awr rydym wedi gwneud yn union beth sydd angen i wneud hynny cyhyd ag 871 00:37:04,160 --> 00:37:08,600 rydym yn newid yr hyn Jake werth oedd i fod yn 26. 872 00:37:08,600 --> 00:37:12,110 >> Erbyn hyn mae gennym ddigon o wybodaeth yn dal i i gynnal dilysrwydd 873 00:37:12,110 --> 00:37:13,060 y strwythur data. 874 00:37:13,060 --> 00:37:17,160 Rydym yn dal math o allan o lwc pan fyddwn yn eisiau i fewnosod pedwar neu fwy o gyfanswm 875 00:37:17,160 --> 00:37:20,740 elfennau, ond gallaf o leiaf yn gwneud 'n bert defnydd effeithlon o hyn cyson 876 00:37:20,740 --> 00:37:21,740 amser, mewn gwirionedd. 877 00:37:21,740 --> 00:37:27,150 Nid oes yn rhaid i mi boeni am newid bawb, fel awydd David oedd. 878 00:37:27,150 --> 00:37:30,816 >> Unrhyw gwestiynau ar staciau, neu ciw hwn? 879 00:37:30,816 --> 00:37:32,184 >> GYNULLEIDFA: A yw'r rheswm pam bydd angen maint er mwyn i chi wybod 880 00:37:32,184 --> 00:37:34,010 ble i gael person? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Yn union. 882 00:37:34,770 --> 00:37:38,230 Angen i mi wybod y maint y rhesi oherwydd mae angen i mi wybod yn union sut y 883 00:37:38,230 --> 00:37:41,940 llawer o'r gwerthoedd hyn yn gyfreithlon, ac fel y gallaf ddod o hyd i ble i roi 884 00:37:41,940 --> 00:37:42,800 y person nesaf. 885 00:37:42,800 --> 00:37:43,300 Yn union. 886 00:37:43,300 --> 00:37:44,580 Mae maint yw - 887 00:37:44,580 --> 00:37:46,360 mewn gwirionedd, nid ydym yn diweddaru'r hyn eto. 888 00:37:46,360 --> 00:37:48,380 I ychwanegu fy hun yn 26. 889 00:37:48,380 --> 00:37:51,760 Mae'r maint yn awr, nid 1, ond 2. 890 00:37:51,760 --> 00:37:57,780 Felly, yn awr mae hyn yn wir yn fy helpu i ddod o hyd i'r pennaeth y rhestr, nad yw'n 0, nid 891 00:37:57,780 --> 00:37:59,250 1, ond yw 2. 892 00:37:59,250 --> 00:38:01,665 Mae blaen y rhestr yn wir rhif 22. 893 00:38:01,665 --> 00:38:05,120 Oherwydd efe a ddaeth i mewn yn gyntaf, felly dylai ef yn cael ei ganiatáu i mewn i'r siop ger fy mron, 894 00:38:05,120 --> 00:38:08,780 hyd yn oed er eu golwg Dwi'n sefyll yn agosach at y siop. 895 00:38:08,780 --> 00:38:09,220 >> Mae pob hawl? 896 00:38:09,220 --> 00:38:12,410 Mae rownd o gymeradwyaeth ar gyfer guys hyn a byddwn yn gadael iddynt oddi yno. 897 00:38:12,410 --> 00:38:17,090 >> [Cymeradwyaeth] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: Gallwn roi eich bod yn cadw yr hambwrdd. 899 00:38:18,150 --> 00:38:20,760 Gallem weld beth sy'n digwydd os ydych ei eisiau, ond efallai na. 900 00:38:20,760 --> 00:38:21,590 Mae pob hawl. 901 00:38:21,590 --> 00:38:25,380 Felly beth nawr mae hynny'n gadael ni? 902 00:38:25,380 --> 00:38:28,900 Wel, gadewch i mi cynnig bod yna ychydig o strwythurau data arall gallem 903 00:38:28,900 --> 00:38:33,810 dechrau ychwanegu at ein pecyn cymorth a fydd yn mewn gwirionedd fod yn eithaf, yn eithaf perthnasol fel 904 00:38:33,810 --> 00:38:35,270 rydym yn plymio i mewn i we stwff. 905 00:38:35,270 --> 00:38:38,150 Sydd unwaith eto, mae rhyw fath o gysylltiad i goed ar ffurf 906 00:38:38,150 --> 00:38:40,550 rhywbeth o'r enw DOM, dogfen model gwrthrych. 907 00:38:40,550 --> 00:38:42,370 Ond byddwn yn gweld mwy o hynny cyn bo hir. 908 00:38:42,370 --> 00:38:46,260 >> Gadewch i mi gynnig definitionally ein bod yn ffoniwch goeden yn awr yr hyn y gallai gwybod i chi cyn 909 00:38:46,260 --> 00:38:48,820 mwy o goeden deulu, lle rydych yn cael rhywfaint o hynafiad yn y 910 00:38:48,820 --> 00:38:49,790 gwreiddiau'r goeden. 911 00:38:49,790 --> 00:38:54,480 A batriarchaidd neu matriarch yn frig y goeden. 912 00:38:54,480 --> 00:38:56,700 Heb ei briod, yn yr achos hwn. 913 00:38:56,700 --> 00:39:00,940 Ond mae gennym yn awr yr hyn y byddwn yn galw plant, sef nodau sy'n hongian 914 00:39:00,940 --> 00:39:05,480 oddi ar y plentyn chwith neu i'r plentyn iawn, saethau fel y dangosir yma. 915 00:39:05,480 --> 00:39:10,490 >> Mewn geiriau eraill, mewn strwythur data coeden mewn cyfrifiadur, coeden wedi sero 916 00:39:10,490 --> 00:39:11,480 neu fwy o nodau. 917 00:39:11,480 --> 00:39:13,500 Os oes o leiaf un nod, sy'n cael ei alw y gwraidd. 918 00:39:13,500 --> 00:39:15,700 Mae'n y pethau weledol y rydym yn tynnu ar y brig. 919 00:39:15,700 --> 00:39:20,280 A dyna nod, fel unrhyw nod arall, gall gael sero, un, neu ddau, neu dri, 920 00:39:20,280 --> 00:39:23,600 neu faint bynnag o blant y strwythur data yn cefnogi. 921 00:39:23,600 --> 00:39:29,150 Yn yr achos hwn, y gwraidd, storio gwerth un, mae dau o blant, 2 a 3, 922 00:39:29,150 --> 00:39:33,020 felly rydym yn gyffredinol ffoniwch 2 y chwith plentyn a 3 y plentyn cywir. 923 00:39:33,020 --> 00:39:36,940 >> Ac yna pan fyddwn yn mynd i lawr i 5, 6, a Efallai 7, 6 yn cael ei alw y plentyn canol. 924 00:39:36,940 --> 00:39:38,940 Os oes gennych bedwar o blant, mae'n mynd yn ddryslyd. 925 00:39:38,940 --> 00:39:42,260 Felly, rydym yn rhoi'r gorau i ddefnyddio math hwnnw o'r llwybr byr ar lafar. 926 00:39:42,260 --> 00:39:44,580 Ond mewn gwirionedd dim ond coeden deulu. 927 00:39:44,580 --> 00:39:48,880 Ac mae'r dail yma y nodau y eu hunain heb blant. 928 00:39:48,880 --> 00:39:52,540 Maent yn hongian oddi ar waelod y goeden. 929 00:39:52,540 --> 00:39:56,940 >> Felly, sut y gallem weithredu coeden sy'n wedi dim ond dau o blant maximally? 930 00:39:56,940 --> 00:39:58,410 Byddwn yn galw ei fod yn goeden ddeuol. 931 00:39:58,410 --> 00:40:00,960 Bi eto yn golygu dau, yn yr achos, fel gyda deuaidd. 932 00:40:00,960 --> 00:40:04,830 Ac felly gall gael sero, un, neu ddau o blant maximally. 933 00:40:04,830 --> 00:40:08,650 >> 'N annhymerus' cynnig ein bod yn gweithredu'r nod am y strwythur gyda n int, 934 00:40:08,650 --> 00:40:11,910 ac yna dau awgrymiadau, un o'r enw chwith, un o'r enw gywir. 935 00:40:11,910 --> 00:40:14,830 Ond y rhai yn unig 'n glws confensiynau mympwyol. 936 00:40:14,830 --> 00:40:18,170 A beth braf yn awr, yn enwedig os ydych yn fath o drafferth gysyniadol gyda 937 00:40:18,170 --> 00:40:21,300 recursion, neu yn meddwl nad oedd yn mewn gwirionedd yn ateb i unrhyw beth, 938 00:40:21,300 --> 00:40:23,120 yn enwedig os gallech rhedeg allan o gof. 939 00:40:23,120 --> 00:40:26,600 Nawr ein bod yn sôn am ddata strwythurau ac algorithmau sy'n caniatáu 940 00:40:26,600 --> 00:40:31,030 ni i groesi a thrin nhw, ymddangos bod recursion yn dod yn ôl yn 941 00:40:31,030 --> 00:40:34,240 llawer mwy cymhellol os nad yw ffordd hardd. 942 00:40:34,240 --> 00:40:38,670 >> Felly, mae hyn Cynigiaf yw'r gweithredu o swyddogaeth Chwilio. 943 00:40:38,670 --> 00:40:39,870 O ystyried dau fewnbwn - 944 00:40:39,870 --> 00:40:41,570 felly meddyliwch am hyn fel blwch du. 945 00:40:41,570 --> 00:40:46,560 O ystyried dau fewnbwn, n, yn int, a pwyntydd i goeden, pwyntydd i 946 00:40:46,560 --> 00:40:50,020 nod, neu, mewn gwirionedd wraidd coeden, yr wyf yn honni y gall swyddogaeth hon ddychwelyd 947 00:40:50,020 --> 00:40:53,530 gwir neu ffug, sy'n gwerthfawrogi n tu mewn y goeden hon. 948 00:40:53,530 --> 00:40:55,210 >> Beth sydd y tu mewn y blwch du? 949 00:40:55,210 --> 00:40:57,440 Wel, pedair cangen. 950 00:40:57,440 --> 00:40:58,385 Y cyfiawn gyntaf yn gwirio. 951 00:40:58,385 --> 00:41:00,490 Os yw coeden yn null, dim ond dychwelyd ffug. 952 00:41:00,490 --> 00:41:04,580 Os nad oes nod, does dim n, does dim rhif, dim ond dychwelyd ffug. 953 00:41:04,580 --> 00:41:12,330 Os, fodd bynnag, n, mae'r gwerth rydych yn chwilio amdano, yn llai na goeden saeth n, ac 954 00:41:12,330 --> 00:41:15,180 dim ond i fod yn glir, beth mae'n ei olygu pan Rwy'n ysgrifennu goeden ac yna y saeth 955 00:41:15,180 --> 00:41:18,150 nodiant, n? 956 00:41:18,150 --> 00:41:18,690 Yn union. 957 00:41:18,690 --> 00:41:21,970 Mae'n golygu bod dereference pwyntydd enw coeden. 958 00:41:21,970 --> 00:41:26,750 Ewch yno, ac yna yn cael y tu mewn o hynny nod a chael ei faes a elwir yn n. 959 00:41:26,750 --> 00:41:30,810 Ac yna cymharu'r n gwirioneddol a oedd yn pasio i mewn i Chwilio yn ei erbyn. 960 00:41:30,810 --> 00:41:35,390 >> Felly, os n yn llai na, mae'r gwerth n yn y nod goeden ei hun, yn dda, 961 00:41:35,390 --> 00:41:36,720 beth mae hynny'n ei olygu? 962 00:41:36,720 --> 00:41:40,690 Mae hynny'n golygu dim byd ar yr olwg gyntaf. 963 00:41:40,690 --> 00:41:40,900 Iawn? 964 00:41:40,900 --> 00:41:45,560 Yn union fel pan fydd gennych amrywiaeth o gwerthoedd, efallai yr hoffech wneud cais deuaidd 965 00:41:45,560 --> 00:41:48,290 chwilio fel math o raniad a gorchfygu. 966 00:41:48,290 --> 00:41:51,790 Ond beth dybiaeth oedd angen i ni wneud ar gyfer chwiliad deuaidd i weithio o gwbl 967 00:41:51,790 --> 00:41:54,510 yn y llyfr ffôn ac enghreifftiau cynharach? 968 00:41:54,510 --> 00:41:55,530 >> Sut i gael eu datrys. 969 00:41:55,530 --> 00:41:59,490 Felly, gadewch i ni fireinio'r diffiniad o goeden yma nid yn i fod yr un goeden, a all 970 00:41:59,490 --> 00:42:00,880 cael unrhyw nifer o blant. 971 00:42:00,880 --> 00:42:04,700 Nid dim ond coeden ddeuaidd, a all cael 0, 1, neu 2 maximally. 972 00:42:04,700 --> 00:42:09,700 Ond fel coeden chwiliad deuaidd, neu BST, sydd ychydig yn ffordd ffansi o ddweud 973 00:42:09,700 --> 00:42:15,430 goeden ddeuol fel bod pob nod yn chwith plentyn, os yw'n bresennol, yn 974 00:42:15,430 --> 00:42:16,830 llai na'r nod. 975 00:42:16,830 --> 00:42:20,170 A'r plentyn hawl pob nod, yn os yw'n bresennol, yn fwy 976 00:42:20,170 --> 00:42:21,740 na'r nod ei hun. 977 00:42:21,740 --> 00:42:25,200 >> Felly, mewn geiriau eraill, os ydych yn tynnu y tu allan i goeden, yr holl niferoedd yn 978 00:42:25,200 --> 00:42:30,620 gydbwyso yn ofalus fel hyn felly os mae gennych 55 fel y gwraidd, gall 33 fynd 979 00:42:30,620 --> 00:42:33,090 ar yr ochr chwith am ei fod yn llai na 55. 980 00:42:33,090 --> 00:42:36,430 77 Gall mynd i'r dde oherwydd ei fod yn fwy na 55. 981 00:42:36,430 --> 00:42:40,750 Ond yn awr yn sylwi, yr un diffiniad, mae'n ddiffiniad ailadroddus ar lafar, 982 00:42:40,750 --> 00:42:42,600 wedi gwneud cais am 33. 983 00:42:42,600 --> 00:42:47,610 Mae'n rhaid i 33 o blant ar y chwith fod yn llai na hynny, a rhaid plentyn iawn 33, a 44, yn 984 00:42:47,610 --> 00:42:48,580 yn fwy nag ef. 985 00:42:48,580 --> 00:42:51,670 >> Felly, mae hyn yn goeden chwiliad deuaidd, a Yr wyf yn cynnig, gan ddefnyddio ychydig o 986 00:42:51,670 --> 00:42:53,910 recursion, gallwn yn awr ddod o hyd i n. 987 00:42:53,910 --> 00:42:59,160 Felly, os n yn llai na gwerth n sy'n nod ar hyn o bryd, dw i'n mynd i fynd 988 00:42:59,160 --> 00:43:04,090 ymlaen a punt, fel petai, a dim ond dychwelyd beth bynnag yw'r ateb o 989 00:43:04,090 --> 00:43:08,470 chwilio am n ar y plentyn chwith goeden. 990 00:43:08,470 --> 00:43:11,370 Hysbysiad eto, swyddogaeth hon dim ond disgwyl yn seren nod, a 991 00:43:11,370 --> 00:43:12,780 pwyntydd i nod. 992 00:43:12,780 --> 00:43:17,360 Felly, yn sicr y gallaf wneud coeden saeth ar y chwith, a fydd yn arwain 993 00:43:17,360 --> 00:43:18,400 mi nod arall. 994 00:43:18,400 --> 00:43:19,480 Ond beth yw y nod? 995 00:43:19,480 --> 00:43:22,820 >> Wel, yn ôl y datganiad hwn, chwith yn unig yw pwyntydd, er mai dim ond 996 00:43:22,820 --> 00:43:27,090 golygu fy mod i'n mynd at y swyddogaeth chwilio pwyntydd gwahanol, sef 997 00:43:27,090 --> 00:43:30,750 yr un sy'n cynrychioli coeden fy mhlentyn chwith yn. 998 00:43:30,750 --> 00:43:36,040 Felly, yn yr achos hwn, y pwyntydd i 33, os mae hyn yn ein cyfraniad sampl y cyfamser, os 999 00:43:36,040 --> 00:43:40,740 n yn fwy na gwerth n yn y nod ar hyn o bryd yn y goeden, yna rwy'n 1000 00:43:40,740 --> 00:43:43,370 mynd i fynd yn ei flaen ac punt yn y llall cyfeiriad a dim ond dweud, nid wyf yn 1001 00:43:43,370 --> 00:43:47,280 gwybod os y gwerth hwn yw n yn y goeden, ond yr wyf yn gwybod os yw, ei fod yn i lawr fy 1002 00:43:47,280 --> 00:43:49,090 cangen iawn, fel petai. 1003 00:43:49,090 --> 00:43:53,120 Felly, gadewch i mi alwad chwilio recursively, pasio n eto, ond pasio mewn 1004 00:43:53,120 --> 00:43:54,580 pwyntydd i fy mhlentyn dde. 1005 00:43:54,580 --> 00:44:00,020 >> Mewn geiriau eraill, os ydw i'n ar hyn o bryd yn 55 ac rwy'n edrych am 99, yr wyf yn gwybod bod 99 1006 00:44:00,020 --> 00:44:04,270 yn fwy na 55, felly dim ond fel yr wyf yn rhwygo y ffôn llyfr wythnosau yn ôl ac rydym 1007 00:44:04,270 --> 00:44:07,140 aeth yn iawn, yn yr un modd rydym ni mynd i fynd i'r dde yma. 1008 00:44:07,140 --> 00:44:11,960 Ac nid wyf yn gwybod os yw'n ar fy hawl plentyn, ac nid yw'n, 77 yno, ond 1009 00:44:11,960 --> 00:44:13,210 Dwi'n gwybod ei fod yn y cyfeiriad hwnnw. 1010 00:44:13,210 --> 00:44:18,770 Felly, yr wyf yn galw chwilio am fy mhlentyn dde, 77, a gadewch ffigur chwilio allan o 1011 00:44:18,770 --> 00:44:24,950 yno os 99 yn yr fympwyol enghraifft o hyn yw mewn gwirionedd yno. 1012 00:44:24,950 --> 00:44:26,900 >> Else, beth yw'r achos terfynol? 1013 00:44:26,900 --> 00:44:28,620 Os yw coeden yn null un achos. 1014 00:44:28,620 --> 00:44:31,890 Os yw n yn llai na'r nod ar hyn o bryd yn gwerth yn achos arall. 1015 00:44:31,890 --> 00:44:35,120 Os yw n yn fwy na'r presennol gwerth nod yw trydydd achos. 1016 00:44:35,120 --> 00:44:38,250 Beth yw'r achos bedwaredd a'r olaf? 1017 00:44:38,250 --> 00:44:39,480 Yr wyf yn meddwl ein bod allan o achosion, dde? 1018 00:44:39,480 --> 00:44:44,690 Rhaid iddo fod yn bod n yn y nod ar hyn o bryd a dwi ar. 1019 00:44:44,690 --> 00:44:49,640 >> Felly, os ydw i'n chwilio am 55 ar hyn o bryd yn y stori, y gangen o 1020 00:44:49,640 --> 00:44:51,780 byddai coeden yn dychwelyd yn wir. 1021 00:44:51,780 --> 00:44:55,380 Felly, yr hyn sy'n ddiddorol yma yw ein bod yn mewn gwirionedd, yn wahanol wythnosau diwethaf, rydym fath 1022 00:44:55,380 --> 00:44:56,740 o'r gennym ddau achos sylfaenol. 1023 00:44:56,740 --> 00:44:58,300 Ac nid oes rhaid iddynt cael ei gyd ar y brig. 1024 00:44:58,300 --> 00:45:01,390 Mae pen uchaf yn achos sylfaenol oherwydd os bydd y goeden yn null, does dim byd i'w wneud. 1025 00:45:01,390 --> 00:45:03,410 Dim ond dychwelyd codio galed gwerth o ffug. 1026 00:45:03,410 --> 00:45:07,400 >> Mae'r gangen gwaelod yn fath o diofyn, lle os ydym wedi gwirio ar gyfer 1027 00:45:07,400 --> 00:45:11,550 null, rydym wedi gwirio os dylai fod yn chwith, ond ni ddylai fod yn, rydym wedi 1028 00:45:11,550 --> 00:45:14,640 gwirio a ddylai fod yn iawn, ond mae'n Ni ddylai fod, yn amlwg mae'n rhaid iddo fod 1029 00:45:14,640 --> 00:45:15,870 iawn lle yr ydym. 1030 00:45:15,870 --> 00:45:16,780 Dyna achos sylfaenol. 1031 00:45:16,780 --> 00:45:19,920 Felly, mae dau achos recursive gwasgu yno yn y canol. 1032 00:45:19,920 --> 00:45:21,630 Ond gallwn fod wedi ysgrifennu hyn mewn unrhyw drefn. 1033 00:45:21,630 --> 00:45:24,520 Fi jyst yn meddwl ei fath o teimlo'n naturiol i wirio yn gyntaf am gamgymeriad posibl, 1034 00:45:24,520 --> 00:45:28,340 ac yna gwirio'r i'r chwith, ac yna gwirio'r dde, ac yna cymryd yn ganiataol eich bod chi yn y nod 1035 00:45:28,340 --> 00:45:30,630 rydych yn chwilio amdano mewn gwirionedd. 1036 00:45:30,630 --> 00:45:36,240 >> Felly, pam y gallai hyn fod yn ddefnyddiol? 1037 00:45:36,240 --> 00:45:37,910 Felly, mae'n troi allan - 1038 00:45:37,910 --> 00:45:42,110 a gadewch i mi neidio i ymlid dyma sydd yn y we. 1039 00:45:42,110 --> 00:45:44,920 Rydym yn mynd i ddechrau defnyddio nid iaith raglennu ar y dechrau, ond mae 1040 00:45:44,920 --> 00:45:46,030 iaith markup. 1041 00:45:46,030 --> 00:45:48,740 A markup iaith yn un sy'n debyg o ran ysbryd i'r rhaglenni 1042 00:45:48,740 --> 00:45:51,715 iaith, ond nid yw'n rhoi i chi y gallu i fynegi eich hun yn rhesymegol. 1043 00:45:51,715 --> 00:45:55,070 Mae'n yn unig yn rhoi i chi y gallu i mynegi eich hun strwythurol. 1044 00:45:55,070 --> 00:45:57,960 >> Ble ydych chi eisiau rhoi rhywbeth ar y dudalen, mae'r dudalen ar y we? 1045 00:45:57,960 --> 00:45:59,200 Pa liw ydych chi eisiau ei wneud? 1046 00:45:59,200 --> 00:46:00,950 Pa faint ffont ydych chi eisiau ei wneud? 1047 00:46:00,950 --> 00:46:02,970 Pa eiriau ydych chi mewn gwirionedd yn chwilio amdanynt ar y dudalen we? 1048 00:46:02,970 --> 00:46:04,060 Felly dyna iaith markup. 1049 00:46:04,060 --> 00:46:07,690 Ond yna byddwn yn cyflwyno yn gyflym iawn JavaScript, sydd yn llawn-fledged 1050 00:46:07,690 --> 00:46:08,560 rhaglennu iaith. 1051 00:46:08,560 --> 00:46:12,530 Debyg iawn o ran golwg syntactically i C, ond bydd yn cael rhywfaint o 1052 00:46:12,530 --> 00:46:15,200 'n glws, yn fwy pwerus, yn fwy nodweddion cyfeillgar i'r defnyddiwr. 1053 00:46:15,200 --> 00:46:18,050 >> Ac un o'r rhwystredigaethau ar hyn o pwynt yn y semester yw ein bod yn chi helpu 1054 00:46:18,050 --> 00:46:22,065 fuan gweithredu sillafu yn llawer llai llinellau o god ddefnyddio ieithoedd eraill 1055 00:46:22,065 --> 00:46:25,580 na C ei hun yn caniatáu, ond am reswm yn byddwn yn deall yn fuan. 1056 00:46:25,580 --> 00:46:27,750 Hwn fydd y dudalen we cyntaf o'r fath. 1057 00:46:27,750 --> 00:46:30,120 Bydd yn gwbl underwhelming, yr un cyntaf a wnawn. 1058 00:46:30,120 --> 00:46:31,400 Bydd yn dweud yn syml, helo byd. 1059 00:46:31,400 --> 00:46:34,010 Ond os nad ydych erioed wedi ei weld o'r blaen, mae hyn yn HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Iaith. 1061 00:46:35,670 --> 00:46:39,310 >> Os ydych yn mynd i ddewis penodol ddewislen rhan fwyaf o unrhyw borwr, ar unrhyw dudalen ar y we ar 1062 00:46:39,310 --> 00:46:43,160 y rhyngrwyd, gallwch weld y HTML a ysgrifennodd rai pobl 1063 00:46:43,160 --> 00:46:44,400 creu y dudalen we. 1064 00:46:44,400 --> 00:46:47,850 Ac mae'n debyg nad yw'n edrych fel byr neu mor daclus â hyn. 1065 00:46:47,850 --> 00:46:51,400 Ond bydd yn dilyn y patrwm o'r rhain cromfachau agored a slaes a 1066 00:46:51,400 --> 00:46:53,660 llythrennau ac o bosibl rhifau. 1067 00:46:53,660 --> 00:46:56,770 >> Rwy'n meddwl y byddwn i'n rhoi teaser i chi o'r hyn y byddwch yn gallu gwneud 1068 00:46:56,770 --> 00:46:57,950 ar ôl cymryd CS50. 1069 00:46:57,950 --> 00:47:02,620 Gadewch i mi fynd i cs.harvard.edu / ddwyn, hafan ein hunain Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Gwnaeth hyn i ni. 1071 00:47:06,080 --> 00:47:07,490 Felly byddwch yn fuan yn gallu gwneud hynny. 1072 00:47:07,490 --> 00:47:10,660 A hefyd, yr hyn yr ydych wedi clywed y bore yma - 1073 00:47:10,660 --> 00:47:12,480 yr hyn yr ydych wedi clywed y bore yma - 1074 00:47:12,480 --> 00:47:13,780 >> [Bochdew DAWNS CERDDORIAETH] 1075 00:47:13,780 --> 00:47:15,702 >> - You'll yn gallu gwneud hyn. 1076 00:47:15,702 --> 00:47:16,790 Mae hynny'n ein disgwyl ar ddydd Mercher. 1077 00:47:16,790 --> 00:47:17,791 Byddwn yn eich gweld bryd hynny. 1078 00:47:17,791 --> 00:47:22,950 >> [Bochdew DAWNS CERDDORIAETH] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: Yn y CS50 nesaf - 1080 00:47:24,300 --> 00:47:31,670