1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Weithiau, wrth adeiladu
rhaglen, efallai y byddwch am i ddefnyddio

3
00:00:10,890 --> 00:00:13,190
strwythur data a elwir fel geiriadur.

4
00:00:13,190 --> 00:00:17,960
Geiriadur allweddi mapiau, sy'n cael eu
llinynnau fel arfer, i werthoedd, ints,

5
00:00:17,960 --> 00:00:21,900
chars, pwyntydd i ryw gwrthrych,
beth bynnag yr ydym ei eisiau.

6
00:00:21,900 --> 00:00:26,510
Mae'n union fel geiriaduron cyffredin
geiriau sy'n map trwy diffiniadau.

7
00:00:26,510 --> 00:00:29,440
>> Geiriaduron rhoi i ni y
gallu i storio gwybodaeth

8
00:00:29,440 --> 00:00:32,750
gysylltiedig gyda rhywbeth
ac yn edrych i fyny yn ddiweddarach.

9
00:00:32,750 --> 00:00:36,620
Felly, sut rydym yn mewn gwirionedd yn gweithredu
geiriadur mewn, dyweder, C cod y gallwn

10
00:00:36,620 --> 00:00:38,460
defnyddio yn un o'n rhaglenni?

11
00:00:38,460 --> 00:00:41,790
Wel, mae yna lawer o ffyrdd y
gallem weithredu geiriadur.

12
00:00:41,790 --> 00:00:45,930
>> Ar gyfer un, gallem ddefnyddio amrywiaeth ein bod yn
ddeinamig newid maint neu gallem ddefnyddio

13
00:00:45,930 --> 00:00:49,150
rhestr gysylltiedig, bwrdd hash
neu goeden deuaidd.

14
00:00:49,150 --> 00:00:52,250
Ond beth bynnag yr ydym yn dewis, dylem
fod yn ymwybodol o'r effeithlonrwydd ac

15
00:00:52,250 --> 00:00:54,300
perfformiad y gweithredu.

16
00:00:54,300 --> 00:00:57,930
Dylem feddwl am yr algorithm a ddefnyddir
i fewnosod ac yn edrych eitemau i fyny i mewn

17
00:00:57,930 --> 00:00:59,120
ein strwythur data.

18
00:00:59,120 --> 00:01:03,060
>> Am y tro, gadewch i ni gymryd yn ganiataol ein bod yn
am ddefnyddio llinynnau fel allweddi.

19
00:01:03,060 --> 00:01:07,290
Gadewch i ni siarad am un posibilrwydd,
strwythur data a elwir yn trie.

20
00:01:07,290 --> 00:01:11,210
Felly dyma cynrychiolaeth weledol
o trie.

21
00:01:11,210 --> 00:01:14,590
>> Fel y mae'r llun yn awgrymu, yn trie
yn strwythur data coeden gyda

22
00:01:14,590 --> 00:01:16,050
nodau cysylltu â'i gilydd.

23
00:01:16,050 --> 00:01:19,420
Rydym yn gweld fod yna clir gwreiddyn
nod gyda rhai cysylltiadau yn ymestyn i

24
00:01:19,420 --> 00:01:20,500
nodau eraill.

25
00:01:20,500 --> 00:01:23,040
Ond beth mae pob nod yn ei gynnwys?

26
00:01:23,040 --> 00:01:26,700
Os byddwn yn cymryd yn ganiataol ein bod yn storio allweddi
gyda chymeriadau yr wyddor yn unig, a

27
00:01:26,700 --> 00:01:30,150
nid ydym yn poeni am gyfalafu,
dyma diffiniad o nod y

28
00:01:30,150 --> 00:01:31,100
yn ddigon.

29
00:01:31,100 --> 00:01:34,130
>> Mae gwrthrych y mae ei fath yn strwythur
Mae gan nod dwy ran

30
00:01:34,130 --> 00:01:35,740
a elwir data a phlant.

31
00:01:35,740 --> 00:01:39,200
Rydym wedi gadael y rhan data fel sylw
i gael ei ddisodli gan elfen

32
00:01:39,200 --> 00:01:43,190
datganiad pan fydd nod strwythur yn
hymgorffori mewn rhaglen C.

33
00:01:43,190 --> 00:01:47,040
Efallai y bydd y rhan data o nod fod yn
Gwerth boolean i nodi p'un a

34
00:01:47,040 --> 00:01:51,160
nid yw'r nod yn cynrychioli cwblhau
allwedd geiriadur neu gallai fod yn

35
00:01:51,160 --> 00:01:54,240
llinyn cynrychioli'r diffiniad
gair yn y geiriadur.

36
00:01:54,240 --> 00:01:58,870
>> Byddwn yn defnyddio'r wyneb hapus i nodi
pan fydd data yn bresennol mewn nod.

37
00:01:58,870 --> 00:02:02,310
Mae 26 o elfennau yn ein
plant amrywiaeth, un mynegai

38
00:02:02,310 --> 00:02:03,690
bob cymeriad yr wyddor.

39
00:02:03,690 --> 00:02:06,570
Cawn weld arwyddocâd
o hyn yn fuan.

40
00:02:06,570 --> 00:02:10,759
>> Gadewch i ni gael golwg agosach o'r nod gwraidd
yn ein diagram, sydd heb unrhyw ddata

41
00:02:10,759 --> 00:02:14,740
gysylltiedig ag ef, fel y nodir gan y
absenoldeb yr wyneb sy'n gwenu yn y

42
00:02:14,740 --> 00:02:16,110
cyfran data.

43
00:02:16,110 --> 00:02:19,910
Mae'r saethau yn ymestyn o rannau o
yr amrywiaeth plant yn cynrychioli'r di-nod

44
00:02:19,910 --> 00:02:21,640
awgrymiadau i nodau eraill.

45
00:02:21,640 --> 00:02:25,500
Er enghraifft, mae'r saeth yn ymestyn o
ail elfen blant

46
00:02:25,500 --> 00:02:28,400
cynrychioli'r llythyr B
mewn cywair geiriadur.

47
00:02:28,400 --> 00:02:31,920
Ac yn y diagram mwy o faint
rydym yn labelu 'i ag a B.

48
00:02:31,920 --> 00:02:35,810
>> Noder bod yn y diagram mawr, pan fyddwn yn
tynnu pwyntydd i nod arall, mae'n

49
00:02:35,810 --> 00:02:39,100
Nid yw o bwys os yw'r pen saeth
yn cyfarfod y nod eraill.

50
00:02:39,100 --> 00:02:43,850
Mae ein trie geiriadur sampl yn cynnwys
dau air, hynny a chwyddo.

51
00:02:43,850 --> 00:02:47,040
Gadewch i ni gerdded trwy enghraifft o
edrych i fyny data ar gyfer allwedd.

52
00:02:47,040 --> 00:02:50,800
>> Gadewch i ni dybio ein bod yn awyddus i edrych ar y
cyfatebol gwerth ar gyfer y bath allweddol.

53
00:02:50,800 --> 00:02:53,610
Byddwn yn dechrau ein golwg i fyny
yn y nôd gwraidd.

54
00:02:53,610 --> 00:02:57,870
Yna, byddwn yn cymryd y llythyr cyntaf ein
allweddol, B, ac yn dod o hyd i'r cyfatebol

55
00:02:57,870 --> 00:03:00,020
gweld yn ein amrywiaeth plant.

56
00:03:00,020 --> 00:03:04,490
Sylwch fod yna yn union 26 o smotiau
yn yr arae, un ar gyfer pob llythyren o'r

57
00:03:04,490 --> 00:03:05,330
wyddor.

58
00:03:05,330 --> 00:03:08,800
A byddwn yn cael y smotiau yn cynrychioli
llythrennau'r wyddor mewn trefn.

59
00:03:08,800 --> 00:03:13,960
>> Byddwn yn edrych ar yr ail mynegai yna,
mynegai un, ar gyfer B. Yn gyffredinol, os ydym

60
00:03:13,960 --> 00:03:17,990
gael rhywfaint o wyddor gymeriad C rydym
Gallai benderfynu ar y fan a'r lle cyfatebol

61
00:03:17,990 --> 00:03:21,520
yn yr arae plant yn defnyddio
cyfrifiad fel hyn.

62
00:03:21,520 --> 00:03:25,140
Gallem fod wedi defnyddio blant mwy
amrywiaeth os ydym am gynnig edrych i fyny o

63
00:03:25,140 --> 00:03:28,380
allweddi gydag ystod ehangach o gymeriadau,
megis y cyfan

64
00:03:28,380 --> 00:03:29,880
Cymeriad ASCII a osodwyd.

65
00:03:29,880 --> 00:03:32,630
>> Yn yr achos hwn, y pwyntydd
yn ein amrywiaeth plant yn

66
00:03:32,630 --> 00:03:34,320
Nid yw mynegai un yn null.

67
00:03:34,320 --> 00:03:36,600
Felly, byddwn yn parhau yn edrych
i fyny y bath allweddol.

68
00:03:36,600 --> 00:03:40,130
Os ydym erioed wedi dod ar draws pwyntydd null
yn y fan a'r lle priodol yn y plant

69
00:03:40,130 --> 00:03:43,230
amrywiaeth wrth i ni gerdded trwy'r nodau,
Yna, bydd rhaid i ni ddweud ein bod yn

70
00:03:43,230 --> 00:03:45,630
Ni allai ddod o hyd i unrhyw beth am y allweddol.

71
00:03:45,630 --> 00:03:49,370
>> Yn awr, byddwn yn cymryd yr ail lythyr o
ein allweddol, A, ac yn parhau yn dilyn

72
00:03:49,370 --> 00:03:52,400
awgrymiadau yn y ffordd hon nes i ni
cyrraedd diwedd ein allweddol.

73
00:03:52,400 --> 00:03:56,530
Os byddwn yn cyrraedd diwedd y allweddol heb
daro unrhyw dod i ben marw, awgrymiadau null,

74
00:03:56,530 --> 00:03:59,730
fel sy'n digwydd yma, yna dim ond
rhaid i wirio un peth arall.

75
00:03:59,730 --> 00:04:02,110
Yn allweddol hwn mewn gwirionedd yn
yn y geiriadur?

76
00:04:02,110 --> 00:04:07,660
>> Os felly, dylem ddod o hyd i werth, yn dda a
gwenu icon wyneb yn ein diagram lle

77
00:04:07,660 --> 00:04:08,750
y gair yn dod i ben.

78
00:04:08,750 --> 00:04:12,270
Os oes rhywbeth arall storio gyda
y data, yna gallwn ddychwelyd.

79
00:04:12,270 --> 00:04:16,500
Er enghraifft, nid yw'r sw allweddol yn y
geiriadur, er y gallem gael

80
00:04:16,500 --> 00:04:19,810
cyrraedd diwedd allwedd hon heb erioed
taro pwyntydd null, er ein bod

81
00:04:19,810 --> 00:04:21,089
ailadrodd drwy'r trie.

82
00:04:21,089 --> 00:04:25,436
>> Os byddwn yn ceisio edrych ar y bath allweddol, y
ail i mynegai array nod llynedd,

83
00:04:25,436 --> 00:04:28,750
sy'n cyfateb i'r llythyren H, byddai
wedi cynnal pwyntydd null.

84
00:04:28,750 --> 00:04:31,120
Felly nid bath yn y geiriadur.

85
00:04:31,120 --> 00:04:34,800
Ac felly mae trie yn unigryw gan fod yr allweddi
byth yn cael eu storio yn benodol yn

86
00:04:34,800 --> 00:04:36,650
strwythur data.

87
00:04:36,650 --> 00:04:38,810
Felly sut rydym yn rhoi rhywbeth
i mewn i trie?

88
00:04:38,810 --> 00:04:41,780
>> Gadewch i mewnosoder y allweddol
sw yn ein trie.

89
00:04:41,780 --> 00:04:46,120
Cofiwch fod wyneb hapus mewn nod
Gallai ohebu yn cod i syml

90
00:04:46,120 --> 00:04:50,170
Gwerth boolaidd i ddangos bod sw
yn y geiriadur neu y gallai

91
00:04:50,170 --> 00:04:53,710
yn cyfateb i gael rhagor o wybodaeth ein bod yn
yn dymuno cysylltu â sw allweddol,

92
00:04:53,710 --> 00:04:56,860
fel y diffiniad o'r
gair neu rywbeth arall.

93
00:04:56,860 --> 00:05:00,350
Mewn rhai ffyrdd, mae'r broses i fewnosod
rhywbeth i mewn i trie yn debyg i

94
00:05:00,350 --> 00:05:02,060
edrych i fyny rhywbeth mewn trie.

95
00:05:02,060 --> 00:05:05,720
>> Byddwn yn dechrau gyda'r nod gwraidd eto,
pwyntiau canlynol yn cyfateb i

96
00:05:05,720 --> 00:05:07,990
y llythrennau ein allweddol.

97
00:05:07,990 --> 00:05:11,310
Yn ffodus, roeddem yn gallu dilyn awgrymiadau
yr holl ffordd nes i ni gyrraedd

98
00:05:11,310 --> 00:05:12,770
y diwedd y cyfnod allweddol.

99
00:05:12,770 --> 00:05:16,480
Gan fod sw yn rhagddodiad o'r gair
chwyddo, sy'n aelod o'r

100
00:05:16,480 --> 00:05:19,440
geiriadur, nid oes angen i ni
dyrannu unrhyw nodau newydd.

101
00:05:19,440 --> 00:05:23,140
>> Gallwn addasu'r nod i ddangos bod
y llwybr o gymeriadau yn arwain at

102
00:05:23,140 --> 00:05:25,360
mae'n cynrychioli allweddol yn ein geiriadur.

103
00:05:25,360 --> 00:05:28,630
Yn awr, gadewch i ni geisio gosod y
BATH allweddol i mewn i'r trie.

104
00:05:28,630 --> 00:05:32,260
Byddwn yn dechrau ar y nod gwraidd
a dilyn awgrymiadau eto.

105
00:05:32,260 --> 00:05:35,620
Ond yn y sefyllfa hon, rydym yn taro marw
ben cyn ein bod yn gallu cyrraedd y

106
00:05:35,620 --> 00:05:36,940
diwedd y cyfnod allweddol.

107
00:05:36,940 --> 00:05:40,980
Yn awr, bydd angen i ni ddyrannu rhywfaint newydd
Bydd angen i nodau i ddyrannu un newydd

108
00:05:40,980 --> 00:05:43,660
nod ar gyfer bob un sy'n parhau
llythyr o'n allweddol.

109
00:05:43,660 --> 00:05:46,740
>> Yn yr achos hwn, rydym yn unig mae angen
i ddyrannu un nod newydd.

110
00:05:46,740 --> 00:05:50,590
Yna, bydd angen i ni wneud y mynegai H
cyfeirio at y nod newydd.

111
00:05:50,590 --> 00:05:54,070
Unwaith eto, gallwn addasu'r nod i
yn dangos bod y llwybr o gymeriadau

112
00:05:54,070 --> 00:05:57,120
gan arwain at ei fod yn cynrychioli
allweddol yn ein geiriadur.

113
00:05:57,120 --> 00:06:00,730
Gadewch i resymu am y asymptotic
cymhlethdod ein gweithdrefnau ar gyfer y rhain

114
00:06:00,730 --> 00:06:02,110
dau gweithrediadau.

115
00:06:02,110 --> 00:06:06,420
>> Rydym yn sylwi bod yn y ddau achos y nifer
o'r camau ein algorithm gymerodd ei

116
00:06:06,420 --> 00:06:09,470
gymesur â nifer y
llythyrau yn y gair allweddol.

117
00:06:09,470 --> 00:06:10,220
Mae hynny'n iawn.

118
00:06:10,220 --> 00:06:13,470
Pan fyddwch am i chwilio am air mewn
trie 'ch jyst angen i chi ailadrodd drwy

119
00:06:13,470 --> 00:06:17,100
llythyrau o un i un nes i chi naill ai
cyrraedd diwedd y gair neu'r

120
00:06:17,100 --> 00:06:19,060
taro pen marw yn y trie.

121
00:06:19,060 --> 00:06:22,470
>> A phan fyddwch yn dymuno mewnosod allweddol
gwerth pâr i mewn i trie gan ddefnyddio'r

122
00:06:22,470 --> 00:06:26,250
weithdrefn buom yn ei drafod, yr achos gwaethaf
bydd rhaid i chi ddyrannu nod newydd

123
00:06:26,250 --> 00:06:27,550
ar gyfer pob llythyren.

124
00:06:27,550 --> 00:06:31,290
A byddwn yn cymryd yn ganiataol dyraniad hwnnw
yn weithrediad amser cyson.

125
00:06:31,290 --> 00:06:35,850
Felly, os ydym yn tybio bod hyd allweddol yw
ffinio gan cyson sefydlog, yn

126
00:06:35,850 --> 00:06:39,400
mewnosod ac yn edrych i fyny yn gyson
gweithrediadau amser am trie.

127
00:06:39,400 --> 00:06:42,930
>> Os nad ydym yn gwneud y dybiaeth hon y
hyd allweddol wedi'i ffinio gan sefydlog

128
00:06:42,930 --> 00:06:46,650
gyson, yna mewnosod ac yn edrych i fyny,
yn yr achos gwaethaf, yn cael eu llinellol yn y

129
00:06:46,650 --> 00:06:48,240
hyd y allweddol.

130
00:06:48,240 --> 00:06:51,800
Sylwch fod y nifer o eitemau eu storio
yn y trie nid yw'n effeithio ar y golwg i fyny

131
00:06:51,800 --> 00:06:52,820
neu amser fewnosod.

132
00:06:52,820 --> 00:06:55,360
Dim ond ei heffeithio gan y
hyd y allweddol.

133
00:06:55,360 --> 00:06:59,300
>> Ar y llaw arall, gan ychwanegu cofnodion at, dyweder,
tabl hash yn tueddu i wneud

134
00:06:59,300 --> 00:07:01,250
yn y dyfodol yn edrych i fyny yn arafach.

135
00:07:01,250 --> 00:07:04,520
Er y gall hyn ymddangos yn apelio ar y dechrau,
dylem gadw mewn cof bod y

136
00:07:04,520 --> 00:07:08,740
Nid yw cymhlethdod asymptotic ffafriol yn
yn golygu bod yn ymarferol mae'r data

137
00:07:08,740 --> 00:07:11,410
strwythur o reidrwydd
y tu hwnt i waradwydd.

138
00:07:11,410 --> 00:07:15,860
Rhaid inni hefyd ystyried bod i storio
gair mewn trie ei angen arnom, yn y gwaethaf

139
00:07:15,860 --> 00:07:19,700
achos, mae nifer o nodau cyfrannol
i hyd y gair ei hun.

140
00:07:19,700 --> 00:07:21,880
>> Ceisiau yn tueddu i ddefnyddio llawer o le.

141
00:07:21,880 --> 00:07:25,620
Dyna yn wahanol i tabl hash,
lle mai dim ond angen un nod newydd i ni

142
00:07:25,620 --> 00:07:27,940
storio rhywfaint pâr o werth allweddol.

143
00:07:27,940 --> 00:07:31,370
Nawr, unwaith eto mewn theori, gofod mawr
Nid yw yfed yn ymddangos fel mawr

144
00:07:31,370 --> 00:07:34,620
delio, yn enwedig gan fod modern
gyfrifiaduron gigabeit a

145
00:07:34,620 --> 00:07:36,180
gigabeit o gof.

146
00:07:36,180 --> 00:07:39,200
Ond mae'n troi allan bod gennym
i chi boeni am y defnydd cof a

147
00:07:39,200 --> 00:07:42,540
sefydliad er mwyn
perfformiad, gan gyfrifiaduron modern

148
00:07:42,540 --> 00:07:46,960
fecanweithiau ar waith o dan y
chwfl i gyflymu mynediad cof.

149
00:07:46,960 --> 00:07:51,180
>> Ond dulliau hyn yn gweithio orau pan
mynedfeydd cof yn cael eu gwneud yn gryno

150
00:07:51,180 --> 00:07:52,810
rhanbarthau neu ardaloedd.

151
00:07:52,810 --> 00:07:55,910
A gallai y nodau o trie yn byw
yn unrhyw le yn y domen.

152
00:07:55,910 --> 00:07:58,390
Ond mae'r rhain yn masnach-offs
y mae'n rhaid inni eu hystyried.

153
00:07:58,390 --> 00:08:01,440
>> Cofiwch fod, wrth ddewis data
strwythur ar gyfer tasg benodol, rydym yn

154
00:08:01,440 --> 00:08:04,420
Dylai feddwl am ba fath o
gweithrediadau angen i'r strwythur data i

155
00:08:04,420 --> 00:08:07,140
cymorth a faint perfformiad
pob un o'r rhai a

156
00:08:07,140 --> 00:08:09,080
materion gweithrediadau i ni.

157
00:08:09,080 --> 00:08:11,300
Gall y rhain gweithrediadau hyd yn oed
ymestyn y tu hwnt i

158
00:08:11,300 --> 00:08:13,430
edrych sylfaenol i fyny a gosod.

159
00:08:13,430 --> 00:08:17,010
Gadewch i ni dybio ein bod yn awyddus i weithredu math
ymarferoldeb auto-gwblhau, mae llawer

160
00:08:17,010 --> 00:08:18,890
fel peiriant chwilio Google yn ei wneud.

161
00:08:18,890 --> 00:08:22,210
Hynny yw, dychwelyd yr holl allweddi a
a allai fod gwerthoedd sy'n

162
00:08:22,210 --> 00:08:24,130
cael rhagddodiad penodol.

163
00:08:24,130 --> 00:08:27,050
>> Mae trie yn unigryw ddefnyddiol
gyfer y gwaith hwn.

164
00:08:27,050 --> 00:08:29,890
Mae'n syml i ailadrodd drwy
y trie ar gyfer pob cymeriad

165
00:08:29,890 --> 00:08:30,950
y rhagddodiad.

166
00:08:30,950 --> 00:08:33,559
Yn union fel llawdriniaeth yn edrych i fyny,
gallem ddilyn awgrymiadau

167
00:08:33,559 --> 00:08:35,400
cymeriad drwy gymeriad.

168
00:08:35,400 --> 00:08:38,659
Yna, pan fyddwn yn cyrraedd ar ddiwedd y
rhagddodiad, gallem ailadrodd drwy'r

169
00:08:38,659 --> 00:08:42,049
rhan sy'n weddill o'r strwythur data
gan fod unrhyw o'r allweddi y tu hwnt i

170
00:08:42,049 --> 00:08:43,980
y pwynt hwn yn cael y rhagddodiad.

171
00:08:43,980 --> 00:08:47,670
>> Mae hefyd yn hawdd i gael y rhestr hon
yn nhrefn yr wyddor ers y

172
00:08:47,670 --> 00:08:50,970
elfennau o'r array plant
yn cael eu harchebu yn nhrefn yr wyddor.

173
00:08:50,970 --> 00:08:54,420
Felly, gobeithio y byddwch yn ystyried
rhoi ceisio cais.

174
00:08:54,420 --> 00:08:56,085
Rwy'n Kevin Schmid, ac mae hyn yn CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, mae hyn yn ddechrau
y dirywiad.

177
00:09:00,790 --> 00:09:01,350
Mae'n ddrwg gen i.

178
00:09:01,350 --> 00:09:01,870
Mae'n ddrwg gennym.

179
00:09:01,870 --> 00:09:02,480
Mae'n ddrwg gennym.

180
00:09:02,480 --> 00:09:03,130
Mae'n ddrwg gennym.

181
00:09:03,130 --> 00:09:03,950
>> Streic pedwar.

182
00:09:03,950 --> 00:09:04,360
Rwyf allan.

183
00:09:04,360 --> 00:09:05,280
Mae'n ddrwg gennym.

184
00:09:05,280 --> 00:09:06,500
Mae'n ddrwg gennym.

185
00:09:06,500 --> 00:09:07,490
Mae'n ddrwg gennym.

186
00:09:07,490 --> 00:09:12,352
Mae'n ddrwg gennym ar gyfer gwneud y person sy'n
wedi i olygu hyn yn mynd crazy.

187
00:09:12,352 --> 00:09:13,280
>> Mae'n ddrwg gennym.

188
00:09:13,280 --> 00:09:13,880
Mae'n ddrwg gennym.

189
00:09:13,880 --> 00:09:15,080
Mae'n ddrwg gennym.

190
00:09:15,080 --> 00:09:15,680
Mae'n ddrwg gennym.

191
00:09:15,680 --> 00:09:16,280
>> SIARADWR 1: Da iawn.

192
00:09:16,280 --> 00:09:17,530
Mae hynny'n ei wneud yn dda iawn.

193
00:09:17,530 --> 00:09:18,430