1 00:00:00,000 --> 00:00:05,259 2 00:00:05,259 --> 00:00:08,300 DOUG LLOYD: Mar sin, i CS50, tá muid clúdaithe a lán de na struchtúir éagsúla sonraí, 3 00:00:08,300 --> 00:00:09,180 ceart? 4 00:00:09,180 --> 00:00:11,420 Againn atá le feiceáil eagair, agus nasctha liostaí, agus táblaí hash, 5 00:00:11,420 --> 00:00:15,210 agus iarracht, stoic agus scuainí. 6 00:00:15,210 --> 00:00:17,579 Beidh muid ag foghlaim freisin beag faoi ​​chrainn agus heaps, 7 00:00:17,579 --> 00:00:20,120 ach i ndáiríre seo go léir deireadh ach suas a bheith athruithe ar théama. 8 00:00:20,120 --> 00:00:22,840 Tá i ndáiríre na de chineál ar cheithre smaointe bunúsacha 9 00:00:22,840 --> 00:00:25,190 gur féidir gach rud eile boil síos go dtí. 10 00:00:25,190 --> 00:00:28,150 Arrays, liostaí nasctha, táblaí hash, agus iarracht. 11 00:00:28,150 --> 00:00:30,720 Agus mar a dúirt mé, tá Tá éagsúlachtaí orthu, 12 00:00:30,720 --> 00:00:32,720 ach tá sé seo go leor i bhfad ag dul chun achoimre 13 00:00:32,720 --> 00:00:38,140 gach rud a táimid ag dul chun labhairt faoi ​​sa rang seo i dtéarmaí C. 14 00:00:38,140 --> 00:00:40,140 >> Ach conas a dhéanann seo go léir beart suas, ceart? 15 00:00:40,140 --> 00:00:44,265 Táimid tar éis Labhair faoi na buntáistí agus na míbhuntáistí de gach ceann i físeáin ar leith orthu, 16 00:00:44,265 --> 00:00:46,390 ach níl a lán de uimhreacha dul thrown timpeall. 17 00:00:46,390 --> 00:00:48,723 Níl a lán de ginearálta smaointe ag fáil thrown timpeall. 18 00:00:48,723 --> 00:00:51,950 A ligean ar iarracht a dhéanamh agus a chomhdhlúthú sé isteach ach áit amháin. 19 00:00:51,950 --> 00:00:55,507 A ligean ar weigh an son i gcoinne na míbhuntáistí, agus a mheas 20 00:00:55,507 --> 00:00:57,340 a struchtúr sonraí d'fhéadfadh a bheith ar na sonraí ceart 21 00:00:57,340 --> 00:01:01,440 Struchtúr le do staid faoi leith, is cuma cén cineál sonraí a bhfuil tú ag a stóráil. 22 00:01:01,440 --> 00:01:06,625 Ní gá duit gá go mór i gcónaí chun úsáid a bhaint as a chur isteach go tapa Super, scriosadh, 23 00:01:06,625 --> 00:01:10,761 agus Lookup de Trie má tá tú i ndáiríre nach cúram faoi a chur isteach agus a scriosadh 24 00:01:10,761 --> 00:01:11,260 an iomarca. 25 00:01:11,260 --> 00:01:13,968 Más gá duit ach randamach tapa rochtain, b'fhéidir go bhfuil sraith níos fearr. 26 00:01:13,968 --> 00:01:15,340 Mar sin, a ligean ar distill sin. 27 00:01:15,340 --> 00:01:18,530 A ligean ar labhairt faoi gach ceann de na ceithre cineálacha mór ar struchtúir sonraí 28 00:01:18,530 --> 00:01:21,720 go atá againn Labhair faoi, agus ach a fheiceáil nuair a d'fhéadfadh siad a bheith go maith, 29 00:01:21,720 --> 00:01:23,340 agus nuair nach bhféadfadh siad a bheith chomh maith. 30 00:01:23,340 --> 00:01:24,610 Sin a ligean le tús a chur le arrays. 31 00:01:24,610 --> 00:01:27,300 Mar sin, a chur isteach, go bhfuil de chineál ar dona. 32 00:01:27,300 --> 00:01:31,350 >> Is chur isteach ag deireadh na eagar OK, má tá muid ag tógáil sraith mar a théann muid. 33 00:01:31,350 --> 00:01:33,570 Ach má ní mór dúinn a chur isteach eilimintí isteach sa lár, 34 00:01:33,570 --> 00:01:35,550 I mo thuairimse, ar ais go dtí a chur isteach a shórtáil, níl a lán 35 00:01:35,550 --> 00:01:37,510 de aistriú a d'oirfeadh gné i ann. 36 00:01:37,510 --> 00:01:41,170 Agus mar sin má táimid ag dul a chur isteach áit ar bith ach an deireadh eagar, 37 00:01:41,170 --> 00:01:43,590 go dócha nach chomh mór sin. 38 00:01:43,590 --> 00:01:46,710 >> Mar an gcéanna, a scriosadh, ach amháin má tá muid scriosadh ó dheireadh na eagar, 39 00:01:46,710 --> 00:01:49,810 Is dócha freisin nach mór mar sin má nach bhfuil muid ag iarraidh a fhágáil bearnaí folamh, 40 00:01:49,810 --> 00:01:50,790 a ghnáth ní dhéanaimid. 41 00:01:50,790 --> 00:01:54,700 Is mian linn a bhaint gné, agus ansin saghas a dhéanamh snug sé arís. 42 00:01:54,700 --> 00:01:57,670 Agus mar sin a scriosadh eilimintí ó sraith, freisin nach mór mar sin. 43 00:01:57,670 --> 00:01:58,820 >> Lookup, cé go bhfuil, go hiontach. 44 00:01:58,820 --> 00:02:00,920 Ní mór dúinn rochtain randamach, Lookup am tairiseach. 45 00:02:00,920 --> 00:02:03,800 Táimid ag rá ach seacht, agus a théann muid go eagar athlonnú seacht. 46 00:02:03,800 --> 00:02:05,907 Deirimid 20, le dul chun eagar athlonnú 20. 47 00:02:05,907 --> 00:02:07,240 Nach bhfuil againn a iterate trasna. 48 00:02:07,240 --> 00:02:08,630 Sin maith go leor. 49 00:02:08,630 --> 00:02:11,020 >> Tá arrays freisin sách éasca a shórtáil. 50 00:02:11,020 --> 00:02:14,040 Gach uair a labhair muid faoi sórtáil algartam, ar nós saghas roghnú, 51 00:02:14,040 --> 00:02:18,820 saghas a chur isteach, mboilgeog a shórtáil, chumasadh a shórtáil, a úsáid le linn i gcónaí arrays chun é a dhéanamh, 52 00:02:18,820 --> 00:02:21,860 mar go bhfuil arrays furasta go leor a saghas, i gcomparáid leis an struchtúir sonraí 53 00:02:21,860 --> 00:02:22,970 againn le feiceáil go dtí seo. 54 00:02:22,970 --> 00:02:24,320 >> Tá siad freisin réasúnta beag. 55 00:02:24,320 --> 00:02:25,695 Ní Tá a lán de spás breise. 56 00:02:25,695 --> 00:02:29,210 Atá leagtha tú díreach leataobh díreach oiread agus mar is gá duit a shealbhú do shonraí, 57 00:02:29,210 --> 00:02:30,320 agus sin go leor i bhfad é. 58 00:02:30,320 --> 00:02:33,180 Mar sin, tá siad deas beag agus éifeachtach sa tslí sin. 59 00:02:33,180 --> 00:02:36,000 Ach downside eile, áfach, Is go bhfuil siad socraithe i méid. 60 00:02:36,000 --> 00:02:38,630 Ní mór dúinn a dhearbhú go cruinn conas mór, ba mhaith linn ár n-sraith a bheith, 61 00:02:38,630 --> 00:02:39,940 agus táimid ag a fháil ach amháin lámhaigh ar sé. 62 00:02:39,940 --> 00:02:41,280 Ní féidir linn ag fás agus Laghdaigh sé. 63 00:02:41,280 --> 00:02:44,582 >> Más gá dúinn chun fás nó a Laghdaigh sé, táimid ag Ní mór a dhearbhú le sraith iomlán nua, 64 00:02:44,582 --> 00:02:47,750 cóip gach ceann de na gnéithe de na an chéad sraith isteach sa dara sraith. 65 00:02:47,750 --> 00:02:51,410 Agus má miscalculated muid go am, ní mór dúinn a dhéanamh arís. 66 00:02:51,410 --> 00:02:52,760 Ní mór mar sin. 67 00:02:52,760 --> 00:02:58,750 Mar sin ní gá arrays a thabhairt dúinn an tsolúbthacht go bhfuil líon athróg na n-eilimintí. 68 00:02:58,750 --> 00:03:01,320 >> Le liosta nasctha, Tá a chur isteach éasca go leor. 69 00:03:01,320 --> 00:03:03,290 Táimid ag tack díreach isteach ar an tosaigh. 70 00:03:03,290 --> 00:03:04,892 Tá a scriosadh freisin éasca go leor. 71 00:03:04,892 --> 00:03:06,100 Ní mór dúinn teacht ar na heilimintí. 72 00:03:06,100 --> 00:03:07,270 A mbíonn baint éigin cuardach. 73 00:03:07,270 --> 00:03:10,270 >> Ach nuair a tá tú ag fáil an eilimint bhfuil tú ag lorg, go léir is gá duit a dhéanamh 74 00:03:10,270 --> 00:03:12,830 Is athrú pointeoir, b'fhéidir dhá má tá tú 75 00:03:12,830 --> 00:03:15,151 a nasctha list-- ar doubly liosta nasctha, rather-- 76 00:03:15,151 --> 00:03:16,650 agus ansin is féidir leat saor in aisce go díreach an nód. 77 00:03:16,650 --> 00:03:18,399 Ní gá duit a athrú gach rud timpeall. 78 00:03:18,399 --> 00:03:22,090 Leat athrú ach dhá threo, mar sin tá go leor tapaidh. 79 00:03:22,090 --> 00:03:23,470 >> Tá Lookup olc áfach, ceart? 80 00:03:23,470 --> 00:03:26,280 Chun go mbeimid chun teacht ar an eilimint i liosta nasctha, 81 00:03:26,280 --> 00:03:29,154 cibé acu gceann agus ina gceann nó doubly nasctha, ní mór dúinn a líneach cuardaigh sé. 82 00:03:29,154 --> 00:03:32,320 Ní mór dúinn tús a chur ag an tús agus bogadh an deireadh, nó tús a chur ag deireadh an t-aistriú 83 00:03:32,320 --> 00:03:33,860 go dtí an tús. 84 00:03:33,860 --> 00:03:35,474 Ní chuirimid bhfuil rochtain randamach níos mó. 85 00:03:35,474 --> 00:03:37,265 Mar sin, má táimid ag déanamh a a lán de chuardach, b'fhéidir 86 00:03:37,265 --> 00:03:39,830 Ní liosta nasctha go leor mar sin maith dúinn. 87 00:03:39,830 --> 00:03:43,750 >> Tá siad freisin i ndáiríre deacair a shórtáil, ceart? 88 00:03:43,750 --> 00:03:45,666 An bealach amháin is féidir leat i ndáiríre shórtáil liosta nasctha 89 00:03:45,666 --> 00:03:47,870 is a shórtáil sé mar thógáil tú é. 90 00:03:47,870 --> 00:03:50,497 Ach má tá tú shórtáil sé mar atá tú thógáil é, tá tú a thuilleadh 91 00:03:50,497 --> 00:03:51,830 ag déanamh insertions tapaidh níos mó. 92 00:03:51,830 --> 00:03:53,746 Nach bhfuil tú ag tacking ach rudaí isteach ar an tosaigh. 93 00:03:53,746 --> 00:03:55,710 Tá tú chun teacht ar an bhfód i gceart a chur air, 94 00:03:55,710 --> 00:03:57,820 agus ansin do chur isteach thiocfaidh chun bheith díreach faoi chomh dona 95 00:03:57,820 --> 00:03:59,390 mar leanas a chur isteach i eagar. 96 00:03:59,390 --> 00:04:03,130 Mar sin, nach bhfuil nasctha liostaí chomh mór le haghaidh sonraí a shórtáil. 97 00:04:03,130 --> 00:04:05,830 >> Tá siad freisin go leor beag, méid-ciallmhar. 98 00:04:05,830 --> 00:04:08,496 Liosta doubly nasctha beagán níos mó ná liostaí nasctha ina n-aonar, 99 00:04:08,496 --> 00:04:10,620 atá beagán níos mó ná arrays, ach nach bhfuil sé 100 00:04:10,620 --> 00:04:13,330 méid ollmhór de spás amú. 101 00:04:13,330 --> 00:04:18,730 Mar sin má tá an spás ar phréimh, ach Ní préimh i ndáiríre dian, 102 00:04:18,730 --> 00:04:22,180 D'fhéadfadh sé seo a bheith ar an mbealach ceart dul. 103 00:04:22,180 --> 00:04:23,330 >> Táblaí hash. 104 00:04:23,330 --> 00:04:25,850 A chur isteach i dtábla hash Is simplí go leor. 105 00:04:25,850 --> 00:04:26,980 Tá sé ina próiseas dhá chéim. 106 00:04:26,980 --> 00:04:30,700 An Chéad ní mór dúinn a rith ár sonraí trí feidhm hash a fháil cód hash, 107 00:04:30,700 --> 00:04:37,550 agus ansin táimid ag cuir isteach an eilimint isteach sa tábla hash ag an suíomh cód hash. 108 00:04:37,550 --> 00:04:40,879 >> Scriosadh, cosúil leis an liosta a nasctha, Is éasca aon uair amháin a fhaigheann tú an eilimint. 109 00:04:40,879 --> 00:04:43,170 Tá tú chun é a fháil ar dtús, ach ansin nuair a scriosadh tú é, 110 00:04:43,170 --> 00:04:45,128 is gá duit ach a mhalartú cúpla leideanna, 111 00:04:45,128 --> 00:04:47,250 má tá tú ag baint úsáide as shlabhrú ar leith. 112 00:04:47,250 --> 00:04:49,942 Má tú ag baint úsáide deacra, nó mura bhfuil tú 113 00:04:49,942 --> 00:04:51,650 ag baint úsáide as shlabhrú ar chor ar bith i do tábla hash, 114 00:04:51,650 --> 00:04:53,040 Tá a scriosadh i ndáiríre i ndáiríre éasca. 115 00:04:53,040 --> 00:04:57,134 Gach gá duit a dhéanamh ná hash an sonraí, agus ansin téigh go dtí an suíomh sin. 116 00:04:57,134 --> 00:04:58,925 Agus ag glacadh leis nach bhfuil tú tá aon imbhuailtí, 117 00:04:58,925 --> 00:05:01,650 beidh tú in ann a scriosadh go han-tapa. 118 00:05:01,650 --> 00:05:04,930 >> Anois, tá Lookup i gcás ina rudaí a fháil beagán níos casta. 119 00:05:04,930 --> 00:05:06,910 Tá sé ar an meán níos fearr ná liostaí nasctha. 120 00:05:06,910 --> 00:05:09,560 Má tú ag baint úsáide shlabhrú, tá tú fós le liosta nasctha, 121 00:05:09,560 --> 00:05:13,170 rud a chiallaíonn go bhfuil tú fós ar an cuardach aimhleasa liosta nasctha. 122 00:05:13,170 --> 00:05:18,390 Ach toisc go bhfuil tú ag cur do nasctha liosta agus scoilteadh sé os cionn 100 nó 1,000 123 00:05:18,390 --> 00:05:25,380 nó n-eilimintí i do tábla hash, tá tú Tá liostaí nasctha go léir ar cheann nú an méid. 124 00:05:25,380 --> 00:05:27,650 Tá siad ar fad i bhfad níos lú. 125 00:05:27,650 --> 00:05:32,080 Tá tú liostaí nasctha n ina ionad de liosta nasctha ar cheann de mhéid n. 126 00:05:32,080 --> 00:05:34,960 >> Agus mar sin i gcónaí seo fíor-domhan fachtóir, a bhfuil muid go ginearálta 127 00:05:34,960 --> 00:05:39,730 nach labhairt faoi i gcastacht am, sé dhéanann a dhéanamh i ndáiríre difríocht a anseo. 128 00:05:39,730 --> 00:05:43,020 Mar sin, tá Lookup fós líneach cuardaigh má tá tú ag baint úsáide as shlabhrú, 129 00:05:43,020 --> 00:05:46,780 ach fad an liosta bhfuil tú ag cuardach trí 130 00:05:46,780 --> 00:05:50,080 Tá an-, an-ghearr i gcomparáid. 131 00:05:50,080 --> 00:05:52,995 Arís, má tá sórtáil do sprioc anseo, hash tábla ar 132 00:05:52,995 --> 00:05:54,370 is dócha nach bhfuil ar an mbealach ceart dul. 133 00:05:54,370 --> 00:05:56,830 Just a úsáid le sraith má sórtáil i ndáiríre tábhachtach a thabhairt duit. 134 00:05:56,830 --> 00:05:58,590 >> Agus is féidir leo a reáchtáil an gamut na méid. 135 00:05:58,590 --> 00:06:01,640 Tá sé deacair a rá cé acu a Tá tábla hash beag nó mór, 136 00:06:01,640 --> 00:06:04,110 toisc go mbraitheann sé i ndáiríre ar cé chomh mór é do tábla hash. 137 00:06:04,110 --> 00:06:07,340 Má tá tú ag dul ach a bheith stóráil cúig eilimintí i do tábla hash, 138 00:06:07,340 --> 00:06:10,620 agus tá tú tábla hash le 10,000 heilimintí ann, 139 00:06:10,620 --> 00:06:12,614 bhfuil tú ag wasting is dócha a lán de spás. 140 00:06:12,614 --> 00:06:15,030 Codarsnacht bheith féidir leat chomh maith tá táblaí hash an-dlúth, 141 00:06:15,030 --> 00:06:18,720 ach faigheann an níos lú do tábla hash, an níos faide gach ceann de na liostaí sin atá nasctha 142 00:06:18,720 --> 00:06:19,220 Faigheann. 143 00:06:19,220 --> 00:06:22,607 Agus mar sin aon bhealach a shainmhíniú ann i ndáiríre go díreach ar an méid de tábla hash, 144 00:06:22,607 --> 00:06:24,440 ach tá sé sábháilte is dócha a rá go bhfuil sé go ginearálta 145 00:06:24,440 --> 00:06:27,990 ag dul a bheith níos mó ná nasctha liosta a stóráil ar na sonraí céanna, 146 00:06:27,990 --> 00:06:30,400 ach níos lú ná Trie. 147 00:06:30,400 --> 00:06:32,720 >> Agus tá iarracht an ceathrú de na struchtúir 148 00:06:32,720 --> 00:06:34,070 go atá muid ag caint faoi. 149 00:06:34,070 --> 00:06:36,450 A chur isteach i i Trie is casta. 150 00:06:36,450 --> 00:06:38,400 Níl a lán de dinimiciúil leithdháileadh cuimhne, 151 00:06:38,400 --> 00:06:40,780 go háirithe ag an tús, mar atá tú ag tosú a thógáil. 152 00:06:40,780 --> 00:06:43,700 Ach tá sé in am tairiseach. 153 00:06:43,700 --> 00:06:47,690 Tá sé ach an eilimint dhaonna anseo go ndéanann tricky é. 154 00:06:47,690 --> 00:06:53,250 Ag a bhíonn pointeoir null, malloc spás, dul ann, spás, b'fhéidir malloc 155 00:06:53,250 --> 00:06:54,490 ó ann arís. 156 00:06:54,490 --> 00:06:58,880 An saghas fachtóir imeaglú leideanna i leithdháileadh cuimhne dinimiciúil 157 00:06:58,880 --> 00:07:00,130 Is é an hurdle a ghlanadh. 158 00:07:00,130 --> 00:07:04,550 Ach nuair a tá tú ag glanadh é, leanas a chur isteach iarbhír a thagann simplí go leor, 159 00:07:04,550 --> 00:07:06,810 agus tá sé cinnte am tairiseach. 160 00:07:06,810 --> 00:07:07,680 >> Is scriosadh éasca. 161 00:07:07,680 --> 00:07:11,330 Gach gá duit a dhéanamh ná nascleanúint síos cúpla leideanna agus saor in aisce ar an nód, 162 00:07:11,330 --> 00:07:12,420 mar sin tá go maith go leor. 163 00:07:12,420 --> 00:07:13,930 Tá Lookup freisin go leor go tapa. 164 00:07:13,930 --> 00:07:16,780 Tá sé seo bunaithe ach amháin ar an fad do chuid sonraí. 165 00:07:16,780 --> 00:07:19,924 Mar sin, má tá gach ceann de do shonraí cúig teaghráin carachtar, 166 00:07:19,924 --> 00:07:22,590 mar shampla, tá tú ag a stóráil cúig teaghráin carachtar i do Trie, 167 00:07:22,590 --> 00:07:25,439 thógann sé ach cúig céimeanna a teacht ar cad tá tú ag lorg. 168 00:07:25,439 --> 00:07:28,480 Is cúig ach ina fhachtóir tairiseach, mar sin arís, a chur isteach, scriosadh, agus a chuardach 169 00:07:28,480 --> 00:07:31,670 tá anseo am ar fad tairiseach, go héifeachtach. 170 00:07:31,670 --> 00:07:34,880 >> Tá rud eile go bhfuil do Trie iarbhír curtha in eagar de chineál ar cheana, ceart? 171 00:07:34,880 --> 00:07:36,800 De bhua an gcaoi bhfuil muid eilimintí a chur isteach, 172 00:07:36,800 --> 00:07:40,060 trí litir ag dul trí litir an eochair, nó trí dhigit dhigit an eochair, 173 00:07:40,060 --> 00:07:45,084 de ghnáth, chríochnaíonn do Trie suas a bheith de chineál ar curtha in eagar mar a thógáil tú é. 174 00:07:45,084 --> 00:07:47,250 Ní chuireann sé a dhéanann i ndáiríre ciall chun smaoineamh ar sórtáil 175 00:07:47,250 --> 00:07:49,874 ar an mbealach céanna a cheapann againn faoi sé le arrays, nó liostaí nasctha, 176 00:07:49,874 --> 00:07:51,070 nó táblaí hash. 177 00:07:51,070 --> 00:07:54,780 Ach i roinnt chiall, do Trie Tá curtha in eagar mar a théann tú. 178 00:07:54,780 --> 00:07:58,630 >> An downside, ar ndóigh, go a thiocfaidh chun bheith go tapa Trie ollmhór. 179 00:07:58,630 --> 00:08:02,970 Ó gach pointe acomhal, d'fhéadfadh tú have-- más é atá do eochair dhigit, 180 00:08:02,970 --> 00:08:04,880 tá tú 10 eile áiteanna is féidir leat dul, a 181 00:08:04,880 --> 00:08:07,490 Ciallaíonn sé sin gach nód Tá faisnéis 182 00:08:07,490 --> 00:08:11,440 faoi ​​na sonraí is mian leat a stóráil ag an nód, móide 10 leideanna. 183 00:08:11,440 --> 00:08:14,430 Cé acu, ar CS50 IDE é, 80 bytes. 184 00:08:14,430 --> 00:08:17,220 Mar sin tá sé ar a laghad 80 bytes le haghaidh gach nód a chruthú duit, 185 00:08:17,220 --> 00:08:19,240 agus ní ar sin comhaireamh fiú sonraí. 186 00:08:19,240 --> 00:08:24,950 Agus má tá do nóid litreacha in ionad na dhigit, 187 00:08:24,950 --> 00:08:27,825 anois tá tú 26 leideanna ó gach suíomh. 188 00:08:27,825 --> 00:08:32,007 Agus 26 uair 8 Is dócha 200 bytes, nó rud éigin mar sin. 189 00:08:32,007 --> 00:08:33,840 Agus tá tú caipitil agus lowercase-- is féidir leat 190 00:08:33,840 --> 00:08:35,381 a fheiceáil nuair mé ag dul leis seo, ceart? 191 00:08:35,381 --> 00:08:37,500 Is féidir le do nóid fháil i ndáiríre mór, agus mar sin an Trie 192 00:08:37,500 --> 00:08:40,470 féin, tríd is tríd is féidir, fháil i ndáiríre mór, freisin. 193 00:08:40,470 --> 00:08:42,630 Mar sin má tá an spás ar ard phréimh ar do chóras, 194 00:08:42,630 --> 00:08:45,830 ní a d'fhéadfadh a bheith ar Trie ar an mbealach ceart chun dul, cé na tairbhí eile 195 00:08:45,830 --> 00:08:47,780 a thagann i spraoi. 196 00:08:47,780 --> 00:08:48,710 Tá mé Doug Lloyd. 197 00:08:48,710 --> 00:08:50,740 Is é seo an CS50. 198 00:08:50,740 --> 00:08:52,316