1 00:00:00,000 --> 00:00:07,700 2 00:00:07,700 --> 00:00:10,890 >> KEVIN Schmid: Uaireanta, nuair a thógáil clár, b'fhéidir gur mhaith leat a úsáid a bhaint as 3 00:00:10,890 --> 00:00:13,190 struchtúr sonraí ar a dtugtar foclóir. 4 00:00:13,190 --> 00:00:17,960 A eochracha léarscáileanna foclóir, atá teaghráin de ghnáth, do luachanna, ints, 5 00:00:17,960 --> 00:00:21,900 carachtair, pointeoir le roinnt réad, is cuma cad ba mhaith linn. 6 00:00:21,900 --> 00:00:26,510 Tá sé díreach cosúil le foclóirí ngnáthnós focail léarscáil trí shainmhínithe. 7 00:00:26,510 --> 00:00:29,440 >> A chur ar fáil Foclóirí dúinn leis an cumas chun faisnéis a stóráil 8 00:00:29,440 --> 00:00:32,750 bhaineann le rud éigin agus é a breathnú suas níos déanaí. 9 00:00:32,750 --> 00:00:36,620 Mar sin, conas is féidir linn a chur i bhfeidhm i ndáiríre foclóir i, a rá, C cód gur féidir linn 10 00:00:36,620 --> 00:00:38,460 úsáid i gceann dár gcláir? 11 00:00:38,460 --> 00:00:41,790 Bhuel, tá a lán de na bealaí gur d'fhéadfadh muid foclóir a chur i bhfeidhm. 12 00:00:41,790 --> 00:00:45,930 >> I gcás amháin, d'fhéadfadh muid a úsáid le sraith go bhfuil muid dinimiciúil ath-mhéid nó a d'fhéadfadh muid a úsáid 13 00:00:45,930 --> 00:00:49,150 liosta nasctha, tábla hash nó crann dénártha. 14 00:00:49,150 --> 00:00:52,250 Ach is cuma cad a roghnaíonn againn, ba chóir dúinn a bheith aireach ar an éifeachtúlacht agus 15 00:00:52,250 --> 00:00:54,300 feidhmíocht chur chun feidhme. 16 00:00:54,300 --> 00:00:57,930 Ba chóir dúinn smaoineamh ar an algartam a úsáidtear a chur isteach agus a breathnú suas míreanna i 17 00:00:57,930 --> 00:00:59,120 ár struchtúr sonraí. 18 00:00:59,120 --> 00:01:03,060 >> Chun anois, a ligean ar glacadh leis go bhfuil muid ag ag iarraidh a teaghráin a úsáid mar eochracha. 19 00:01:03,060 --> 00:01:07,290 A ligean ar labhairt faoi an bhféidearthacht amháin, struchtúr sonraí a dtugtar trie. 20 00:01:07,290 --> 00:01:11,210 Mar sin, tá anseo dearc de trie. 21 00:01:11,210 --> 00:01:14,590 >> Mar a léiríonn an pictiúr, le trie Tá struchtúr crann le sonraí a 22 00:01:14,590 --> 00:01:16,050 nóid nasctha le chéile. 23 00:01:16,050 --> 00:01:19,420 Feicimid go bhfuil fhréamh ann go soiléir nód le roinnt naisc a leathnú go dtí 24 00:01:19,420 --> 00:01:20,500 nóid eile. 25 00:01:20,500 --> 00:01:23,040 Ach cad a dhéanann gach nód comhdhéanta de? 26 00:01:23,040 --> 00:01:26,700 Má glacaimid go bhfuil muid eochracha a stóráil le carachtair aibítreacha amháin, agus 27 00:01:26,700 --> 00:01:30,150 ní féidir linn cúram faoi caipitlithe, anseo tá sainmhíniú ar nód a 28 00:01:30,150 --> 00:01:31,100 is leor. 29 00:01:31,100 --> 00:01:34,130 >> Tá réad a bhfuil a gcineál struct Tá nód dhá chuid 30 00:01:34,130 --> 00:01:35,740 ar a dtugtar sonraí agus leanaí. 31 00:01:35,740 --> 00:01:39,200 Táimid tar éis d'fhág an chuid sonraí mar a comment a chur in ionad comhpháirt 32 00:01:39,200 --> 00:01:43,190 dearbhú nuair a bhíonn nód struct ionchorprú i gclár C. 33 00:01:43,190 --> 00:01:47,040 D'fhéadfadh an chuid sonraí de nód a bheith ina Luach Boole a chur in iúl cibé acu atá nó 34 00:01:47,040 --> 00:01:51,160 Léiríonn nach bhfuil an nód críochnú de eochair foclóir nó d'fhéadfadh sé a bheith ina 35 00:01:51,160 --> 00:01:54,240 teaghrán ionadaíonn an sainmhíniú de focal san fhoclóir. 36 00:01:54,240 --> 00:01:58,870 >> Beidh muid úsáid ar aghaidh smiley a chur in iúl nuair a bhíonn sonraí i láthair i nód. 37 00:01:58,870 --> 00:02:02,310 Tá 26 eilimintí i ár páistí sraith, innéacs amháin 38 00:02:02,310 --> 00:02:03,690 in aghaidh an litir. 39 00:02:03,690 --> 00:02:06,570 Beidh muid a fheiceáil ar an tábhacht seo go luath. 40 00:02:06,570 --> 00:02:10,759 >> A ligean ar a fháil breathnú níos dlúithe ar an nód fréimhe inár léaráid, nach bhfuil aon sonraí 41 00:02:10,759 --> 00:02:14,740 a bhaineann leis, mar atá léirithe ag an éagmais an duine smiley sa 42 00:02:14,740 --> 00:02:16,110 chuid sonraí. 43 00:02:16,110 --> 00:02:19,910 Na saigheada a shíneann ó na codanna den Léiríonn na páistí sraith neamh-nód 44 00:02:19,910 --> 00:02:21,640 leideanna le nóid eile. 45 00:02:21,640 --> 00:02:25,500 Mar shampla, an arrow a shíneann ó an dara gné de leanaí 46 00:02:25,500 --> 00:02:28,400 Léiríonn an litir B i eochair fhoclóir. 47 00:02:28,400 --> 00:02:31,920 Agus sa léaráid níos mó lipéad dúinn é le B. 48 00:02:31,920 --> 00:02:35,810 >> Tabhair faoi deara gur sa léaráid mó, nuair a muid tharraingt pointeoir chuig nód eile, é a 49 00:02:35,810 --> 00:02:39,100 nach ábhar i gcás an rinn saighde Buaileann an nód eile. 50 00:02:39,100 --> 00:02:43,850 Tá ár sampla foclóir trie dhá fhocal, go agus súmáil. 51 00:02:43,850 --> 00:02:47,040 A ligean ar siúl trí shampla de breathnú suas sonraí le haghaidh eochair. 52 00:02:47,040 --> 00:02:50,800 >> Cuir bhíomar ag iarraidh chun breathnú suas ar an luach comhfhreagrach don folctha eochair. 53 00:02:50,800 --> 00:02:53,610 Beidh muid tús a chur lenár breathnú suas ag an nód fhréamh. 54 00:02:53,610 --> 00:02:57,870 Ansin, beidh muid a chur ar an chéad litir ar ár eochair, B, agus teacht ar an comhfhreagrach 55 00:02:57,870 --> 00:03:00,020 láthair in ár sraith bpáistí. 56 00:03:00,020 --> 00:03:04,490 Tabhair faoi deara go bhfuil go díreach 26 spotaí in eagar, ceann amháin do gach litir 57 00:03:04,490 --> 00:03:05,330 an aibítir. 58 00:03:05,330 --> 00:03:08,800 Agus beidh orainn ionadaíocht a dhéanamh ar spotaí an litreacha na haibítre in ord. 59 00:03:08,800 --> 00:03:13,960 >> Beidh muid ag breathnú ar an dara innéacs ansin, innéacs amháin, do B. Go ginearálta, má táimid 60 00:03:13,960 --> 00:03:17,990 go bhfuil roinnt aibítreach carachtar C againn D'fhéadfadh a chinneadh an láthair comhfhreagrach 61 00:03:17,990 --> 00:03:21,520 in eagar leanaí ag baint úsáide ríomh mar seo. 62 00:03:21,520 --> 00:03:25,140 D'fhéadfadh muid a bheith in úsáid le páistí níos mó eagar má bhíomar ag iarraidh a thairiscint breathnú suas ar 63 00:03:25,140 --> 00:03:28,380 eochracha le raon níos leithne de charachtair, mar shampla an fad 64 00:03:28,380 --> 00:03:29,880 Carachtar ASCII a leagan síos. 65 00:03:29,880 --> 00:03:32,630 >> Sa chás seo, an pointeoir in ár sraith páistí ag 66 00:03:32,630 --> 00:03:34,320 Ní innéacs amháin null. 67 00:03:34,320 --> 00:03:36,600 Mar sin, beidh muid ag leanúint ar aghaidh ag lorg suas an folctha eochair. 68 00:03:36,600 --> 00:03:40,130 Má bhíonn muid riamh pointeoir nialasach ag an láthair ceart i do na páistí 69 00:03:40,130 --> 00:03:43,230 eagar cé trasnaithe againn ar an nóid, ansin beidh orainn a rá go bhfuil muid 70 00:03:43,230 --> 00:03:45,630 Ní fhéadfaí aon rud don eochair sin a aimsiú. 71 00:03:45,630 --> 00:03:49,370 >> Anois, beidh orainn a chur ar an dara litir ár n-eochair, A, agus leanúint ar aghaidh a leanas 72 00:03:49,370 --> 00:03:52,400 leideanna ar an mbealach seo go dtí go againn teacht ar an deireadh ár eochair. 73 00:03:52,400 --> 00:03:56,530 Má shroicheann muid deireadh an eochair gan ag bualadh aon foircinn marbh, leideanna null, 74 00:03:56,530 --> 00:03:59,730 mar go bhfuil an cás anseo, ansin dúinn ach a sheiceáil ach rud amháin níos mó. 75 00:03:59,730 --> 00:04:02,110 An bhfuil an eochair i ndáiríre san fhoclóir? 76 00:04:02,110 --> 00:04:07,660 >> Más amhlaidh, ba chóir dúinn a fháil ar luach, go maith le icon aghaidh smiley inár léaráid ina 77 00:04:07,660 --> 00:04:08,750 Críochnaíonn an focal. 78 00:04:08,750 --> 00:04:12,270 Má tá rud éigin eile a stóráil le na sonraí, ansin is féidir linn a thabhairt ar ais é. 79 00:04:12,270 --> 00:04:16,500 Mar shampla, nach bhfuil an zú eochair sa foclóir, cé go raibh muid ábalta a bheith 80 00:04:16,500 --> 00:04:19,810 shroich an deireadh an eochair gan riamh bualadh le pointeoir null, agus muid 81 00:04:19,810 --> 00:04:21,089 iterate trí trie. 82 00:04:21,089 --> 00:04:25,436 >> Má iarracht muid chun breathnú suas ar an folctha eochair, an dara nód seo caite innéacs eagar, 83 00:04:25,436 --> 00:04:28,750 a fhreagraíonn do na litir H, bheadh a bhí i seilbh pointeoir null. 84 00:04:28,750 --> 00:04:31,120 Mar sin, nach bhfuil folctha san fhoclóir. 85 00:04:31,120 --> 00:04:34,800 Agus mar sin tá trie uathúil sa mhéid is go na heochracha Tá riamh stóráil go sainráite sna 86 00:04:34,800 --> 00:04:36,650 an struchtúr sonraí. 87 00:04:36,650 --> 00:04:38,810 Mar sin, conas is féidir linn rud éigin a chur isteach isteach i trie? 88 00:04:38,810 --> 00:04:41,780 >> A ligean ar chur isteach an eochair zú isteach inár trie. 89 00:04:41,780 --> 00:04:46,120 Cuimhnigh go bhfuil ar aghaidh smiley ag nód D'fhéadfadh freagairt cód le simplí 90 00:04:46,120 --> 00:04:50,170 Luach Boole a chur in iúl go zú Is san fhoclóir nó d'fhéadfadh sé 91 00:04:50,170 --> 00:04:53,710 Comhfhreagróidh tuilleadh eolais a fháil go bhfuil muid ar mian leo a chomhlachú leis an zú eochair, 92 00:04:53,710 --> 00:04:56,860 cosúil leis an sainmhíniú ar an focal nó rud éigin eile. 93 00:04:56,860 --> 00:05:00,350 I roinnt bealaí, an próiseas a chur isteach Tá rud éigin i trie cosúil leis 94 00:05:00,350 --> 00:05:02,060 ag breathnú suas rud éigin i trie. 95 00:05:02,060 --> 00:05:05,720 >> Beidh muid tús a chur leis an nód fréimhe arís, leideanna seo a leanas a fhreagraíonn do 96 00:05:05,720 --> 00:05:07,990 na litreacha ar ár eochair. 97 00:05:07,990 --> 00:05:11,310 Luckily, bhí muid in ann leideanna a leanúint léir ar an mbealach go dtí gur shroich muid 98 00:05:11,310 --> 00:05:12,770 an deireadh an eochair. 99 00:05:12,770 --> 00:05:16,480 Ós rud é zú réimír an focal súmáil, atá ina bhall den 100 00:05:16,480 --> 00:05:19,440 foclóir, ní mór dúinn a leithdháileadh aon nóid nua. 101 00:05:19,440 --> 00:05:23,140 >> Is féidir linn a mhodhnú ar an nód a chur in iúl go an chonair na carachtair as a 102 00:05:23,140 --> 00:05:25,360 léiríonn sé ár foclóir eochair. 103 00:05:25,360 --> 00:05:28,630 Anois, a ligean ar iarracht tríd an eochair folctha isteach sa trie. 104 00:05:28,630 --> 00:05:32,260 Beidh muid ag tosú ag an nód fréimhe agus leideanna a leanúint arís. 105 00:05:32,260 --> 00:05:35,620 Ach sa chás seo, bhuail muid marbh deireadh sula bhfuil muid in ann a fháil chun an 106 00:05:35,620 --> 00:05:36,940 deireadh an eochair. 107 00:05:36,940 --> 00:05:40,980 Anois, beidh orainn gá a leithdháileadh roinnt nua Beidh gá nóid a nua amháin a leithdháileadh 108 00:05:40,980 --> 00:05:43,660 nód le haghaidh gach eile litir ár eochair. 109 00:05:43,660 --> 00:05:46,740 >> Sa chás seo, ní mór dúinn ach a leithdháileadh nód nua amháin. 110 00:05:46,740 --> 00:05:50,590 Ansin, beidh orainn gá a dhéanamh ar an innéacs H tagairt an nód nua seo. 111 00:05:50,590 --> 00:05:54,070 Arís eile, is féidir linn a mhodhnú an nód a le fios go an chonair na carachtair 112 00:05:54,070 --> 00:05:57,120 as a dtiocfaidh sé ionann eochair i ár foclóir. 113 00:05:57,120 --> 00:06:00,730 A ligean ar réasúnú faoin asymptotic chastacht ár nósanna imeachta chun na 114 00:06:00,730 --> 00:06:02,110 dá n-oibríochtaí. 115 00:06:02,110 --> 00:06:06,420 >> Faoi deara go sa dá chás ar an líon d'céimeanna ár algartam thóg a bhí 116 00:06:06,420 --> 00:06:09,470 comhréireach leis an líon litreacha sa eochairfhocal. 117 00:06:09,470 --> 00:06:10,220 Sin ceart. 118 00:06:10,220 --> 00:06:13,470 Nuair is mian leat chun breathnú suas le focal i trie is gá duit ach a iterate trí 119 00:06:13,470 --> 00:06:17,100 na litreacha ceann ar cheann go dtí go tú ceachtar teacht ar an deireadh an fhocail nó 120 00:06:17,100 --> 00:06:19,060 bhuail ar deireadh marbh sa trie. 121 00:06:19,060 --> 00:06:22,470 >> Agus nuair is mian leat a chur isteach eochair luach péire isteach trie baint úsáide as an 122 00:06:22,470 --> 00:06:26,250 imeachta a phlé againn, an cás is measa beidh tú a leithdháileadh nód nua 123 00:06:26,250 --> 00:06:27,550 do gach litir. 124 00:06:27,550 --> 00:06:31,290 Agus beidh muid ag glacadh leis go bhfuil leithdháileadh Is oibríocht am tairiseach. 125 00:06:31,290 --> 00:06:35,850 Mar sin, má glacadh againn go bhfuil an fad eochrach atá teorantach le tairiseach seasta, déantar na 126 00:06:35,850 --> 00:06:39,400 Tá isteach agus breathnú suas tairiseach oibríochtaí ama le haghaidh trie. 127 00:06:39,400 --> 00:06:42,930 >> Más rud é nach bhfuil muid a dhéanamh ar an toimhde go Is é an fad eochrach atá teorantach le seasta 128 00:06:42,930 --> 00:06:46,650 tairiseach, ansin a chur isteach agus a breathnú suas, i gcás is measa, tá líneach i 129 00:06:46,650 --> 00:06:48,240 fad an eochair. 130 00:06:48,240 --> 00:06:51,800 Fógra go bhfuil líon na n-ítimí a stóráil sa trie ní dhéanann sé difear an cuma ar bun 131 00:06:51,800 --> 00:06:52,820 nó am a chur isteach. 132 00:06:52,820 --> 00:06:55,360 Tá sé tionchar ach amháin ag an fad an eochair. 133 00:06:55,360 --> 00:06:59,300 >> I gcodarsnacht leis sin, iontrálacha a chur leis, a rá, Is nós le tábla hash a dhéanamh 134 00:06:59,300 --> 00:07:01,250 amach anseo breathnú suas níos moille. 135 00:07:01,250 --> 00:07:04,520 Cé go d'fhéadfadh sé seo fuaime achomharc ar dtús, ba chóir dúinn a choinneáil i gcuimhne go bhfuil 136 00:07:04,520 --> 00:07:08,740 Ní dhéanann castacht asymptotic fabhrach chiallaíonn go bhfuil i gcleachtas na sonraí 137 00:07:08,740 --> 00:07:11,410 Tá struchtúr gá thar reproach. 138 00:07:11,410 --> 00:07:15,860 Ní mór dúinn a mheas freisin go bhfuil a stóráil ar focal i trie is gá dúinn, i an ceann is measa 139 00:07:15,860 --> 00:07:19,700 cás, roinnt nóid comhréireach le fad an focal féin. 140 00:07:19,700 --> 00:07:21,880 >> Claonadh iarracht a úsáid a lán de spás. 141 00:07:21,880 --> 00:07:25,620 Sin i gcodarsnacht le tábla hash, nuair is gá dúinn ach nód nua amháin 142 00:07:25,620 --> 00:07:27,940 stóráil roinnt péire eochair luach. 143 00:07:27,940 --> 00:07:31,370 Anois, arís go teoiriciúil, spás mór Ní tomhaltas cosúil mhaith mór 144 00:07:31,370 --> 00:07:34,620 déileáil, go háirithe ós rud é go nua-aimseartha Tá ríomhairí ghigibheart agus 145 00:07:34,620 --> 00:07:36,180 ghigibheart de chuimhne. 146 00:07:36,180 --> 00:07:39,200 Ach casadh sé amach go bhfuil muid fós a bheith buartha faoi úsáide cuimhne agus 147 00:07:39,200 --> 00:07:42,540 eagraíocht ar mhaithe le feidhmíocht, ós rud é ríomhairí nua-aimseartha 148 00:07:42,540 --> 00:07:46,960 Tá meicníochtaí i bhfeidhm faoi na cochall chun dlús a chur le rochtain chuimhne. 149 00:07:46,960 --> 00:07:51,180 >> Ach oibríonn na meicníochtaí is fearr nuair a rochtana cuimhne a dhéantar i dhlúth 150 00:07:51,180 --> 00:07:52,810 réigiúin nó ceantair. 151 00:07:52,810 --> 00:07:55,910 Agus d'fhéadfadh na nóid a trie cónaí áit ar bith sa gcarn. 152 00:07:55,910 --> 00:07:58,390 Ach tá na trádáil-dícheangail nach mór dúinn a mheas. 153 00:07:58,390 --> 00:08:01,440 >> Cuimhnigh go bhfuil, nuair a roghnú na sonraí struchtúr do thasc áirithe, ní mór dúinn 154 00:08:01,440 --> 00:08:04,420 Ba chóir smaoineamh ar cad é cineál na oibríochtaí is gá an struchtúr sonraí a 155 00:08:04,420 --> 00:08:07,140 tacaíocht agus cé mhéad an fheidhmíocht gach ceann de na 156 00:08:07,140 --> 00:08:09,080 nithe oibríochtaí a chur chugainn. 157 00:08:09,080 --> 00:08:11,300 Féadfaidh na hoibríochtaí fiú leathnú níos faide ná díreach 158 00:08:11,300 --> 00:08:13,430 breathnú bunúsach suas agus a chur isteach. 159 00:08:13,430 --> 00:08:17,010 Cuir bhíomar ag iarraidh a chineál a chur i bhfeidhm na feidhmiúlachta auto-iomlán, i bhfad 160 00:08:17,010 --> 00:08:18,890 mar a dhéanann Google inneall cuardaigh. 161 00:08:18,890 --> 00:08:22,210 Is é sin, ar ais go léir na heochracha agus d'fhéadfadh a luachanna 162 00:08:22,210 --> 00:08:24,130 Tá réimír tugtha. 163 00:08:24,130 --> 00:08:27,050 >> Is trie uathúil úsáideach don oibríocht seo. 164 00:08:27,050 --> 00:08:29,890 Tá sé éasca a iterate trí an trie do gach carachtar ar 165 00:08:29,890 --> 00:08:30,950 an réimír. 166 00:08:30,950 --> 00:08:33,559 Díreach cosúil le breathnú suas oibríocht, d'fhéadfadh muid leideanna a leanúint 167 00:08:33,559 --> 00:08:35,400 carachtar le carachtar. 168 00:08:35,400 --> 00:08:38,659 Ansin, nuair a thagann muid ag deireadh na réimír, d'fhéadfadh muid a iterate trí na 169 00:08:38,659 --> 00:08:42,049 chuid eile den struchtúr sonraí ós rud é aon cheann de na heochracha níos faide 170 00:08:42,049 --> 00:08:43,980 an bpointe seo tá an réimír. 171 00:08:43,980 --> 00:08:47,670 >> Tá sé éasca freisin a fháil seo a liostú in ord aibítre ó 172 00:08:47,670 --> 00:08:50,970 eilimintí den eagar leanaí curtha in ord aibítre. 173 00:08:50,970 --> 00:08:54,420 Mar sin tá súil againn go mbainfidh tú a mheas iarracht a thabhairt triail a bhaint. 174 00:08:54,420 --> 00:08:56,085 Tá mé Kevin Schmid, agus tá sé seo CS50. 175 00:08:56,085 --> 00:08:58,745 176 00:08:58,745 --> 00:09:00,790 >> Ah, is é seo an tús an meath. 177 00:09:00,790 --> 00:09:01,350 Tá brón orm. 178 00:09:01,350 --> 00:09:01,870 Tá brón orm. 179 00:09:01,870 --> 00:09:02,480 Tá brón orm. 180 00:09:02,480 --> 00:09:03,130 Tá brón orm. 181 00:09:03,130 --> 00:09:03,950 >> Stailc ceithre. 182 00:09:03,950 --> 00:09:04,360 Tá mé amach. 183 00:09:04,360 --> 00:09:05,280 Tá brón orm. 184 00:09:05,280 --> 00:09:06,500 Tá brón orm. 185 00:09:06,500 --> 00:09:07,490 Tá brón orm. 186 00:09:07,490 --> 00:09:12,352 Tá brón orainn le haghaidh a dhéanamh ar an duine a Tá a chur in eagar seo a dul ar mire. 187 00:09:12,352 --> 00:09:13,280 >> Tá brón orm. 188 00:09:13,280 --> 00:09:13,880 Tá brón orm. 189 00:09:13,880 --> 00:09:15,080 Tá brón orm. 190 00:09:15,080 --> 00:09:15,680 Tá brón orm. 191 00:09:15,680 --> 00:09:16,280 >> Cainteoir 1: Maith thú. 192 00:09:16,280 --> 00:09:17,530 Sin a rinneadh i ndáiríre go maith. 193 00:09:17,530 --> 00:09:18,430