1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - 5 Set broblem]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Mae hyn yn CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Mae pob hawl. Helo, bawb, a chroeso i Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 yn Camsillafu, y byddwn yn gwneud wirydd sillafu.

6
00:00:17,400 --> 00:00:21,030
Sillafu-gwirwyr yn hynod o bwysig.

7
00:00:21,030 --> 00:00:23,390
A yw hyn wedi digwydd i chi erioed?

8
00:00:23,390 --> 00:00:27,170
Byddwch yn gweithio iawn, iawn celc ar bapur ar gyfer y gem

9
00:00:27,170 --> 00:00:33,120
ac yna yn dal yn y pen draw cael rade glow iawn fel D neu D =

10
00:00:33,120 --> 00:00:39,390
a hynny oherwydd chi yw'r spoiler liverwurst yn y gair morfil eang.

11
00:00:39,390 --> 00:00:44,710
Ie, prawfddarllen eich pupurau yn fater o, y impotence mwyaf.

12
00:00:44,710 --> 00:00:49,140
Mae hon yn broblem sy'n effeithio ar manly, myfyrwyr manly.

13
00:00:49,140 --> 00:00:56,260
Dywedwyd wrthyf unwaith gan fy torturer gradd Sith na fyddwn byth yn mynd i mewn i gydweithiwr da.

14
00:00:56,260 --> 00:01:00,250
A dyna i gyd wyf erioed wedi eisiau, dyna i gyd am unrhyw blentyn yn fy oed i,

15
00:01:00,250 --> 00:01:04,569
dim ond i fynd i mewn i gydweithiwr da.

16
00:01:04,569 --> 00:01:12,720
Ac nid yn unig unrhyw gydweithiwr. Rhif Roeddwn i eisiau mynd i gydweithiwr Ivory Cyfreithiol.

17
00:01:12,720 --> 00:01:18,360
Felly, pe na byddwn wedi gwella, byddai mynd yn fy mreuddwydion o fynd i Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, neu Carchar - chi'n gwybod, yn y Carchar, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Felly Cefais fy hun yn wirydd sillafu.

20
00:01:25,170 --> 00:01:29,380
Dyna darn bach o un o fy artistiaid gair llafar hoff, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Beth bynnag, fel y dywed, y pwysigrwydd o gael wirydd sillafu yn bwysig iawn.

22
00:01:34,630 --> 00:01:39,440
>> Felly croeso i Walkthrough 5, y byddwn yn siarad am pset5: Camsillafu,

23
00:01:39,440 --> 00:01:44,300
y byddwn yn gwneud ein hunain gwirydd sillafu.

24
00:01:44,300 --> 00:01:50,880
Mae'r pecyn cymorth ar gyfer yr wythnos, y cod dosbarthu, yn mynd i fod yn bwysig edrych ar

25
00:01:50,880 --> 00:01:54,950
dim ond er mwyn deall y swyddogaethau gwahanol y mae eich geiriadur yn mynd i gael.

26
00:01:54,950 --> 00:02:01,500
Rydym yn wir yn mynd i fod yn cael ffeiliau c lluosog. Sydd gyda'i gilydd yn gwneud ein pset.

27
00:02:01,500 --> 00:02:05,420
Ac felly yn edrych drwy'r agweddau gwahanol, er nad ydym yn bod mewn gwirionedd yn golygu

28
00:02:05,420 --> 00:02:10,770
un o'r ffeiliau, speller.c, gan wybod sut y mae'n gweithio gyda perthynas â dictionary.c,

29
00:02:10,770 --> 00:02:14,100
y byddwn yn ei ysgrifennu, yn mynd i fod yn eithaf pwysig.

30
00:02:14,100 --> 00:02:16,970
Mae'r fanyleb pset hefyd yn cynnwys llawer o wybodaeth ddefnyddiol

31
00:02:16,970 --> 00:02:21,360
o ran pethau y gallwch eu cymryd yn ganiataol, rheolau a phethau fel 'na,

32
00:02:21,360 --> 00:02:24,710
felly gwnewch yn siŵr i ddarllen y fanyleb pset yn ofalus am awgrymiadau.

33
00:02:24,710 --> 00:02:29,310
Ac os ydynt yn ansicr o reol neu rywbeth fel 'na, yna bob amser yn cyfeirio at y fanyleb pset

34
00:02:29,310 --> 00:02:31,550
neu Trafodwch.

35
00:02:31,550 --> 00:02:34,060
Mae'r pset yn mynd i ddibynnu'n drwm ar awgrymiadau,

36
00:02:34,060 --> 00:02:37,890
felly rydym yn awyddus i wneud yn siŵr ein bod yn deall y gwahaniaeth rhwng y sêr ychwanegu

37
00:02:37,890 --> 00:02:41,680
o flaen enw y pwyntydd a ampersands, sut i'w rhyddhau, ac ati

38
00:02:41,680 --> 00:02:47,550
Felly, fod yn feistr o awgrymiadau yn mynd i fod yn ddefnyddiol iawn yn y set hon broblem.

39
00:02:47,550 --> 00:02:50,460
Rydym yn mynd i edrych i mewn rhestrau cysylltiedig ychydig yn fwy,

40
00:02:50,460 --> 00:02:57,790
lle mae gennym elfennau yr ydym yn galw nodau sydd wedi ddau werth yn ogystal â pwyntydd

41
00:02:57,790 --> 00:03:02,520
at y nod nesaf, ac felly yn ei hanfod yn cysylltu gwahanol elfennau un ar ôl y llall.

42
00:03:02,520 --> 00:03:07,190
Mae yna ychydig o ddewisiadau gwahanol o weithredu eich geiriadur gwirioneddol.

43
00:03:07,190 --> 00:03:13,150
Rydym yn mynd i edrych i mewn dau brif ddull, sy'n tablau hash ac wedyn yn ceisio.

44
00:03:13,150 --> 00:03:17,660
Yn y ddau o'r rheiny, maent yn cynnwys rhyw fath o syniad o restr sy'n gysylltiedig

45
00:03:17,660 --> 00:03:20,790
lle rydych wedi elfennau sy'n gysylltiedig â'i gilydd.

46
00:03:20,790 --> 00:03:25,640
Ac felly rydym ni'n mynd i edrych dros sut efallai y byddwch yn gallu gweithredu o ran rhestrau cysylltiedig,

47
00:03:25,640 --> 00:03:29,680
eu creu, llywio o ran sut i, er enghraifft, rhowch nod i mewn iddo

48
00:03:29,680 --> 00:03:32,760
neu am ddim bob un o'r nodau yn ogystal.

49
00:03:32,760 --> 00:03:34,740
O ran nodau rhyddhau, mae hynny'n bwysig iawn

50
00:03:34,740 --> 00:03:37,700
pa bryd bynnag y cof malloc, wedyn rydym yn rhyddhau ei.

51
00:03:37,700 --> 00:03:42,910
Felly, rydym am wneud yn siŵr nad oes unrhyw pwyntydd yn mynd unfreed, nad oes gennym unrhyw ollyngiadau cof.

52
00:03:42,910 --> 00:03:48,330
Rydym yn mynd i gyflwyno dull o'r enw Valgrind sy'n rhedeg eich rhaglen

53
00:03:48,330 --> 00:03:52,260
a gwiriadau a oedd yr holl cof eich bod yn dyrannu ei ryddhau wedyn.

54
00:03:52,260 --> 00:03:59,080
Eich pset yn unig gwblhau pan fydd yn gweithio ac mae ymarferoldeb llawn,

55
00:03:59,080 --> 00:04:03,990
ond hefyd, Valgrind yn dweud wrthych nad ydych wedi dod o hyd unrhyw ollyngiadau cof.

56
00:04:03,990 --> 00:04:06,690
Yn olaf, ar gyfer y pset, Rwy'n awyddus iawn i bwysleisio -

57
00:04:06,690 --> 00:04:11,360
Yr wyf yn golygu, fel arfer, yr wyf yn sicr yn gefnogwr o ddefnyddio pen a phapur ar gyfer eich setiau problem,

58
00:04:11,360 --> 00:04:14,840
ond ar gyfer yr un yma, credaf fod pen a phapur yn mynd i fod yn arbennig o bwysig

59
00:04:14,840 --> 00:04:19,000
pan fyddwch eisiau cael tynnu saethau i bethau a deall sut mae pethau'n gweithio.

60
00:04:19,000 --> 00:04:24,440
Felly, yn bendant yn ceisio defnyddio pin a phapur i dynnu pethau allan cyn i chi gael codio

61
00:04:24,440 --> 00:04:26,970
oherwydd gallai gael ychydig anniben.

62
00:04:26,970 --> 00:04:30,700
>> Yn gyntaf, gadewch i ni fynd i mewn i restrau cysylltiedig ychydig.

63
00:04:30,700 --> 00:04:35,510
Rhestrau cysylltiedig yn cynnwys nodau, lle mae pob nod werth sy'n gysylltiedig ag ef,

64
00:04:35,510 --> 00:04:39,810
yn ogystal â rhoi syniad inni am y nod nesaf ar ei ôl.

65
00:04:39,810 --> 00:04:43,680
Mae cwpl o bethau pwysig gyda'r rhestrau cysylltiedig y mae angen inni i gofio

66
00:04:43,680 --> 00:04:48,810
lle mae ein nod cyntaf yw, ac yna ar ôl i ni wybod ble y nod cyntaf yw,

67
00:04:48,810 --> 00:04:52,990
y ffordd y gallwn gael mynediad i'r nod fod y pwyntiau nod cyntaf i

68
00:04:52,990 --> 00:04:55,850
ac yna yr un ar ôl hynny ac un ar ôl hynny.

69
00:04:55,850 --> 00:05:00,340
Ac yna yr elfen olaf yn eich rhestr cysylltiedig yn pwyntydd y nod yn

70
00:05:00,340 --> 00:05:02,340
bob amser yn mynd i dynnu i NULL.

71
00:05:02,340 --> 00:05:08,230
Pan fydd pwyntiau nod i NULL, yna rydych yn gwybod eich bod wedi cyrraedd diwedd y rhestr,

72
00:05:08,230 --> 00:05:12,320
bod y nod yw'r un olaf, nad oes dim ar ôl hynny.

73
00:05:12,320 --> 00:05:16,970
Yma yn y sgematig, gwelwch fod y saethau yw'r awgrymiadau,

74
00:05:16,970 --> 00:05:20,290
a'r adran glas yn lle mae'r gwerth yn cael ei storio,

75
00:05:20,290 --> 00:05:24,420
ac yna y blwch coch gyda'r pwyntydd i fod yn pwyntydd y nod yn

76
00:05:24,420 --> 00:05:27,050
pwyntio at y nod nesaf ar ei ôl.

77
00:05:27,050 --> 00:05:33,730
Ac felly byddwch yn gweld yma, byddai'r nod D pwynt i nwl oherwydd ei fod yn elfen olaf yn y rhestr.

78
00:05:33,730 --> 00:05:38,240
>> Gadewch i ni edrych ar sut y gallem ddiffinio strwythur ar gyfer nod.

79
00:05:38,240 --> 00:05:40,130
Ac ers i ni am gael nodau lluosog,

80
00:05:40,130 --> 00:05:43,180
hyn yn mynd i ddod yn strwythur typedef

81
00:05:43,180 --> 00:05:46,870
lle rydym yn mynd i gael enghreifftiau gwahanol o nodau.

82
00:05:46,870 --> 00:05:50,850
Ac felly rydym yn ei ddiffinio fel math data newydd.

83
00:05:50,850 --> 00:05:53,630
Yma, mae gennym nod strwythur typedef.

84
00:05:53,630 --> 00:05:56,160
Yn yr enghraifft hon, rydym yn delio â nodau cyfanrif,

85
00:05:56,160 --> 00:06:00,490
felly mae gennym werth cyfanrif a enwir ac yna mae gennym arall pwyntydd,

86
00:06:00,490 --> 00:06:07,390
ac yn yr achos hwn, mae'n pwyntydd i nod, felly mae gennym nod strwythur * a elwir yn nesaf.

87
00:06:07,390 --> 00:06:09,520
Ac yna rydym yn galw hyn yn nod holl beth.

88
00:06:09,520 --> 00:06:11,110
Gwnewch yn siŵr eich bod yn dilyn y gystrawen.

89
00:06:11,110 --> 00:06:17,940
Hysbysiad bod nod wedi ei gyfeirio mewn gwirionedd i fyny uchod, yn ogystal fel y nodir isod y braces cyrliog.

90
00:06:17,940 --> 00:06:23,400
Yna i gadw cofnod o lle mae fy nod cyntaf yw yn y rhestr cysylltiedig,

91
00:06:23,400 --> 00:06:29,390
hynny, rwyf wedi pwyntydd cainc o'r enw pen, a gofod malloc wyf ddigon ar gyfer maint y nod.

92
00:06:29,390 --> 00:06:36,240
Rhybudd, fodd bynnag, bod pennaeth mewn gwirionedd yn pwyntydd nod o'i gyferbynnu â nod ei hun.

93
00:06:36,240 --> 00:06:40,130
Felly, y pennaeth mewn gwirionedd nid yw'n cynnwys unrhyw werth,

94
00:06:40,130 --> 00:06:45,590
dim ond yn cyfeirio at ba un bynnag y nod cyntaf yn fy rhestr cysylltiedig yn.

95
00:06:55,080 --> 00:06:58,340
>> I gael syniad gwell o restrau cysylltiedig, oherwydd ei fod yn bwysig iawn

96
00:06:58,340 --> 00:07:02,220
i gadw golwg ar wneud yn siŵr eich bod yn cynnal y gadwyn,

97
00:07:02,220 --> 00:07:09,990
Rwy'n hoffi meddwl ohono fel pobl mewn llinell yn dal dwylo,

98
00:07:09,990 --> 00:07:14,330
lle mae pob person yn dal dwylo gyda yr un nesaf.

99
00:07:14,330 --> 00:07:18,350
Ni allwch weld yn y llun, ond yn y bôn maent yn pwyntio at y person nesaf

100
00:07:18,350 --> 00:07:23,760
sydd yn eu cadwyn.

101
00:07:23,760 --> 00:07:29,270
Ac felly os ydych am deithio ar draws rhestr cysylltiedig lle mae'r bobl hyn -

102
00:07:29,270 --> 00:07:32,830
dychmygu pob un o'r bobl hynny gwerthoedd sy'n gysylltiedig â hwy

103
00:07:32,830 --> 00:07:36,590
a hefyd yn cyfeirio at y person nesaf yn y llinell -

104
00:07:36,590 --> 00:07:40,810
os ydych am i groesi'r rhestr cysylltiedig, er enghraifft, naill ai i olygu'r gwerthoedd

105
00:07:40,810 --> 00:07:42,830
neu chwilio am werth neu rywbeth fel 'na,

106
00:07:42,830 --> 00:07:48,270
yna byddwch chi eisiau i gael pwyntydd i'r person penodol.

107
00:07:48,270 --> 00:07:52,670
Felly, rydym yn mynd i gael data fath pwyntydd nod.

108
00:07:52,670 --> 00:07:55,580
Er yr achos hwn, gadewch i ni ei alw cyrchwr.

109
00:07:55,580 --> 00:07:59,630
Arall fyddai ffordd gyffredin i enwi hyn yn iterator neu rywbeth fel 'na

110
00:07:59,630 --> 00:08:05,130
oherwydd ei fod yn ailadrodd drosodd ac mewn gwirionedd yn symud y nod ei fod yn pwyntio at.

111
00:08:05,130 --> 00:08:14,410
Bydd hyn dyma fydd ein cyrchwr.

112
00:08:14,410 --> 00:08:20,180
Bydd ein cyrchwr 1 yn cyfeirio at yr elfen gyntaf yn ein rhestr.

113
00:08:20,180 --> 00:08:26,910
Ac felly yr hyn yr ydym am ei wneud yw y byddai yn y bôn rydym yn parhau y cyrchwr,

114
00:08:26,910 --> 00:08:29,130
symud o ochr i ochr.

115
00:08:29,130 --> 00:08:33,409
Yn yr achos hwn, rydym am symud i'r elfen nesaf yn y rhestr.

116
00:08:33,409 --> 00:08:38,480
Gyda arrays, beth y byddem yn ei wneud yw y byddem yn unig yn dweud ein bod yn cynyddu'r mynegai erbyn 1.

117
00:08:38,480 --> 00:08:46,020
Yn yr achos hwn, yr hyn y mae angen i ni ei wneud yw mewn gwirionedd yn dod o hyd i pa berson y person hwn ar hyn o bryd yn pwyntio at,

118
00:08:46,020 --> 00:08:48,930
ac mae hynny'n mynd i fod yn werth nesaf.

119
00:08:48,930 --> 00:08:53,230
Felly, os cyrchwr yn unig yw pwyntydd nod, yna beth yr ydym am ei wneud

120
00:08:53,230 --> 00:08:56,320
yw ein bod am i gyrraedd y gwerth y mae'r cyrchwr yn pwyntio i.

121
00:08:56,320 --> 00:09:01,350
Rydym yn awyddus i gyrraedd y nod, ac yna, unwaith y byddwn ni'n ar y nod, dod o hyd i ble mae'n pwyntio at.

122
00:09:01,350 --> 00:09:05,820
I gyrraedd y nod go iawn y mae'r cyrchwr yn pwyntio at,

123
00:09:05,820 --> 00:09:13,160
Fel arfer, rydym yn nodi iddo gan (* cyrchwr).

124
00:09:13,160 --> 00:09:19,160
Byddai hynny'n rhoi i chi y nod go iawn y mae'r cyrchwr yn pwyntio i.

125
00:09:19,160 --> 00:09:21,730
Ac yna ar ôl hynny, yr hyn rydym am ei wneud yw ein bod am gael mynediad

126
00:09:21,730 --> 00:09:25,680
beth bynnag yw gwerth nod nesaf yw.

127
00:09:25,680 --> 00:09:32,820
I wneud hynny, i gael mynediad i'r gwerthoedd tu mewn i'r strwythur, mae gennym y gweithredwr dot.

128
00:09:32,820 --> 00:09:39,530
Felly, yna byddai'n (* cyrchwr). Nesaf.

129
00:09:39,530 --> 00:09:44,840
Ond mae hyn yn ychydig yn flêr o ran cael y cromfachau o gwmpas y cyrchwr *,

130
00:09:44,840 --> 00:09:56,800
ac felly rydym yn cymryd lle'r datganiad hwn cyfan gyda cyrchwr->.

131
00:09:56,800 --> 00:10:02,700
Mae hwn yn dash ac yna arwydd mwy na, felly gwneud saeth.

132
00:10:02,700 --> 00:10:05,840
cyrchwr-> nesaf.

133
00:10:05,840 --> 00:10:12,390
Bydd hynny mewn gwirionedd yn mynd â chi y nôd bod y pwyntiau cyrchwr. Bod y gwerth hwnnw'n o nesaf.

134
00:10:12,390 --> 00:10:16,790
Felly, yn lle cael y seren a'r dot, rydych yn disodli'r gyda saeth.

135
00:10:16,790 --> 00:10:24,820
Byddwch yn ofalus iawn i wneud yn siŵr eich bod yn ceisio defnyddio'r gystrawen.

136
00:10:33,550 --> 00:10:37,620
>> Nawr ein bod wedi ein cyrchwr, os ydym am i gael mynediad i'r gwerth,

137
00:10:37,620 --> 00:10:40,450
o'r blaen, cawsom cyrchwr-> nesaf,

138
00:10:40,450 --> 00:10:46,260
ond i gael mynediad i'r gwerth ar y nod bod y cyrchwr yn pwyntio at, rydym yn unig yn syml yn dweud

139
00:10:46,260 --> 00:10:48,070
nod-> werth.

140
00:10:48,070 --> 00:10:53,600
Oddi yno, mae'n fath o ddata beth bynnag rydym wedi diffinio'r gwerthoedd a'r nodau i fod.

141
00:10:53,600 --> 00:10:59,620
Os yw'n nod int, yna cyrchwr-> werth yn unig yn mynd i fod yn gyfanrif.

142
00:10:59,620 --> 00:11:04,870
Felly gallwn wneud gweithrediadau ar hynny, gwirio cydraddoldeb, neilltuo ei werthoedd gwahanol, ac ati

143
00:11:04,870 --> 00:11:11,090
Felly, yna beth rydych am ei wneud os ydych am symud eich cyrchwr at y person nesaf,

144
00:11:11,090 --> 00:11:15,270
chi mewn gwirionedd yn newid gwerth y cyrchwr.

145
00:11:15,270 --> 00:11:19,340
Gan cyrchwr yn bwyntydd nod, byddwch yn newid y cyfeiriad pwyntydd gwirioneddol

146
00:11:19,340 --> 00:11:23,890
i gyfeiriad y nod nesaf yn eich rhestr.

147
00:11:23,890 --> 00:11:28,930
Mae hyn yn dim ond rhai cod lle y gallech ailadrodd.

148
00:11:28,930 --> 00:11:31,230
Ble alla i gael y sylw wneud rhywbeth,

149
00:11:31,230 --> 00:11:33,850
dyna lle mae'n debyg eich bod yn mynd i gael y gwerth

150
00:11:33,850 --> 00:11:37,850
neu wneud rhywbeth i wneud gyda'r nod penodol.

151
00:11:37,850 --> 00:11:43,050
I gychwyn i ffwrdd, yr wyf yn dweud bod fy cyrchwr i ddechrau

152
00:11:43,050 --> 00:11:48,430
yn mynd i gyfeirio at yr elfen gyntaf yn y rhestr cysylltiedig.

153
00:11:48,430 --> 00:11:52,910
Ac felly i fyny i ddod, rwy'n ddiffinio fel pennaeth y nod.

154
00:11:52,910 --> 00:11:57,610
>> Fel y soniais o'r blaen, gan ryddhau yn wirioneddol bwysig.

155
00:11:57,610 --> 00:12:02,440
Byddwch am wneud yn siŵr eich bod yn rhyddhau pob elfen yn y rhestr unwaith y byddwch wedi gorffen ag ef.

156
00:12:02,440 --> 00:12:04,940
Pan nad oes angen i chi gyfeirio at unrhyw un o'r awgrymiadau anymore,

157
00:12:04,940 --> 00:12:10,620
ydych am wneud yn siŵr eich bod yn rhyddhau pawb awgrymiadau.

158
00:12:10,620 --> 00:12:14,460
Ond ydych chi am fod yn ofalus iawn yma yn yr ydych am osgoi unrhyw ollyngiadau cof.

159
00:12:14,460 --> 00:12:25,080
Os ydych yn rhad ac am ddim un person yn rhy gynnar, yna mae'r holl arwyddion bod pwyntiau nod i

160
00:12:25,080 --> 00:12:26,900
yn mynd i gael eu colli.

161
00:12:26,900 --> 00:12:32,070
Fynd yn ôl at yr enghraifft person i'w gwneud yn ychydig yn fwy stakes uchel,

162
00:12:32,070 --> 00:12:49,600
gadewch i ni gael y bobl hyn, ac eithrio yn yr achos hwn y maent yn hofran dros llyn gyda anghenfil.

163
00:12:49,600 --> 00:12:53,200
Rydym eisiau gwneud yn siŵr bod pryd bynnag y byddwn yn rhyddhau, nad ydym yn colli

164
00:12:53,200 --> 00:12:58,920
a gadael i fynd o unrhyw nodau cyn i ni ryddhau mewn gwirionedd nhw.

165
00:12:58,920 --> 00:13:05,730
Er enghraifft, os ydych i wneud dim ond ffoniwch am ddim ar y boi yma,

166
00:13:05,730 --> 00:13:15,350
yna byddai'n cael ei ryddhau, ond yna byddai pob un o'r rhain guys wedyn yn cael eu colli

167
00:13:15,350 --> 00:13:18,450
a byddent yn drifft i ffwrdd ac yn syrthio i lawr.

168
00:13:18,450 --> 00:13:24,900
Felly, rydym am wneud yn siŵr bod lle hynny, rydym am gynnal cyswllt â'r gweddill.

169
00:13:37,630 --> 00:13:42,480
Mae ein, pwyntydd pen sy'n cyfeirio at yr elfen gyntaf yn y rhestr.

170
00:13:42,480 --> 00:13:49,990
Mae'n fath o fel rhaff angori y person cyntaf.

171
00:13:52,870 --> 00:13:57,470
Beth efallai y byddwch am ei wneud pan fyddwch yn rhyddhau rhestr yn cael -

172
00:13:57,470 --> 00:14:04,520
Os ydych am i ryddhau yr elfen gyntaf yn gyntaf, yna gallwch gael pwyntydd dros dro

173
00:14:04,520 --> 00:14:07,370
bod pwyntiau i beth bynnag yr elfen gyntaf yn.

174
00:14:07,370 --> 00:14:11,420
Felly, rydych yn cael eich pwyntydd dros dro pwyntio yma.

175
00:14:11,420 --> 00:14:15,840
Y ffordd honno, mae gennym gafael ar y nod cyntaf.

176
00:14:15,840 --> 00:14:18,930
Ac yna, gan ein bod yn gwybod bod y nod cyntaf yn mynd i gael eu rhyddhau,

177
00:14:18,930 --> 00:14:24,890
yna gallwn symud y rhaff, mae hyn yn angor, mae ein pennaeth,

178
00:14:24,890 --> 00:14:31,930
i mewn gwirionedd yn pwyntio i beth bynnag yr un cyntaf yn pwyntio at.

179
00:14:31,930 --> 00:14:38,760
Felly, mae hyn mewn gwirionedd pen yn cyfeirio at yr ail elfen yn awr.

180
00:14:38,760 --> 00:14:43,980
Nawr rydym yn cael i ryddhau beth bynnag yn cael ei storio mewn adeiladau dros,

181
00:14:43,980 --> 00:14:53,360
ac felly gallwn ddileu, heb ei beryglu pob un o'r nodau eraill yn ein rhestr.

182
00:14:54,140 --> 00:15:05,020
Gallai ffordd arall y gallech wneud hyn fyddai

183
00:15:05,020 --> 00:15:08,650
bob tro y byddwch yn unig ryddhau yr elfen olaf yn y rhestr

184
00:15:08,650 --> 00:15:11,010
oherwydd eu bod yn sicr o beidio gael eu hamlygu i unrhyw beth.

185
00:15:11,010 --> 00:15:15,570
Felly, fe allech chi jyst ryddhau yr un yma, yna ddim yr un, yna ddim yr un.

186
00:15:15,570 --> 00:15:21,900
Mae hynny'n bendant yn gweithio, ond ychydig yn arafach oherwydd erbyn natur y rhestrau cysylltiedig,

187
00:15:21,900 --> 00:15:24,670
Ni allwn yn unig yn syth neidio i'r un diwethaf.

188
00:15:24,670 --> 00:15:28,030
Mae'n rhaid i ni deithio ar draws pob elfen yn y rhestr sy'n gysylltiedig

189
00:15:28,030 --> 00:15:31,020
a gwirio a bod un yn pwyntio at null, gwirio bob tro,

190
00:15:31,020 --> 00:15:33,780
ac yna unwaith rydym yn cyrraedd y diwedd, yna rhad ac am ddim hynny.

191
00:15:33,780 --> 00:15:40,270
Pe baech yn gwneud y broses hon, byddech mewn gwirionedd yn gwirio yma,

192
00:15:40,270 --> 00:15:44,190
gwirio yma, yna gwirio yma, gan ryddhau ei,

193
00:15:44,190 --> 00:15:47,470
yna mynd yn ôl, gan wirio yma, gwirio yma, gan ryddhau ei,

194
00:15:47,470 --> 00:15:49,660
gwirio yma, ac yna rhyddhau ei.

195
00:15:49,660 --> 00:15:52,880
Mae hynny'n cymryd ychydig mwy o amser. Yeah.

196
00:15:52,880 --> 00:15:59,060
>> [Myfyrwyr] A fyddai'n bosibl i wneud rhestr cysylltiedig sy'n storio yn bwyntydd allanfa i'r diwedd?

197
00:15:59,060 --> 00:16:01,320
Byddai hynny'n sicr yn bosibl.

198
00:16:01,320 --> 00:16:08,340
I ailadrodd y cwestiwn, a yw'n bosibl cael strwythur restr cysylltiedig

199
00:16:08,340 --> 00:16:12,490
fel bod gennych pwyntydd pwyntio at ddiwedd y rhestr sy'n gysylltiedig?

200
00:16:12,490 --> 00:16:18,090
Byddwn i'n dweud hynny'n bosibl, a bob tro y byddwch rhoi rhywbeth yn eich rhestr cysylltiedig

201
00:16:18,090 --> 00:16:21,470
byddai'n rhaid i chi ddiweddaru'r pwyntydd a phethau fel 'na.

202
00:16:21,470 --> 00:16:26,640
Byddai gennych gynffon * nod, er enghraifft.

203
00:16:26,640 --> 00:16:29,840
Ond pan fyddwch yn gweithredu'r nodwedd, rhaid i chi feddwl am y fasnach-offs,

204
00:16:29,840 --> 00:16:32,700
fel faint o weithiau ydw i'n mynd i gael ei ailadrodd dros hyn,

205
00:16:32,700 --> 00:16:36,100
pa mor anodd y mae'n mynd i fod i gadw golwg ar y gynffon yn ogystal â'r pennaeth

206
00:16:36,100 --> 00:16:38,400
yn ogystal â'm iterator, a phethau fel 'na.

207
00:16:40,730 --> 00:16:42,480
A yw hynny'n -? >> [Myfyrwyr] Yeah.

208
00:16:42,480 --> 00:16:48,270
Mae'n bosibl, ond o ran penderfyniadau dylunio, rhaid i chi bwyso a mesur yr opsiynau.

209
00:16:53,850 --> 00:17:01,090
>> Dyma sgerbwd o god a fyddai'n caniatáu i chi i ryddhau pob elfen mewn rhestr cysylltiedig.

210
00:17:01,090 --> 00:17:05,460
Unwaith eto, gan fy mod i'n ailadrodd dros rhestr cysylltiedig, dw i'n mynd i eisiau cael rhyw fath o cyrchwr

211
00:17:05,460 --> 00:17:08,670
neu iterator.

212
00:17:08,670 --> 00:17:14,640
Rydym yn ailadrodd nes bod y cyrchwr yn null.

213
00:17:14,640 --> 00:17:17,640
Nid ydych am i ailadrodd pan fydd eich cyrchwr yn null

214
00:17:17,640 --> 00:17:20,579
oherwydd mae hynny'n golygu nad oes unrhyw beth yn y rhestr.

215
00:17:20,579 --> 00:17:25,069
Felly, yna dyma wyf yn gwneud * nod dros dro

216
00:17:25,069 --> 00:17:29,610
dynnu sylw at yr hyn rwy'n ei ystyried yw'r cyntaf o fy rhestr,

217
00:17:29,610 --> 00:17:35,340
ac yna mi symud fy cyrchwr ymlaen 1 ac yna rhad ac am ddim beth bynnag yr wyf wedi'i gael yn y storfa dros dro.

218
00:17:38,460 --> 00:17:43,650
>> Nawr rydym yn dod i mewnosod mewn rhestrau cysylltiedig.

219
00:18:00,200 --> 00:18:09,660
Mae gennyf dri nodau yn fy rhestr gysylltiedig, a gadewch i ni fynd â'r achos syml

220
00:18:09,660 --> 00:18:18,970
lle rydym am mewnosod un arall nod ar ddiwedd ein rhestr cysylltiedig.

221
00:18:18,970 --> 00:18:25,980
I wneud hynny, y cyfan byddem yn ei wneud yw y byddem yn tramwyo

222
00:18:25,980 --> 00:18:32,100
i ddod o hyd lle y diwedd presennol y rhestr cysylltiedig yw, felly pa bynnag nod yn pwyntio at NULL -

223
00:18:32,100 --> 00:18:33,850
dyna yr un yma -

224
00:18:33,850 --> 00:18:37,260
ac yna dweud, mewn gwirionedd, nid yw'r un yn mynd i fod y nod olaf;

225
00:18:37,260 --> 00:18:39,830
rydym yn wir yn mynd i gael un arall.

226
00:18:39,830 --> 00:18:46,260
Felly, byddai gennym y cerrynt un pwynt i beth bynnag yr ydym yn gosod.

227
00:18:46,260 --> 00:18:50,080
Felly, yn awr, y person goch yma yn dod y nod olaf yn y rhestr cysylltiedig.

228
00:18:50,080 --> 00:18:56,080
Ac felly y nodwedd y nod olaf yn y rhestr cysylltiedig yw ei fod yn cyfeirio at NULL.

229
00:18:56,080 --> 00:19:09,380
Felly, yna beth y byddai'n rhaid inni ei wneud yw gosod pwyntydd y boi coch i NULL. Mae yna.

230
00:19:09,380 --> 00:19:25,370
>> Ond beth os ydym eisiau i osod nod mewn rhwng yr un ail a'r trydydd?

231
00:19:25,370 --> 00:19:28,960
Nad yw rhywun yn mor syml oherwydd ein bod eisiau gwneud yn siwr

232
00:19:28,960 --> 00:19:34,290
nad ydym yn gadael i fynd o unrhyw nod yn ein rhestr cysylltiedig.

233
00:19:34,290 --> 00:19:43,450
Beth byddai'n rhaid i ni ei wneud yw gwneud yn siŵr ein bod yn angori ein hunain i bob un.

234
00:19:43,450 --> 00:19:49,900
Er enghraifft, gadewch i ni yn galw hyn yn ail un.

235
00:19:49,900 --> 00:19:54,390
Os byddwch yn dweud yr ail un yn awr yn cyfeirio at yr un newydd

236
00:19:54,390 --> 00:20:02,520
a 'ch jyst gwneud pwyntydd yno, yna byddai hynny'n arwain at y boi yn cael ei golli

237
00:20:02,520 --> 00:20:07,830
oherwydd nad oes unrhyw gysylltiad ag ef.

238
00:20:07,830 --> 00:20:18,970
Yn lle hynny - 'N annhymerus' tynnu hyn eto. Esgusodwch fy galluoedd artistig.

239
00:20:18,970 --> 00:20:26,570
Rydym yn gwybod na allwn yn unig yn cysylltu'n uniongyrchol 2 i un newydd.

240
00:20:26,570 --> 00:20:30,480
Mae'n rhaid i ni wneud yn siŵr ein bod yn dal gafael ar yr un ddiwethaf.

241
00:20:30,480 --> 00:20:39,200
Yr hyn yr hoffem ei wneud yw cael pwyntydd dros dro

242
00:20:39,200 --> 00:20:42,650
i'r elfen sy'n mynd i gael ei atodi ar.

243
00:20:42,650 --> 00:20:45,140
Felly, yna mae gennym pwyntydd dros dro yno.

244
00:20:45,140 --> 00:20:50,780
Ers i ni yn gwybod bod yr un trydydd cael ei gadw golwg ar,

245
00:20:50,780 --> 00:20:53,680
2 Mae cyswllt yn awr at ein un newydd.

246
00:20:53,680 --> 00:20:57,490
Ac os yw hyn yn guy coch newydd yn mynd i fod rhwng 2 a 3,

247
00:20:57,490 --> 00:21:05,550
yna beth yw pwyntydd y dyn yn mynd i gyfeirio at? >> [Myfyrwyr] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Yeah.

249
00:21:07,490 --> 00:21:15,430
Felly, yna werth y boi coch nesaf yn mynd i fod dros dro.

250
00:21:26,090 --> 00:21:33,010
Pan fyddwch chi'n gosod mewn rhestrau cysylltiedig, gwelsom y gallem

251
00:21:33,010 --> 00:21:38,260
yn hawdd ychwanegu rhywbeth at y diwedd drwy greu amrywiaeth dros dro,

252
00:21:38,260 --> 00:21:42,850
neu os ydym am ychwanegu rhywbeth i ganol ein amrywiaeth,

253
00:21:42,850 --> 00:21:46,810
yna byddai'n cymryd ychydig yn fwy anghyfforddus.

254
00:21:46,810 --> 00:21:50,240
Os ydych chi eisiau, er enghraifft, restr datrys cysylltiedig,

255
00:21:50,240 --> 00:21:54,880
yna rhaid i chi math o bwyso a mesur y costau a manteision hynny

256
00:21:54,880 --> 00:21:59,720
oherwydd os ydych am gael amrywiaeth datrys, mae hynny'n golygu bod bob tro y rhowch i mewn iddo,

257
00:21:59,720 --> 00:22:01,630
mae'n mynd i gymryd ychydig mwy o amser.

258
00:22:01,630 --> 00:22:05,500
Fodd bynnag, os ydych am i yn nes ymlaen, gan y byddwn yn dod o hyd y byddwn yn dymuno,

259
00:22:05,500 --> 00:22:10,280
chwilio trwy restr gysylltiedig, yna efallai y byddai'n haws os ydych yn gwybod bod popeth mewn trefn.

260
00:22:10,280 --> 00:22:15,340
Felly, efallai y byddwch am bwyso a mesur costau a manteision hynny.

261
00:22:20,150 --> 00:22:27,740
>> Ffordd arall i fewnosod i mewn i restr cysylltiedig yw i fewnosod yn dechrau o restr.

262
00:22:27,740 --> 00:22:34,700
Os byddwn yn tynnu ein angor yma - mae hyn yn ein pen -

263
00:22:34,700 --> 00:22:40,960
ac yna wedi y bobl gysylltiedig ag ef,

264
00:22:40,960 --> 00:22:48,460
ac yna mae gennym nod newydd gael ei mewnosod yn y dechrau,

265
00:22:48,460 --> 00:22:52,590
yna efallai y hyn yr ydym eisiau ei wneud?

266
00:22:55,220 --> 00:23:03,580
Beth fyddai o'i le gyda dim ond dweud yr wyf am gysylltu'r goch at y glas,

267
00:23:03,580 --> 00:23:05,790
oherwydd dyna yr un cyntaf?

268
00:23:05,790 --> 00:23:08,570
Beth fyddai'n digwydd yma?

269
00:23:08,570 --> 00:23:12,130
Byddai pob un o'r tri yn mynd ar goll.

270
00:23:12,130 --> 00:23:14,140
Felly, nid ydym am wneud hynny.

271
00:23:14,140 --> 00:23:21,430
Unwaith eto, rydym wedi dysgu bod angen i ni gael rhyw fath o pwyntydd dros dro.

272
00:23:21,430 --> 00:23:34,470
Gadewch i ni ddewis cael bwynt dros dro at y boi.

273
00:23:34,470 --> 00:23:39,640
Yna gallwn gael y glas un pwynt dros dro

274
00:23:39,640 --> 00:23:43,240
ac yna y pwynt coch at y glas.

275
00:23:43,240 --> 00:23:47,830
Y rheswm pam yr wyf yn defnyddio pobl yma oherwydd ein bod wir eisiau i ddychmygu

276
00:23:47,830 --> 00:23:53,180
dal ar i bobl a sicrhau bod gennym gyswllt â hwy

277
00:23:53,180 --> 00:23:57,590
cyn i ni adael i fynd o llaw arall neu rywbeth fel 'na.

278
00:24:05,630 --> 00:24:10,650
>> Nawr bod gennym synnwyr o restrau cysylltiedig - sut y gallwn greu rhestr cysylltiedig

279
00:24:10,650 --> 00:24:15,090
a chreu'r strwythurau ar gyfer y cynnwys y diffiniad math ar gyfer nod

280
00:24:15,090 --> 00:24:19,060
ac yna gwneud yn siwr bod gennym syniad inni am y pennaeth y rhestr cysylltiedig -

281
00:24:19,060 --> 00:24:23,210
unwaith y byddwn wedi hynny, ac rydym yn gwybod sut i groesi drwy amrywiaeth,

282
00:24:23,210 --> 00:24:28,200
mynediad gwahanol elfennau, rydym yn gwybod sut i fewnosod ac rydym yn gwybod sut i'w rhyddhau,

283
00:24:28,200 --> 00:24:30,260
yna gallwn fynd i mewn i gamsillafu.

284
00:24:30,260 --> 00:24:38,150
Fel arfer, mae gennym adran o gwestiynau a fydd yn cael a ddefnyddiwyd gennych i weithredu gyda rhestrau cysylltiedig

285
00:24:38,150 --> 00:24:41,750
a strwythurau gwahanol fel ciwiau a staciau.

286
00:24:41,750 --> 00:24:46,000
Yna, gallwn symud i mewn i gamsillafu.

287
00:24:46,000 --> 00:24:55,170
>> Camsillafiadau wedi bod yn y cod dosbarthu ychydig o ffeiliau pwysig.

288
00:24:55,170 --> 00:24:58,850
Yn gyntaf rydym yn sylwi bod gennym y Makefile yma,

289
00:24:58,850 --> 00:25:03,040
nad ydym wedi dod ar eu traws mewn gwirionedd o'r blaen.

290
00:25:03,040 --> 00:25:10,090
Os ydych yn edrych y tu mewn i'r ffolder pset5, byddech yn sylwi bod gennych. Ffeil h,

291
00:25:10,090 --> 00:25:12,530
yna mae gennych ddau. ffeiliau c.

292
00:25:12,530 --> 00:25:18,920
Beth mae hyn yn Makefile yn ei wneud o'r blaen, byddem yn jyst deipio gwneud ac yna enw'r rhaglen

293
00:25:18,920 --> 00:25:25,550
ac yna byddem yn gweld pob un o'r dadleuon hyn a baneri pasio i mewn i'r casglwr.

294
00:25:25,550 --> 00:25:30,580
Beth mae'r Makefile yn ei wneud yn ein galluogi i lunio nifer o ffeiliau ar yr un pryd

295
00:25:30,580 --> 00:25:34,650
ac yn pasio yn y baneri yr ydym am.

296
00:25:34,650 --> 00:25:41,300
Yma, rydym yn unig yn gweld bod yna ffeil pennawd yma.

297
00:25:41,300 --> 00:25:43,730
Yna rydym mewn gwirionedd yn cael dwy ffeil ffynhonnell.

298
00:25:43,730 --> 00:25:47,520
Mae gennym speller.c a dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Mae croeso i chi olygu'r Makefile os ydych yn dymuno.

300
00:25:54,560 --> 00:26:03,310
Sylwch mai yma os ydych yn teipio yn lân, yna beth mae'n ei wneud yw mewn gwirionedd yn cael gwared ar unrhyw beth

301
00:26:03,310 --> 00:26:06,340
dyna graidd.

302
00:26:06,340 --> 00:26:09,190
Os cawsoch wall, yn y bôn byddwch yn cael tomen craidd.

303
00:26:09,190 --> 00:26:13,260
Felly, bydd y ffeil bach hyll yn ymddangos yn eich cyfeiriadur o'r enw craidd.

304
00:26:13,260 --> 00:26:16,310
Youll 'angen i gael gwared ar y mwyn ei gwneud yn lân.

305
00:26:16,310 --> 00:26:20,940
Mae'n cael gwared unrhyw ffeiliau exe a. Ffeiliau o.

306
00:26:27,900 --> 00:26:30,220
>> Gadewch i ni edrych i mewn i dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Mae hwn yn dweud ei fod yn datgan ymarferoldeb geiriadur yn.

308
00:26:34,410 --> 00:26:39,530
Mae gennym hyd ar y mwyaf am unrhyw air yn y geiriadur.

309
00:26:39,530 --> 00:26:45,130
Rydym yn dweud bod hyn yn mynd i fod y gair hiraf posibl. Mae o hyd 45.

310
00:26:45,130 --> 00:26:48,900
Felly nid ydym yn mynd i gael unrhyw eiriau sy'n rhagori ar y darn hwnnw.

311
00:26:48,900 --> 00:26:50,980
Yma, rydym yn unig yn cael y prototeipiau swyddogaeth.

312
00:26:50,980 --> 00:26:55,290
Nid oes gennym y gweithredu gwirioneddol oherwydd dyna beth y byddwn yn ei wneud ar gyfer y pset.

313
00:26:55,290 --> 00:26:59,940
Ond beth mae hyn yn ei wneud yw gan ein bod yn delio gyda ffeiliau mawr yma

314
00:26:59,940 --> 00:27:06,650
ac ymarferoldeb ar raddfa fwy, mae'n ddefnyddiol i gael. ffeil h

315
00:27:06,650 --> 00:27:11,290
fel y gall rhywun arall ddarllen neu ddefnyddio eich cod yn deall beth sy'n mynd ymlaen.

316
00:27:11,290 --> 00:27:17,910
Ac efallai y maent am ei weithredu yn ceisio pe baech yn gwneud tablau hash neu i'r gwrthwyneb.

317
00:27:17,910 --> 00:27:21,850
Yna byddent yn dweud fy swyddogaeth llwyth,

318
00:27:21,850 --> 00:27:26,950
gweithredu gwirioneddol yn mynd i anghytuno, ond ni fydd hyn yn prototeip yn newid.

319
00:27:26,950 --> 00:27:33,280
Yma, rydym wedi gwirio, sy'n dychwelyd wir os gair a roddir yn y geiriadur.

320
00:27:33,280 --> 00:27:39,800
Yna, mae gennym lwyth, sydd yn y bôn yn cymryd mewn ffeil geiriadur

321
00:27:39,800 --> 00:27:44,360
ac yna yn llwytho'r i mewn rhywfaint o strwythur data.

322
00:27:44,360 --> 00:27:47,500
Mae gennym maint, a fydd, pan elwir, yn dychwelyd y maint eich geiriadur,

323
00:27:47,500 --> 00:27:50,310
faint o eiriau yn cael eu storio ynddo,

324
00:27:50,310 --> 00:27:54,390
ac yna dadlwytho, sy'n rhyddhau pob cof y gallech fod wedi cymryd

325
00:27:54,390 --> 00:27:57,900
wrth wneud eich geiriadur.

326
00:28:01,070 --> 00:28:03,590
>> Gadewch i ni edrych ar dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Rydym yn gweld ei bod yn edrych yn debyg iawn i dictionary.h, ac eithrio nawr mae'n mae pob un o'r rhain TODOs ynddo.

328
00:28:10,490 --> 00:28:16,980
Ac felly dyna yw eich swydd. Yn y pen draw, byddwch yn llenwi allan speller.c gyda phob un o'r cod hwn.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, pan yn rhedeg, yn cael ei wir yn mynd i wneud unrhyw beth,

330
00:28:21,540 --> 00:28:29,590
felly rydym yn edrych tuag at speller.c weld gweithredu gwirioneddol y gwirydd sillafu.

331
00:28:29,590 --> 00:28:32,060
Hyd yn oed os nad ydych chi'n mynd i fod yn golygu unrhyw un o'r cod hwn,

332
00:28:32,060 --> 00:28:38,050
mae'n bwysig i ddarllen, deall pryd mae llwyth alw, pan ydw i'n galw siec,

333
00:28:38,050 --> 00:28:42,350
dim ond er mwyn deall, fapio allan, gweld sut mae'r swyddogaeth yn gweithio.

334
00:28:42,350 --> 00:28:49,860
Rydym yn gweld ei fod yn gwirio ar gyfer y defnydd cywir.

335
00:28:49,860 --> 00:28:55,200
Yn y bôn, pan fydd rhywun yn rhedeg sillafu, mae hyn yn dangos ei fod yn ddewisol

336
00:28:55,200 --> 00:29:00,950
iddynt basio mewn ffeil geiriadur oherwydd mae mynd i fod yn ddiofyn ffeil geiriadur.

337
00:29:00,950 --> 00:29:05,410
Ac yna mae'n rhaid iddynt basio yn y testun i fod yn sillafu gwirio.

338
00:29:05,410 --> 00:29:11,410
yn delio rusage gydag amser oherwydd bod rhan o'r pset y byddwn yn delio â ddiweddarach

339
00:29:11,410 --> 00:29:14,790
nid yn unig yn cael gweithredu gywiriadur gweithio

340
00:29:14,790 --> 00:29:17,190
ond mewn gwirionedd yn cael i fod yn gyflym.

341
00:29:17,190 --> 00:29:22,040
Ac felly, yna dyna lle rusage yn mynd i ddod i mewn

342
00:29:22,040 --> 00:29:28,740
Yma, rydym yn gweld y galwad cyntaf i un o'n ffeiliau dictionary.c, sef llwyth.

343
00:29:28,740 --> 00:29:34,720
Llwyth yn dychwelyd gwir neu ffug - yn wir ar lwyddiant, ffug ar fethiant.

344
00:29:34,720 --> 00:29:41,400
Felly, os nad yw'r geiriadur yn cael ei lwytho yn gywir, yna bydd y speller.c yn dychwelyd 1 a rhoi'r gorau iddi.

345
00:29:41,400 --> 00:29:47,920
Ond os bydd yn gwneud llwyth yn gywir, yna mae'n mynd i barhau.

346
00:29:47,920 --> 00:29:50,740
Rydym yn parhau, ac rydym yn gweld rhywfaint o ffeil gallaf / O yma,

347
00:29:50,740 --> 00:29:56,210
lle mae'n mynd i fod yn delio ag agor y ffeil testun.

348
00:29:56,210 --> 00:30:04,640
Yma, beth mae hyn yn ei wneud yn sillafu profion bob un gair yn y testun.

349
00:30:04,640 --> 00:30:09,270
Felly beth speller.c yn ei wneud yn iawn yma yn ailadrodd dros bob un o'r geiriau yn y ffeil testun

350
00:30:09,270 --> 00:30:12,790
ac yna eu gwirio yn y geiriadur.

351
00:30:24,680 --> 00:30:32,350
Yma, mae gennym Boolean gamsillafu a fydd yn gweld os gwiriad yn dychwelyd wir neu beidio.

352
00:30:32,350 --> 00:30:37,110
Os ydy'r gair yn mewn gwirionedd yn y geiriadur, yna bydd gwiriad yn dychwelyd yn wir.

353
00:30:37,110 --> 00:30:39,760
Mae hynny'n golygu nad yw'r gair yn cael ei gamsillafu.

354
00:30:39,760 --> 00:30:45,330
Byddai gamsillafu Felly fod yn ffug, a dyna pam mae gennym y bang yno, yr arwydd.

355
00:30:45,330 --> 00:30:56,320
Rydym yn dal i fynd, ac yna mae'n cadw golwg ar faint o gamsillafu geiriau

356
00:30:56,320 --> 00:30:58,910
sydd yn y ffeil.

357
00:30:58,910 --> 00:31:03,870
Mae'n parhau a ddaw i ben ar y ffeil.

358
00:31:03,870 --> 00:31:09,250
Yna dyma, mae'n adrodd faint o eiriau wedi'u camsillafu a gawsoch.

359
00:31:09,250 --> 00:31:12,680
Mae'n cyfrifo faint o amser a gymerwyd i lwytho'r geiriadur,

360
00:31:12,680 --> 00:31:15,080
faint o amser a gymerwyd i wirio ei fod,

361
00:31:15,080 --> 00:31:18,510
faint o amser a gymerwyd i gyfrifo maint,

362
00:31:18,510 --> 00:31:21,260
y dylai, gan y byddwn yn mynd ymlaen, fod yn fach iawn,

363
00:31:21,260 --> 00:31:25,390
ac yna faint o amser a gymerwyd i ddadlwytho'r geiriadur.

364
00:31:25,390 --> 00:31:27,700
Yma i fyny uchod rydym yn gweld yr alwad i ddadlwytho yma.

365
00:31:27,700 --> 00:31:52,690
Os byddwn yn gwirio ar gyfer maint yma,

366
00:31:52,690 --> 00:31:59,050
yna rydym yn gweld bod yma yr alwad i faint pan fydd yn penderfynu maint y geiriadur.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Ein tasg ar gyfer y pset yw gweithredu llwyth, a fydd yn llwytho'r geiriadur

369
00:32:10,920 --> 00:32:15,480
strwythur data - pa un bynnag a ddewiswch, boed yn dabl hash neu roi cynnig ar -

370
00:32:15,480 --> 00:32:18,810
gyda geiriau o'r ffeil geiriadur.

371
00:32:18,810 --> 00:32:25,290
Yna byddwch yn cael faint, a fydd yn dychwelyd y nifer o eiriau yn y geiriadur.

372
00:32:25,290 --> 00:32:29,860
Ac os ydych yn gweithredu llwyth mewn ffordd smart, yna dylai maint fod yn eithaf hawdd.

373
00:32:29,860 --> 00:32:33,860
Yna, rydych wedi gwirio, a fydd yn gwirio os yw gair a roddir yn y geiriadur.

374
00:32:33,860 --> 00:32:38,690
Felly speller.c pasio mewn llinyn, ac yna rhaid i chi wirio a yw'r llinyn

375
00:32:38,690 --> 00:32:41,610
wedi'i gynnwys o fewn eich geiriadur.

376
00:32:41,610 --> 00:32:46,750
Hysbysiad bod gennym gyffredinol, mae geiriaduron safonol,

377
00:32:46,750 --> 00:32:53,020
ond yn yr pset, yn y bôn unrhyw eiriadur a basiwyd yn mewn unrhyw iaith.

378
00:32:53,020 --> 00:32:57,040
Felly, ni allwn gymryd yn ganiataol bod y gair Y tu mewn.

379
00:32:57,040 --> 00:33:03,090
Gallai'r Foobar gair yn cael ei ddiffinio mewn geiriadur penodol yr ydym yn pasio i mewn

380
00:33:03,090 --> 00:33:07,920
Ac yna rydym wedi dadlwytho, sy'n rhyddhau y geiriadur ar y cof.

381
00:33:07,920 --> 00:33:11,930
>> Yn gyntaf, hoffwn i fynd dros y dull tabl hash

382
00:33:11,930 --> 00:33:14,630
ynghylch sut y gallem weithredu pob un o'r rhai pedair swyddogaeth,

383
00:33:14,630 --> 00:33:18,650
ac yna byddaf yn mynd dros y ceisio dull, sut rydym yn gweithredu'r rhai pedair swyddogaeth,

384
00:33:18,650 --> 00:33:22,720
ac ar ddiwedd y sgwrs am rai awgrymiadau cyffredinol pan fyddwch yn gwneud y pset

385
00:33:22,720 --> 00:33:27,870
a hefyd sut y byddwch yn gallu defnyddio Valgrind i wirio am ollyngiadau cof.

386
00:33:27,870 --> 00:33:30,550
>> Gadewch i ni fynd i mewn i'r dull tabl hash.

387
00:33:30,550 --> 00:33:35,910
Mae tabl hash yn cynnwys rhestr o fwcedi.

388
00:33:35,910 --> 00:33:43,010
Mae pob gwerth, pob gair, yn mynd i fynd i mewn i un o'r rhain bwcedi.

389
00:33:43,010 --> 00:33:53,200
Mae tabl hash yn ddelfrydol gyfartal yn dosbarthu pob un o'r gwerthoedd hyn eich bod yn pasio yn

390
00:33:53,200 --> 00:33:57,160
ac yna poblogi'r yn y bwced fel bod pob bwced

391
00:33:57,160 --> 00:34:02,000
Mae am nifer gyfartal o werthoedd ynddo.

392
00:34:02,000 --> 00:34:09,630
Mae'r strwythur ar gyfer tabl hash, mae gennym amrywiaeth o rhestrau cysylltiedig.

393
00:34:09,630 --> 00:34:17,900
Beth rydym yn ei wneud yw pan fyddwn yn pasio mewn gwerth, byddwn yn gwirio ble y dylai'r gwerth perthyn,

394
00:34:17,900 --> 00:34:23,840
sy'n bwced mae'n perthyn iddo, ac yna ei ddodi yn y rhestr cysylltiedig sy'n gysylltiedig â'r bwced.

395
00:34:23,840 --> 00:34:28,199
Yma, yr hyn sydd gennyf yn swyddogaeth hash.

396
00:34:28,199 --> 00:34:31,320
Mae'n tabl hash int.

397
00:34:31,320 --> 00:34:38,540
Felly, ar gyfer y bwced cyntaf, unrhyw gyfanrifau llai na 10 yn mynd i mewn i'r bwced cyntaf.

398
00:34:38,540 --> 00:34:42,190
Unrhyw gyfanrifau yn uwch na 10 ond islaw 20 yn mynd i mewn i'r ail,

399
00:34:42,190 --> 00:34:44,179
ac yna yn y blaen ac yn y blaen.

400
00:34:44,179 --> 00:34:52,370
I mi, mae pob bwced yn cynrychioli rhifau hyn.

401
00:34:52,370 --> 00:34:59,850
Fodd bynnag, yn dweud bawn yn pasio yn 50, er enghraifft.

402
00:34:59,850 --> 00:35:07,490
Mae'n ymddangos fel pe y tri cyntaf yn cynnwys ystod o deg rhif.

403
00:35:07,490 --> 00:35:12,570
Ond yr wyf am ganiatáu fy tabl hash i'w cymryd mewn unrhyw fath o gyfanrifau,

404
00:35:12,570 --> 00:35:19,860
felly, yna byddai'n rhaid i mi hidlo allan yr holl rifau uwch na 30 i mewn i'r bwced diwethaf.

405
00:35:19,860 --> 00:35:26,660
Ac felly, yna a fyddai'n arwain at fath o dabl anghytbwys hash.

406
00:35:31,330 --> 00:35:35,640
I ailadrodd, tabl hash yn unig yw amrywiaeth o bwcedi

407
00:35:35,640 --> 00:35:38,590
lle mae pob bwced yn rhestr cysylltiedig.

408
00:35:38,590 --> 00:35:43,730
Ac felly i benderfynu lle mae pob gwerth yn mynd, a bwced yn mynd i mewn i,

409
00:35:43,730 --> 00:35:46,260
ydych yn mynd i eisiau hyn a elwir yn swyddogaeth hash

410
00:35:46,260 --> 00:35:55,010
sy'n cymryd gwerth ac yna'n dweud bod hyn yn cyfateb i werth bwced penodol.

411
00:35:55,010 --> 00:36:00,970
Felly, uwchben yn yr enghraifft hon, fy swyddogaeth hash yn cymryd pob gwerth.

412
00:36:00,970 --> 00:36:03,020
Mae'n wirio a oedd yn llai na 10.

413
00:36:03,020 --> 00:36:05,360
Os oedd, byddai'n ei roi yn y bwced cyntaf.

414
00:36:05,360 --> 00:36:08,910
Mae'n gwirio p'un a yw'n llai na 20, yn rhoi i mewn yr ail, os yw'n wir,

415
00:36:08,910 --> 00:36:12,880
gwiriadau os yw'n llai na 30, ac yna'n rhoi i mewn i'r bwced trydydd,

416
00:36:12,880 --> 00:36:16,990
ac yna popeth arall yn unig yn disgyn i'r bwced pedwerydd.

417
00:36:16,990 --> 00:36:20,110
Felly, pryd bynnag y byddwch yn cael gwerth, eich swyddogaeth hash

418
00:36:20,110 --> 00:36:25,420
Bydd yn gosod y gwerth i mewn i'r bwced priodol.

419
00:36:25,420 --> 00:36:32,430
Mae'r swyddogaeth hash y bôn mae angen i wybod faint o fwcedi gennych.

420
00:36:32,430 --> 00:36:37,960
Eich maint y tabl hash, mae nifer o bwcedi sydd gennych,

421
00:36:37,960 --> 00:36:41,190
mae hynny'n mynd i fod yn nifer penodedig sydd hyd i chi, er mwyn i chi benderfynu,

422
00:36:41,190 --> 00:36:43,590
ond mae'n mynd i fod yn nifer penodedig.

423
00:36:43,590 --> 00:36:51,840
Felly eich swyddogaeth hash byddan nhw'n dibynnu ar hynny i benderfynu pa bwced i bob allweddol yn mynd i mewn i

424
00:36:51,840 --> 00:36:54,450
o'r fath fod yn cael ei dosbarthu'n gyfartal.

425
00:36:56,150 --> 00:37:03,820
Yn debyg i ein gweithrediad rhestrau cysylltiedig, yn awr bob nod yn y tabl hash

426
00:37:03,820 --> 00:37:07,000
mewn gwirionedd yn mynd i gael torgoch fath.

427
00:37:07,000 --> 00:37:14,340
Felly mae gennym amrywiaeth torgoch o'r enw gair ac yna un arall pwyntydd i'r nod nesaf,

428
00:37:14,340 --> 00:37:19,010
sy'n gwneud synnwyr oherwydd mae'n mynd i fod yn rhestr cysylltiedig.

429
00:37:19,010 --> 00:37:24,350
Cofiwch pan fyddwn wedi cysylltu rhestrau, fe wnes i * nod a elwir yn bennaeth

430
00:37:24,350 --> 00:37:31,060
oedd yn pwyntio at y nod cyntaf yn y rhestr cysylltiedig.

431
00:37:31,060 --> 00:37:34,020
Ond ar gyfer ein bwrdd hash, oherwydd mae gennym restrau cysylltiedig lluosog,

432
00:37:34,020 --> 00:37:37,520
hyn yr ydym ei eisiau yw rydym am i'n tabl hash i fod fel, "Beth yw fwced?"

433
00:37:37,520 --> 00:37:43,340
Bwced yn unig yw rhestr o awgrymiadau nod,

434
00:37:43,340 --> 00:37:50,620
ac felly mae pob elfen yn y bwced mewn gwirionedd yn pwyntio at ei restr cysylltiedig cyfatebol.

435
00:37:56,180 --> 00:38:01,520
I fynd yn ôl at y sgematig, gwelwch fod y bwcedi eu hunain yn y saethau,

436
00:38:01,520 --> 00:38:06,980
Nid yw nodau gwirioneddol.

437
00:38:11,680 --> 00:38:16,420
Un eiddo hanfodol o swyddogaethau hash yw eu bod yn benderfynedig.

438
00:38:16,420 --> 00:38:19,440
Mae hynny'n golygu bod pryd bynnag y byddwch hash y rhif 2,

439
00:38:19,440 --> 00:38:22,270
dylai bob amser yn dychwelyd yr un bwced.

440
00:38:22,270 --> 00:38:26,440
Mae pob gwerth unigol sy'n mynd i mewn i'r swyddogaeth hash, os dro ar ôl tro,

441
00:38:26,440 --> 00:38:29,690
rhaid iddo gael y mynegai un.

442
00:38:29,690 --> 00:38:34,210
Felly eich swyddogaeth hash yn dychwelyd y mynegai y rhesi

443
00:38:34,210 --> 00:38:38,530
lle mae'r gwerth yn perthyn.

444
00:38:38,530 --> 00:38:41,790
Fel y soniais o'r blaen, mae nifer o bwcedi yn sefydlog,

445
00:38:41,790 --> 00:38:49,630
ac felly eich mynegai eich bod yn dychwelyd wedi i fod yn llai na nifer y bwcedi

446
00:38:49,630 --> 00:38:52,680
ond yn fwy na 0.

447
00:38:52,680 --> 00:39:00,780
Y rheswm pam y mae gennym swyddogaethau hash hytrach na dim ond un rhestr cysylltiedig sengl

448
00:39:00,780 --> 00:39:09,290
neu un amrywiaeth sengl yw ein bod eisiau gallu i neidio i adran benodol yn hawdd y rhan fwyaf o

449
00:39:09,290 --> 00:39:11,720
os ydym yn gwybod y nodweddiadol o werth -

450
00:39:11,720 --> 00:39:14,760
yn hytrach na gorfod chwilio drwy'r geiriadur cyfan cyfan,

451
00:39:14,760 --> 00:39:18,320
gallu i neidio i adran benodol ohono.

452
00:39:19,880 --> 00:39:24,440
Dylai eich swyddogaeth hash yn cymryd i ystyriaeth yn ddelfrydol,

453
00:39:24,440 --> 00:39:28,980
pob bwced Mae tua yr un nifer o allweddi.

454
00:39:28,980 --> 00:39:35,040
Ers y tabl hash yn gyfres o restrau cysylltiedig,

455
00:39:35,040 --> 00:39:38,480
yna bydd y rhestrau cysylltiedig eu hunain yn mynd i gael mwy nag un nod.

456
00:39:38,480 --> 00:39:43,210
Yn yr enghraifft flaenorol, dau rif gwahanol, er nad oeddent yn gyfartal,

457
00:39:43,210 --> 00:39:46,950
pan stwnsio, yn dychwelyd y mynegai un.

458
00:39:46,950 --> 00:39:53,620
Felly, pan fyddwch yn delio â geiriau, un gair wrth stwnsio

459
00:39:53,620 --> 00:39:57,450
byddai gwerth hash un gair arall.

460
00:39:57,450 --> 00:40:04,140
Dyna beth yr ydym yn galw wrthdrawiad, pan fydd gennym nod, pan stwnsio,

461
00:40:04,140 --> 00:40:09,610
nid yw'r rhestr yn gysylltiedig yn y bwced yn wag.

462
00:40:09,610 --> 00:40:14,180
Mae'r dechneg yr ydym yn galw yno yn llinol holi,

463
00:40:14,180 --> 00:40:22,550
ble rydych yn mynd i mewn i'r rhestr cysylltiedig ac yna dod o hyd lle rydych chi eisiau i fewnosod y nod

464
00:40:22,550 --> 00:40:25,520
oherwydd bod gennych gwrthdrawiad.

465
00:40:25,520 --> 00:40:28,070
Gallwch weld y gallai fod yn fasnach-off yma, dde?

466
00:40:28,070 --> 00:40:33,760
Os oes gennych chi bwrdd bach iawn hash, mae nifer fach iawn o bwcedi,

467
00:40:33,760 --> 00:40:36,380
yna rydych chi'n mynd i gael llawer o wrthdrawiadau.

468
00:40:36,380 --> 00:40:40,460
Ond wedyn, os byddwch yn gwneud tabl mawr iawn hash,

469
00:40:40,460 --> 00:40:44,110
mae'n debyg eich bod yn mynd i leihau gwrthdrawiadau,

470
00:40:44,110 --> 00:40:47,170
ond mae'n mynd i fod yn strwythur data mawr iawn.

471
00:40:47,170 --> 00:40:49,310
Mae mynd i fod yn fasnach-offs â hynny.

472
00:40:49,310 --> 00:40:51,310
Felly, pan fyddwch yn gwneud eich pset, ceisiwch i chwarae o gwmpas

473
00:40:51,310 --> 00:40:54,210
rhwng efallai yn gwneud tabl llai hash

474
00:40:54,210 --> 00:41:02,100
ond wedyn gwybod ei fod yn mynd i gymryd ychydig mwy o amser i deithio ar draws y gwahanol elfennau

475
00:41:02,100 --> 00:41:04,270
y rhestrau hynny cysylltiedig.

476
00:41:04,270 --> 00:41:09,500
>> Pa llwyth yn mynd i wneud yw ailadrodd dros bob gair yn y geiriadur.

477
00:41:09,500 --> 00:41:13,180
Mae'n mynd yn arwydd o'r ffeil geiriadur.

478
00:41:13,180 --> 00:41:18,050
Felly, rydych yn mynd i fanteisio ar y ffeil I / O swyddogaethau yr ydych yn meistroli yn pset4

479
00:41:18,050 --> 00:41:23,010
ac yn ailadrodd dros bob gair yn y geiriadur.

480
00:41:23,010 --> 00:41:26,620
Rydych am bob gair yn y geiriadur i ddod yn nod newydd,

481
00:41:26,620 --> 00:41:32,730
a ydych yn mynd i roi pob un o'r nodau tu mewn i'ch data geiriadur strwythur.

482
00:41:32,730 --> 00:41:36,560
Pryd bynnag y byddwch yn cael gair newydd, byddwch yn gwybod ei fod yn mynd i fod yn nod.

483
00:41:36,560 --> 00:41:46,590
Felly, gallwch fynd yn syth ac yn malloc pwyntydd nod ar gyfer pob gair newydd sydd gennych.

484
00:41:46,590 --> 00:41:52,610
Yma Rwy'n galw fy nod new_node pwyntydd ac rwy'n mallocing beth? Mae maint y nod.

485
00:41:52,610 --> 00:41:59,190
Yna i ddarllen y llinyn gwirioneddol o ffeil, oherwydd bod y geiriadur yn cael ei storio mewn gwirionedd

486
00:41:59,190 --> 00:42:03,340
gan gair ac yna llinell newydd, yr hyn y gallwn fanteisio ar

487
00:42:03,340 --> 00:42:06,520
yw'r fscanf swyddogaeth,

488
00:42:06,520 --> 00:42:10,280
lle ffeil yn y ffeil geiriadur ein bod yn pasio i mewn,

489
00:42:10,280 --> 00:42:18,900
felly mae'n sganiau y ffeil ar gyfer llinyn a lleoedd sy'n llinyn i mewn i'r ddadl ddiwethaf.

490
00:42:18,900 --> 00:42:26,890
Os ydych yn cofio yn ôl i un o'r darlithoedd, pan fyddwn yn mynd dros

491
00:42:26,890 --> 00:42:29,320
a math o blicio yr haenau yn ôl ar y llyfrgell CS50,

492
00:42:29,320 --> 00:42:33,430
gwelsom gweithredu fscanf yno.

493
00:42:33,430 --> 00:42:37,700
I fynd yn ôl i fscanf, mae gennym y ffeil ein bod yn darllen,

494
00:42:37,700 --> 00:42:42,570
rydym yn chwilio am llinyn yn y ffeil, ac yna rydym yn gosod i mewn i

495
00:42:42,570 --> 00:42:48,340
yma rwyf wedi new_node-> gair oherwydd new_node yn pwyntydd nod,

496
00:42:48,340 --> 00:42:50,380
nid nod gwirioneddol.

497
00:42:50,380 --> 00:42:57,100
Felly, yna i ddim yn dweud new_node, Dw i eisiau mynd at y nod ei fod yn pwyntio at

498
00:42:57,100 --> 00:43:01,190
ac yna pennu bod gwerth i air.

499
00:43:01,190 --> 00:43:08,540
Rydym yn awyddus i yna cymerwch y gair a rhowch i mewn i'r tabl hash.

500
00:43:08,540 --> 00:43:13,750
Sylweddoli bod wnaethom new_node pwyntydd nod

501
00:43:13,750 --> 00:43:18,230
oherwydd ein bod yn mynd i eisiau gwybod beth yw cyfeiriad y nod yn

502
00:43:18,230 --> 00:43:23,940
pan fyddwn yn mewnosod yn oherwydd bod y strwythur y nodau eu hunain, y strwythur,

503
00:43:23,940 --> 00:43:26,380
yw eu bod yn cael pwyntydd i nod newydd.

504
00:43:26,380 --> 00:43:30,820
Felly, yna beth yw cyfeiriad y nod yn mynd i gyfeirio at?

505
00:43:30,820 --> 00:43:34,550
Sy'n mynd i'r afael yn mynd i fod new_node.

506
00:43:34,550 --> 00:43:42,140
Ydy hynny'n gwneud synnwyr, pam ein bod yn gwneud new_node a * nod yn hytrach na nod?

507
00:43:43,700 --> 00:43:45,700
Iawn.

508
00:43:45,700 --> 00:43:52,840
Mae gennym air. Bod y gwerth hwnnw'n new_node-> gair.

509
00:43:52,840 --> 00:43:55,970
Sy'n cynnwys y gair o'r geiriadur yr ydym am eu mewnbwn.

510
00:43:55,970 --> 00:44:00,210
Felly, yr hyn rydym am ei wneud yw ein bod am alw ein swyddogaeth hash ar y llinyn

511
00:44:00,210 --> 00:44:03,780
oherwydd bod ein swyddogaeth hash cymryd mewn llinyn ac yna dychwelyd i ni cyfanrif,

512
00:44:03,780 --> 00:44:12,090
os yw'r cyfanrif yw'r mynegai lle hashtable ar y mynegai yn cynrychioli y bwced.

513
00:44:12,090 --> 00:44:18,260
Rydym yn awyddus i gymryd y mynegai ac yna mynd i'r mynegai y tabl hash

514
00:44:18,260 --> 00:44:26,960
ac yna ddefnyddio'r rhestr gysylltiedig i osod y nod yn y new_node.

515
00:44:26,960 --> 00:44:31,950
Cofiwch fod bynnag y byddwch yn penderfynu i fewnosod eich nod,

516
00:44:31,950 --> 00:44:34,370
boed hynny yn y canol os ydych am i ddatrys y broblem

517
00:44:34,370 --> 00:44:39,650
neu ar ddechrau neu ar y diwedd, dim ond gwneud yn siwr bod eich nod olaf bob amser yn cyfeirio at NULL

518
00:44:39,650 --> 00:44:46,730
oherwydd dyna'r unig ffordd yr ydym yn gwybod lle mae'r elfen olaf ein rhestr cysylltiedig yn.

519
00:44:50,790 --> 00:44:59,710
>> Os maint yn gyfanrif sy'n cynrychioli nifer y geiriau mewn geiriadur,

520
00:44:59,710 --> 00:45:03,060
yna un ffordd o wneud hyn yw bod pryd bynnag y maint ei alw'n

521
00:45:03,060 --> 00:45:05,840
rydym yn mynd trwy bob elfen yn ein tabl hash

522
00:45:05,840 --> 00:45:09,410
ac yna ailadrodd drwy bob rhestr gysylltiedig o fewn y tabl hash

523
00:45:09,410 --> 00:45:13,770
ac yna cyfrifwch hyd hynny, gynyddu ein cownter gan 1 1.

524
00:45:13,770 --> 00:45:16,580
Ond bob tro y maint ei alw, mae hynny'n mynd i gymryd amser hir

525
00:45:16,580 --> 00:45:22,120
oherwydd ein bod yn mynd i fod yn llinol holi pob un rhestr cysylltiedig.

526
00:45:22,120 --> 00:45:30,530
Yn hytrach, mae'n mynd i fod yn llawer haws os ydych yn cadw golwg ar faint o eiriau yn cael eu trosglwyddo i mewn

527
00:45:30,530 --> 00:45:36,330
Felly, yna os ydych yn cynnwys y cownter o fewn eich swyddogaeth llwyth

528
00:45:36,330 --> 00:45:42,430
bod diweddariadau yn ôl yr angen, yna cownter, os ydych yn gosod i newidyn byd-eang,

529
00:45:42,430 --> 00:45:44,930
yn gallu cael mynediad yn ôl maint.

530
00:45:44,930 --> 00:45:51,450
Felly, beth yw maint y gallai ei wneud yw yn syml mewn un llinell, dim ond dychwelyd y gwerth cownter,

531
00:45:51,450 --> 00:45:55,500
maint y geiriadur, yr ydych eisoes yn delio â hwy yn llwyth.

532
00:45:55,500 --> 00:46:05,190
Dyna beth yr wyf yn golygu pan fyddaf yn dweud os ydych yn gweithredu llwyth mewn ffordd ddefnyddiol,

533
00:46:05,190 --> 00:46:08,540
Yna maint yn mynd i fod yn eithaf hawdd.

534
00:46:08,540 --> 00:46:11,350
>> Felly, yn awr rydym yn cael i wirio.

535
00:46:11,350 --> 00:46:15,960
Nawr rydym yn delio â geiriau o'r testun mewnbwn ffeil,

536
00:46:15,960 --> 00:46:19,910
ac felly rydym yn mynd i fod yn gwirio a yw pob un o'r geiriau hynny mewnbwn

537
00:46:19,910 --> 00:46:22,520
mewn gwirionedd yn y geiriadur neu beidio.

538
00:46:22,520 --> 00:46:26,520
Yn debyg i Scramble, rydym am i ganiatáu ar gyfer ansensitifrwydd achos.

539
00:46:26,520 --> 00:46:32,110
Byddwch am wneud yn siŵr bod yr holl eiriau pasio, hyd yn oed er eu bod yn achos cymysg,

540
00:46:32,110 --> 00:46:37,840
pan elwir gyda cymharu llinyn, yn cyfateb.

541
00:46:37,840 --> 00:46:42,450
Mae'r geiriau yn y ffeiliau geiriadur testun mewn gwirionedd i gyd llythrennau bach.

542
00:46:42,450 --> 00:46:49,280
Peth arall yw y gallwch gymryd yn ganiataol bod pob gair basiwyd yn, bob llinyn,

543
00:46:49,280 --> 00:46:53,200
yn mynd i fod naill ai yn yr wyddor neu gynnwys collnodau.

544
00:46:53,200 --> 00:46:58,010
Collnodau yn mynd i fod yn eiriau dilys yn ein geiriadur.

545
00:46:58,010 --> 00:47:06,470
Felly, os oes gennych air gyda collnod S, dyna gair dilys go iawn yn eich geiriadur

546
00:47:06,470 --> 00:47:11,650
mae hynny'n mynd i fod yn un o'r nodau yn eich tabl hash.

547
00:47:13,470 --> 00:47:18,350
Gwiriwch yn gweithredu gyda os yw'r gair yn bodoli, yna mae'n rhaid i fod yn ein tabl hash.

548
00:47:18,350 --> 00:47:22,210
Os yw'r gair yn y geiriadur, yna mae'r holl eiriau yn y geiriadur yn y tabl hash,

549
00:47:22,210 --> 00:47:26,560
felly gadewch i ni edrych am y gair yn y tabl hash.

550
00:47:26,560 --> 00:47:29,250
Rydym yn gwybod bod ers i ni weithredu ein swyddogaeth hash

551
00:47:29,250 --> 00:47:38,420
fel bod pob gair unigryw yn cael ei stwnsio bob amser i'r un gwerth,

552
00:47:38,420 --> 00:47:43,340
yna rydym yn gwybod, yn hytrach na chwilio drwy ein tabl hash cyfanwaith i gyd,

553
00:47:43,340 --> 00:47:48,310
gallwn mewn gwirionedd ddod o hyd i'r rhestr cysylltiedig y dylai'r gair yn perthyn iddo.

554
00:47:48,310 --> 00:47:51,850
Os yn y geiriadur, yna byddai'n fod yn y bwced.

555
00:47:51,850 --> 00:47:57,140
Beth allwn ni ei wneud, os gair yn enw ein llinyn basio i mewn,

556
00:47:57,140 --> 00:48:01,560
gallwn dim ond hash y gair ac edrych ar y rhestr sy'n gysylltiedig

557
00:48:01,560 --> 00:48:06,410
ar werth hashtable [hash (word)].

558
00:48:06,410 --> 00:48:12,410
Oddi yno, yr hyn y gallwn ei wneud yw ein bod wedi is-set lai o nodau i chwilio am y gair hwn,

559
00:48:12,410 --> 00:48:16,770
ac felly gallwn groesi'r rhestr cysylltiedig, gan ddefnyddio enghraifft o gyfnod cynharach yn y walkthrough,

560
00:48:16,770 --> 00:48:24,110
ac yna galw llinyn cymharu ar y gair lle bynnag y cyrchwr yn pwyntio at,

561
00:48:24,110 --> 00:48:28,430
y gair, a gweld a yw'r cymharu.

562
00:48:30,280 --> 00:48:35,110
Yn dibynnu ar y ffordd yr ydych yn trefnu eich swyddogaeth hash,

563
00:48:35,110 --> 00:48:39,260
os caiff ei datrys, efallai y byddwch yn gallu dychwelyd ffug ychydig yn gynharach,

564
00:48:39,260 --> 00:48:43,440
ond os yw'n heb eu didoli, yna rydych eisiau parhau croesi drwy eich rhestr cysylltiedig

565
00:48:43,440 --> 00:48:46,480
nes i chi ddod o hyd i'r elfen olaf y rhestr.

566
00:48:46,480 --> 00:48:53,320
Ac os nad ydych wedi dod o hyd i'r gair gan yr adeg y byddwch wedi cyrraedd diwedd y rhestr cysylltiedig,

567
00:48:53,320 --> 00:48:56,890
hynny'n golygu nad yw eich gair yn bodoli yn y geiriadur,

568
00:48:56,890 --> 00:48:59,410
ac fel y gair yn annilys,

569
00:48:59,410 --> 00:49:02,730
a dylid gwirio dychwelyd ffug.

570
00:49:02,730 --> 00:49:09,530
>> Nawr rydym yn dod i ddadlwytho, lle rydym eisiau i ryddhau yr holl nodau yr ydym wedi malloc'd,

571
00:49:09,530 --> 00:49:14,050
mor rhad ac am ddim pob un o'r nodau y tu mewn ein tabl hash.

572
00:49:14,050 --> 00:49:20,270
Rydym yn mynd i eisiau i ailadrodd dros yr holl rhestrau cysylltiedig ac yn rhydd pob un o'r nodau yn hynny.

573
00:49:20,270 --> 00:49:29,350
Os edrychwch uchod yn y walkthrough at yr enghraifft lle rydym yn rhyddhau rhestr cysylltiedig,

574
00:49:29,350 --> 00:49:35,140
yna byddwch am ailadrodd y broses ar gyfer pob elfen yn y tabl hash.

575
00:49:35,140 --> 00:49:37,780
A byddaf yn mynd dros hyn tuag at ddiwedd y walkthrough,

576
00:49:37,780 --> 00:49:46,600
ond Valgrind yn offeryn lle gallwch weld os ydych wedi rhyddhau yn briodol

577
00:49:46,600 --> 00:49:53,600
pob nod eich bod wedi malloc'd neu unrhyw beth arall yr ydych wedi malloc'd, unrhyw pwyntydd arall.

578
00:49:55,140 --> 00:50:00,530
Felly dyna tablau hash, lle mae gennym nifer cyfyngedig o bwcedi

579
00:50:00,530 --> 00:50:09,220
a swyddogaeth hash a fydd yn cymryd gwerth ac yna pennu bod gwerth i fwced penodol.

580
00:50:09,220 --> 00:50:13,340
>> Nawr rydym yn dod i gais.

581
00:50:13,340 --> 00:50:18,750
Ceisiau fath o edrych fel hyn, a byddaf hefyd yn tynnu allan enghraifft.

582
00:50:18,750 --> 00:50:25,630
Yn y bôn, mae gennych amrywiaeth gyfan o lythyrau posibl,

583
00:50:25,630 --> 00:50:29,210
ac yna pryd bynnag y byddwch chi'n adeiladu gair,

584
00:50:29,210 --> 00:50:36,490
gall llythyr yn cael ei gysylltu am eiriadur i ystod eang o bosibiliadau.

585
00:50:36,490 --> 00:50:40,840
Rhai o eiriau yn dechrau gyda C ond wedyn yn parhau gyda A,

586
00:50:40,840 --> 00:50:42,960
ond mae eraill yn parhau gyda O, er enghraifft.

587
00:50:42,960 --> 00:50:51,090
Mae trie yn ffordd o ddychmygu holl gyfuniadau posibl o'r geiriau hynny.

588
00:50:51,090 --> 00:50:59,070
Mae trie yn mynd i gadw golwg ar y dilyniant o lythrennau sy'n cynnwys geiriau,

589
00:50:59,070 --> 00:51:08,280
fforchio pan fo angen, pryd y gall un llythyr yn cael ei ddilyn gan lluosog o lythyrau,

590
00:51:08,280 --> 00:51:16,630
ac ar y diwedd yn nodi ar bob pwynt a yw'r gair yn ddilys neu beidio

591
00:51:16,630 --> 00:51:30,120
oherwydd os ydych yn sillafu y gair MAT, MA Nid wyf yn credu yn air ddilys, ond MAT yw.

592
00:51:30,120 --> 00:51:37,820
Ac felly yn eich trie, byddai'n dangos bod ar ôl MAT sydd mewn gwirionedd gair dilys.

593
00:51:41,790 --> 00:51:48,590
Mae pob nod yn ein trie mewn gwirionedd yn mynd i gynnwys amrywiaeth o awgrymiadau nod,

594
00:51:48,590 --> 00:51:52,970
ac rydym yn mynd i gael, yn benodol, 27 o'r rhai awgrymiadau nod,

595
00:51:52,970 --> 00:52:00,550
un ar gyfer pob llythyren yn y wyddor yn ogystal â chymeriad collnod.

596
00:52:00,550 --> 00:52:10,450
Mae pob elfen yn y casgliad yn cael ei hun yn mynd i dynnu i un arall nod.

597
00:52:10,450 --> 00:52:14,020
Felly, os yw'r nod yn NULL, os nad oes unrhyw ôl hynny,

598
00:52:14,020 --> 00:52:20,550
yna rydym yn gwybod nad oes unrhyw lythyrau pellach yn y dilyniant gair.

599
00:52:20,550 --> 00:52:26,950
Ond os nad yw nod yw NULL, sy'n golygu bod mwy o lythyrau yn y dilyniant llythyr.

600
00:52:26,950 --> 00:52:32,160
Ac yna ar ben hynny, mae pob nod yn nodi a fydd y cymeriad olaf gair neu beidio.

601
00:52:38,110 --> 00:52:43,170
>> Gadewch i ni fynd i mewn i enghraifft o trie.

602
00:52:50,500 --> 00:52:58,340
Cyntaf i mi le ar gyfer 27 o nodau yn y casgliad.

603
00:52:58,340 --> 00:53:03,200
Os byddaf yn cael y gair BAR -

604
00:53:13,310 --> 00:53:15,370
Os byddaf yn cael y BAR geiriau a wyf i am osod mewn,

605
00:53:15,370 --> 00:53:22,700
y llythyr cyntaf yn B, felly os yw fy trie yn wag,

606
00:53:22,700 --> 00:53:29,910
B yw'r ail lythyr y wyddor, felly dwi'n mynd i ddewis i roi hyn yma yn y mynegai hwn.

607
00:53:29,910 --> 00:53:33,450
Rydw i'n mynd i gael B yma.

608
00:53:33,450 --> 00:53:42,400
B yn mynd i fod yn nod sy'n cyfeirio at un arall amrywiaeth o holl gymeriadau posibl

609
00:53:42,400 --> 00:53:45,870
a all ddilyn ar ôl y llythyr B.

610
00:53:45,870 --> 00:53:57,610
Yn yr achos hwn, rwy'n delio â'r BAR gair, fel y bydd yn mynd yma.

611
00:54:02,000 --> 00:54:08,990
Ar ôl A, Mae'r llythyr gennyf R, felly, yna pwyntiau bryd i'r cyfuniad eich hun,

612
00:54:08,990 --> 00:54:15,120
ac yna bydd R fod yma.

613
00:54:15,120 --> 00:54:22,470
BAR yn air gyflawn, felly, yna yr wyf i'n mynd i gael R pwynt i'r llall nod

614
00:54:22,470 --> 00:54:33,990
sy'n dweud bod y gair hwnnw yn ddilys.

615
00:54:36,010 --> 00:54:40,970
Bod nod hefyd yn mynd i gael amrywiaeth o nodau,

616
00:54:40,970 --> 00:54:45,260
ond gallai'r rhai sydd yn null.

617
00:54:45,260 --> 00:54:49,080
Ond yn y bôn, gall barhau fel hynny.

618
00:54:49,080 --> 00:54:54,250
Bydd hyn yn dod yn ychydig yn fwy eglur pan fyddwn yn mynd at enghraifft wahanol,

619
00:54:54,250 --> 00:54:56,780
felly dim ond yn amyneddgar gyda mi yno.

620
00:54:56,780 --> 00:55:02,050
Nawr mae gennym BAR tu mewn ein geiriadur.

621
00:55:02,050 --> 00:55:05,980
Nawr yn dweud ein bod yn cael y gair Baz.

622
00:55:05,980 --> 00:55:12,630
Rydym yn dechrau gyda B, ac mae gennym eisoes B fel un o'r llythyrau a anfonwyd sydd yn ein geiriadur.

623
00:55:12,630 --> 00:55:15,170
Dyna dilyn gyda A. Mae gennym A eisoes.

624
00:55:15,170 --> 00:55:19,250
Ond yna yn lle hynny, rydym wedi Z canlynol.

625
00:55:19,250 --> 00:55:25,490
Felly, yna elfen yn ein amrywiaeth yn mynd i fod Z,

626
00:55:25,490 --> 00:55:30,810
ac felly, yna bod un yn mynd i dynnu i un arall ar ddiwedd dilys o'r gair.

627
00:55:30,810 --> 00:55:36,930
Felly, rydym yn gweld bod pan fyddwn yn parhau trwy B ac yna A,

628
00:55:36,930 --> 00:55:43,480
mae dau opsiwn gwahanol ar hyn o bryd yn ein geiriadur am eiriau sy'n dechrau gyda B ac A.

629
00:55:49,650 --> 00:55:57,460
Dweud roeddem yn awyddus i mewnosoder y gair Foobar.

630
00:55:57,460 --> 00:56:05,620
Yna byddem yn gwneud cofnod yn F.

631
00:56:05,620 --> 00:56:11,320
F yn nod sy'n cyfeirio at amrywiaeth gyfan.

632
00:56:11,320 --> 00:56:22,790
Byddem yn dod o hyd i O, ewch i O, O yna gysylltiadau â rhestr gyfan.

633
00:56:22,790 --> 00:56:35,340
Byddai gennym B ac yna parhau, byddem wedi A ac yna R.

634
00:56:35,340 --> 00:56:43,570
Felly, yna croesi Foobar yr holl ffordd i lawr nes Foobar yn air cywir.

635
00:56:43,570 --> 00:56:52,590
Ac felly, yna byddai hyn fod yn air dilys.

636
00:56:52,590 --> 00:57:00,170
Yn awr yn dweud ein gair nesaf yn y geiriadur mewn gwirionedd y FOO gair.

637
00:57:00,170 --> 00:57:03,530
Byddem yn dweud F. Yr hyn sy'n dilyn F?

638
00:57:03,530 --> 00:57:06,190
Fi 'n weithredol eisoes â lle ar gyfer O, felly dwi'n mynd i barhau.

639
00:57:06,190 --> 00:57:09,150
Nid oes angen i mi wneud un newydd. Parhau.

640
00:57:09,150 --> 00:57:15,500
FOO yn air dilys yn y geiriadur, felly, yna yr wyf i'n mynd i ddangos

641
00:57:15,500 --> 00:57:21,660
bod hynny'n ddilys.

642
00:57:21,660 --> 00:57:28,370
Os byddaf yn rhoi'r gorau i fy dilyniant yno, byddai hynny'n gywir.

643
00:57:28,370 --> 00:57:33,050
Ond os ydym yn parhau â'n cyfres o FOO i lawr i B

644
00:57:33,050 --> 00:57:39,750
a dim ond wedi FOOB, nid FOOB yn air, ac nad yw wedi nodi fel un dilys.

645
00:57:47,370 --> 00:57:57,600
Mewn trie, rydych yn cael pob nod nodi a yw'n gair dilys neu beidio,

646
00:57:57,600 --> 00:58:05,840
ac yna bob nod hefyd amrywiaeth o 27 o arwyddion nod

647
00:58:05,840 --> 00:58:09,520
wedyn pwynt i nodau eu hunain.

648
00:58:09,520 --> 00:58:12,940
>> Dyma ffordd o sut efallai y byddwch am i ddiffinio'r hyn.

649
00:58:12,940 --> 00:58:17,260
Fodd bynnag, yn union fel yn yr enghraifft tabl hash, lle cawsom pen * nod

650
00:58:17,260 --> 00:58:21,320
i nodi dechrau ein rhestr cysylltiedig, rydym hefyd yn mynd i eisiau

651
00:58:21,320 --> 00:58:29,150
rhyw ffordd o wybod lle mae dechrau ein trie yw.

652
00:58:29,150 --> 00:58:34,110
Mae rhai pobl yn galw yn ceisio coed, a dyna lle gwraidd yn dod.

653
00:58:34,110 --> 00:58:36,910
Felly, rydym am wraidd ein coeden i wneud yn siŵr ein bod yn aros yn seilio

654
00:58:36,910 --> 00:58:39,570
i ble bynnag mae ein trie yn.

655
00:58:42,910 --> 00:58:46,300
Rydym eisoes yn fath o fynd dros

656
00:58:46,300 --> 00:58:50,240
y ffordd y gallech chi feddwl am lwytho pob gair yn y geiriadur.

657
00:58:50,240 --> 00:58:54,540
Yn y bôn, ar gyfer pob gair rydych yn mynd i eisiau i ailadrodd drwy eich trie

658
00:58:54,540 --> 00:58:59,590
a gwybod bod pob elfen yn y plant - byddem ni'n ei alw plant yn yr achos hwn -

659
00:58:59,590 --> 00:59:04,290
yn cyfateb i lythyr wahanol, rydych yn mynd i eisiau i wirio y rhai gwerthoedd

660
00:59:04,290 --> 00:59:08,320
ar y mynegai penodol sy'n cyfateb i'r llythyren.

661
00:59:08,320 --> 00:59:11,260
Felly meddwl yr holl ffordd yn ôl i Cesar a Vigenere,

662
00:59:11,260 --> 00:59:16,070
gan wybod bod pob llythyr gallwch fath o fap yn ôl i mynegai yn nhrefn yr wyddor,

663
00:59:16,070 --> 00:59:20,690
bendant A drwy'r Z yn mynd i fod yn eithaf hawdd i fapio i lythyr yr wyddor,

664
00:59:20,690 --> 00:59:25,200
ond yn anffodus, collnod hefyd yn gymeriad dderbyniol mewn geiriau.

665
00:59:25,200 --> 00:59:31,650
Dydw i ddim hyd yn oed yn siŵr beth yw gwerth ASCII yw,

666
00:59:31,650 --> 00:59:39,250
felly ar gyfer, os ydych am ddod o hyd i mynegai i benderfynu a ydych am iddo fod naill ai yr un cyntaf

667
00:59:39,250 --> 00:59:44,550
neu yr un diwethaf, bydd rhaid i chi wneud siec godio caled ar gyfer y

668
00:59:44,550 --> 00:59:48,930
a rhoi at ei bod yn fynegai 26, er enghraifft.

669
00:59:48,930 --> 00:59:55,300
Felly, yna rydych yn gwirio gwerth at blant [i]

670
00:59:55,300 --> 00:59:58,400
lle mae [i] yn cyfateb i beth bynnag lythyr rydych chi wedi'i gyrraedd.

671
00:59:58,400 --> 01:00:04,110
Os yw hynny'n NULL, mae hynny'n golygu nad oes ar hyn o bryd unrhyw lythyrau posibl

672
01:00:04,110 --> 01:00:08,150
yn deillio o hynny dilyniant blaenorol, felly rydych yn mynd i eisiau i malloc

673
01:00:08,150 --> 01:00:13,150
ac yn gwneud nod newydd a chael bod plant pwynt [i] iddo

674
01:00:13,150 --> 01:00:17,890
fel eich bod yn creu - pan fyddwn yn mewnosod lythyr i mewn i'r petryal -

675
01:00:17,890 --> 01:00:23,680
sicrhau bod plant nad ydynt yn null a phwynt i mewn i'r nod newydd.

676
01:00:23,680 --> 01:00:28,340
Ond os nad yw hynny'n NULL, fel yn ein hachos ni o FOO

677
01:00:28,340 --> 01:00:34,570
pan fyddwn eisoes wedi cael Foobar, rydym yn parhau,

678
01:00:34,570 --> 01:00:44,010
ac nid ydym yn byth yn gwneud nod newydd ond yn hytrach dim ond gosod i gwir is_word

679
01:00:44,010 --> 01:00:47,790
ar ddiwedd y gair.

680
01:00:50,060 --> 01:00:55,340
>> Felly, yna fel o'r blaen, oherwydd dyma eich bod yn delio gyda phob llythyren ar y tro,

681
01:00:55,340 --> 01:01:01,470
mae'n mynd i fod yn haws i chi ar gyfer maint, yn hytrach na gorfod gyfrifo

682
01:01:01,470 --> 01:01:06,910
ac ewch drwy'r goeden gyfan ac yn cyfrifo faint o blant sy'n rhaid i mi

683
01:01:06,910 --> 01:01:10,850
ac yna fforchio, gan gofio faint sydd ar yr ochr chwith ac ar yr ochr dde

684
01:01:10,850 --> 01:01:12,850
a phethau fel 'na, mae'n mynd i fod yn llawer haws i chi

685
01:01:12,850 --> 01:01:16,220
os ydych yn unig yn cadw golwg ar faint o eiriau rydych yn ychwanegu

686
01:01:16,220 --> 01:01:18,080
pan fyddwch yn delio â llwyth.

687
01:01:18,080 --> 01:01:22,630
Ac felly, yna gall maint ffordd dim ond dychwelyd newidyn byd-eang o faint.

688
01:01:25,320 --> 01:01:28,530
>> Nawr rydym yn dod i wirio.

689
01:01:28,530 --> 01:01:33,920
Un safonau fel o'r blaen, lle rydym eisiau i ganiatáu ar gyfer ansensitifrwydd achos.

690
01:01:33,920 --> 01:01:40,400
Yn ogystal, rydym yn tybio bod y tannau yn gymeriadau yn unig yr wyddor neu y collnodau

691
01:01:40,400 --> 01:01:44,000
oherwydd bod plant yn amrywiaeth o 27 o hyd,

692
01:01:44,000 --> 01:01:48,480
felly yr holl lythrennau'r wyddor yn ogystal â'r collnod.

693
01:01:48,480 --> 01:01:53,800
Am weld pa youll 'angen at gwna ydy youll' angen at ddechrau yn y gwraidd

694
01:01:53,800 --> 01:01:58,440
oherwydd bydd y gwraidd bwyntio at amrywiaeth sy'n cynnwys

695
01:01:58,440 --> 01:02:01,630
holl lythyrau posibl gan ddechrau o air.

696
01:02:01,630 --> 01:02:03,680
Rydych chi'n mynd i ddechrau yno,

697
01:02:03,680 --> 01:02:11,590
ac yna rydych chi'n mynd i wirio a yw hyn NULL werth neu beidio,

698
01:02:11,590 --> 01:02:16,490
oherwydd os bydd y gwerth yn NULL, sy'n golygu nad yw'r geiriadur oes unrhyw werthoedd

699
01:02:16,490 --> 01:02:21,480
sy'n cynnwys y llythyr hwnnw yn y drefn benodol.

700
01:02:21,480 --> 01:02:24,970
Os yw'n NULL, yna mae hynny'n golygu bod y gair yn cael ei gamsillafu ar unwaith.

701
01:02:24,970 --> 01:02:27,110
Ond os nad yw'n NULL, yna gallwch barhau,

702
01:02:27,110 --> 01:02:34,090
dweud bod llythyren gyntaf yn llythyren gyntaf posibl mewn gair,

703
01:02:34,090 --> 01:02:40,630
felly nawr rwyf am i wirio a yw'r ail lythyr, bod dilyniant, o fewn fy ngeiriadur.

704
01:02:40,630 --> 01:02:46,540
Felly, rydych chi'n mynd i fynd at y mynegai plant y nod 1

705
01:02:46,540 --> 01:02:50,720
a gwirio a yw'r ail lythyr yn bodoli.

706
01:02:50,720 --> 01:02:57,440
Yna byddwch yn ailadrodd y broses honno i wirio a yw'r dilyniant yn ddilys neu beidio

707
01:02:57,440 --> 01:02:59,060
o fewn eich trie.

708
01:02:59,060 --> 01:03:06,430
Pryd bynnag y plant nod ar y pwyntiau mynegai i NULL,

709
01:03:06,430 --> 01:03:10,710
eich bod yn gwybod nad yw'r dilyniant yn bodoli,

710
01:03:10,710 --> 01:03:16,230
ond yna os byddwch yn cyrraedd diwedd y gair yr ydych wedi mewnbynnu,

711
01:03:16,230 --> 01:03:20,070
yna rydych am wirio nawr fy mod wedi cwblhau dilyniant hwn

712
01:03:20,070 --> 01:03:27,610
a dod o hyd o fewn fy trie, yw bod gair ddilys ai peidio?

713
01:03:27,610 --> 01:03:32,480
Ac felly, os ydych am wirio hynny, a dyna pryd os ydych wedi gweld bod dilyniant,

714
01:03:32,480 --> 01:03:35,120
yna rydych am wirio a yw'r gair yn ddilys neu beidio

715
01:03:35,120 --> 01:03:40,290
oherwydd cofio yn ôl yn yr achos blaenorol y tynnais lle cawsom FOOB,

716
01:03:40,290 --> 01:03:48,410
a oedd yn ddilyniant dilys a welsom ond nad oedd yn air dilys ei hun.

717
01:03:50,570 --> 01:03:59,000
>> Yn yr un modd, ar gyfer dadlwytho yn y ceisiau ydych am i ddadlwytho pob un o'r nodau yn eich trie.

718
01:03:59,000 --> 01:04:04,790
Mae'n ddrwg gennym. Yn debyg i'r tablau hash lle yn dadlwytho rydym yn rhyddhau yr holl nodau,

719
01:04:04,790 --> 01:04:09,740
yn y cais ydym am hefyd yn rhyddhau pob un o'r nodau.

720
01:04:09,740 --> 01:04:15,000
Bydd Dadlwytho yn gweithio mewn gwirionedd hawsaf o'r gwaelod i'r brig

721
01:04:15,000 --> 01:04:19,290
oherwydd bod y rhain yn rhestrau cysylltiedig yn y bôn.

722
01:04:19,290 --> 01:04:22,540
Felly, rydym am wneud yn siŵr ein bod yn dal gafael ar yr holl werthoedd

723
01:04:22,540 --> 01:04:25,700
ac yn rhydd pob un ohonynt yn benodol.

724
01:04:25,700 --> 01:04:28,840
Beth ydych chi'n mynd i eisiau i'w wneud os ydych chi'n gweithio gyda trie

725
01:04:28,840 --> 01:04:35,640
yn teithio i'r gwaelod a rhad ac am ddim y nod isaf posibl cyntaf

726
01:04:35,640 --> 01:04:39,190
ac yna mynd i fyny i bob un o'r plant hynny ac yna rhad ac am ddim pob un o'r rheiny,

727
01:04:39,190 --> 01:04:43,050
mynd i fyny ac yna rhad ac am ddim, ac ati

728
01:04:43,050 --> 01:04:48,790
Math o fel delio â haen waelod y cyntaf trie

729
01:04:48,790 --> 01:04:51,940
ac yna mynd i fyny ben unwaith y byddwch wedi rhyddhau popeth.

730
01:04:51,940 --> 01:04:56,720
Mae hon yn enghraifft dda o ble y gallai swyddogaeth recursive dod yn ddefnyddiol.

731
01:04:56,720 --> 01:05:03,830
Unwaith y byddwch wedi rhyddhau yr haen waelod eich trie,

732
01:05:03,830 --> 01:05:08,000
yna byddwch yn ffonio dadlwytho ar y gweddill ohono,

733
01:05:08,000 --> 01:05:13,620
gwneud yn siŵr eich bod yn rhyddhau pob mini -

734
01:05:13,620 --> 01:05:16,410
Gallwch fath o yn gweld hynny fel cais mini.

735
01:05:23,300 --> 01:05:28,990
Felly, rydych yn cael eich gwraidd fan hyn.

736
01:05:30,840 --> 01:05:35,230
Im 'jyst yn symleiddio felly nid oes gennyf i dynnu 26 ohonynt.

737
01:05:37,250 --> 01:05:43,770
Felly, mae gennych y rhain, ac yna y rhain yn cynrychioli dilyniant o eiriau

738
01:05:43,770 --> 01:05:54,620
lle mae pob un o'r cylchoedd bach yn llythrennau y gellir eu dilyniannau dilys o lythyrau.

739
01:06:03,040 --> 01:06:07,160
Gadewch i ni barhau dim ond ychydig yn fwy.

740
01:06:15,110 --> 01:06:25,750
Beth ydych chi'n mynd i eisiau ei wneud yw rhad ac am ddim y gwaelod yma ac yna rhad ac am ddim yr un yma

741
01:06:25,750 --> 01:06:31,640
ac yna ddim yr un ar y gwaelod cyn i chi ryddhau'r un gorau hyd yma

742
01:06:31,640 --> 01:06:38,180
oherwydd os ydych yn rhywbeth rhad ac am ddim yn yr ail lefel yma,

743
01:06:38,180 --> 01:06:47,230
yna rydych fyddai mewn gwirionedd yn colli gwerth hwn yma.

744
01:06:47,230 --> 01:06:54,780
Dyna pam ei bod yn bwysig yn dadlwytho i trie i wneud yn siŵr eich bod yn rhyddhau'r ben ôl yn gyntaf.

745
01:06:54,780 --> 01:06:59,480
Beth efallai y byddwch am ei wneud yw dweud ar gyfer pob nod

746
01:06:59,480 --> 01:07:06,430
Rwyf am i ddadlwytho pob un o'r plant.

747
01:07:16,060 --> 01:07:22,140
>> Nawr ein bod wedi mynd dros dadlwytho ar gyfer y dull tabl hash yn ogystal â'r dull trie,

748
01:07:22,140 --> 01:07:27,020
rydym yn mynd i eisiau i edrych ar Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind ydych yn rhedeg gyda gorchmynion canlynol.

750
01:07:29,640 --> 01:07:32,700
Mae gennych valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Rydych yn gwirio ar gyfer yr holl ollyngiadau pan fyddwch yn rhedeg sillafu rhoddir y testun penodol

752
01:07:40,960 --> 01:07:46,980
oherwydd sillafu angen eu cymryd mewn ffeil testun.

753
01:07:46,980 --> 01:07:52,330
Felly, bydd Valgrind yn rhedeg eich rhaglen, yn dweud wrthych faint o bytes ydych wedi ei glustnodi,

754
01:07:52,330 --> 01:07:57,150
faint o bytes rhyddhau chi, a bydd yn dweud wrthych a ydych yn rhyddhau dim ond digon

755
01:07:57,150 --> 01:07:58,930
ynteu a ydych yn gwneud ddigon rhydd,

756
01:07:58,930 --> 01:08:02,850
neu weithiau gallwch hyd yn oed dros-rhad ac am ddim, fel rhad ac am ddim yn nod sydd eisoes wedi rhyddhau

757
01:08:02,850 --> 01:08:05,140
ac felly bydd yn dychwelyd i chi gwallau.

758
01:08:05,140 --> 01:08:11,600
Os ydych yn defnyddio Valgrind, bydd yn rhoi i chi rai negeseuon

759
01:08:11,600 --> 01:08:15,970
nodi a ydych chi wedi rhyddhau naill ai yn llai na digon, dim ond digon,

760
01:08:15,970 --> 01:08:19,609
neu fwy na ddigon o weithiau.

761
01:08:24,370 --> 01:08:30,410
>> Mae rhan o'r pset, mae'n ddewisol i herio y Bwrdd Big.

762
01:08:30,410 --> 01:08:35,790
Ond pan fyddwn ni'n delio â'r strwythurau data

763
01:08:35,790 --> 01:08:40,689
mae'n fath o hwyl i weld pa mor gyflym a pha mor effeithlon a allai eich strwythurau data fod.

764
01:08:40,689 --> 01:08:44,490
A yw eich canlyniad swyddogaeth hash mewn llawer o wrthdrawiadau?

765
01:08:44,490 --> 01:08:46,300
Neu a yw eich data maint mawr iawn?

766
01:08:46,300 --> 01:08:49,420
A yw'n cymryd llawer o amser i deithio ar draws?

767
01:08:49,420 --> 01:08:54,800
Yn y log o sillafu, mae'n allbynnau faint o amser rydych yn ei ddefnyddio i lwytho,

768
01:08:54,800 --> 01:08:57,700
i wirio, i gynnal maint, ac i ddadlwytho,

769
01:08:57,700 --> 01:09:00,720
ac felly rhain yn cael eu postio yn y Bwrdd Fawr,

770
01:09:00,720 --> 01:09:03,600
lle gallwch chi gystadlu yn erbyn eich ffrindiau yn y dosbarth

771
01:09:03,600 --> 01:09:11,350
a rhai aelodau o'r staff i weld pwy sydd â'r cyflymaf gwirydd sillafu.

772
01:09:11,350 --> 01:09:14,760
Un peth y byddwn i'n hoffi i'w nodi am y tablau hash

773
01:09:14,760 --> 01:09:20,470
yw bod rhai swyddogaethau eithaf syml hash y gallem feddwl.

774
01:09:20,470 --> 01:09:27,240
Er enghraifft, mae gennych 26 bwcedi, ac felly bob bwced

775
01:09:27,240 --> 01:09:30,200
cyfateb i'r llythyren gyntaf mewn gair,

776
01:09:30,200 --> 01:09:35,229
ond mae hynny'n mynd i arwain mewn tabl 'n bert anghytbwys hash

777
01:09:35,229 --> 01:09:40,979
oherwydd mae geiriau llawer llai sy'n dechrau â X na dechrau gyda M, er enghraifft.

778
01:09:40,979 --> 01:09:47,890
Un ffordd i fynd ati i sillafu yw os ydych am gael yr holl swyddogaethau eraill i lawr,

779
01:09:47,890 --> 01:09:53,240
yna dim ond yn defnyddio swyddogaeth hash syml i fod yn gallu cael eich cod rhedeg

780
01:09:53,240 --> 01:09:58,650
ac yna mynd yn ôl a newid maint eich tabl hash a'r diffiniad.

781
01:09:58,650 --> 01:10:03,430
Mae yna lawer o adnoddau ar y Rhyngrwyd ar gyfer swyddogaethau hash,

782
01:10:03,430 --> 01:10:08,250
ac felly ar gyfer y pset caniateir i chi ymchwilio i swyddogaethau hash ar y Rhyngrwyd

783
01:10:08,250 --> 01:10:15,560
ar gyfer rhai awgrymiadau ac ysbrydoliaeth cyn belled ag y byddwch yn gwneud yn siwr i ddyfynnu ble y cawsoch rhag.

784
01:10:15,560 --> 01:10:22,060
Mae croeso i chi edrych a dehongli rhywfaint o swyddogaeth hash eich bod yn dod o hyd ar y Rhyngrwyd.

785
01:10:22,060 --> 01:10:27,460
Yn ôl i hynny, efallai y byddwch yn gallu gweld os bydd rhywun yn defnyddio trie

786
01:10:27,460 --> 01:10:31,700
a yw eu rhoi ar waith yn gyflymach nag eich bwrdd hash neu beidio.

787
01:10:31,700 --> 01:10:35,290
Gallwch gyflwyno i Fwrdd Big sawl gwaith.

788
01:10:35,290 --> 01:10:37,660
Bydd yn cofnodi eich cofnod mwyaf diweddar.

789
01:10:37,660 --> 01:10:44,300
Felly, efallai byddwch yn newid eich swyddogaeth hash ac yna sylweddoli ei fod mewn gwirionedd yn llawer cyflymach

790
01:10:44,300 --> 01:10:46,780
neu lawer arafach nag o'r blaen.

791
01:10:46,780 --> 01:10:50,960
Mae hynny'n dipyn o ffordd hwyliog.

792
01:10:50,960 --> 01:10:57,190
Mae bob amser yn 1 neu 2 aelod staff sy'n ceisio gwneud y geiriadur arafaf posibl,

793
01:10:57,190 --> 01:11:00,210
fel bod bob amser yn hwyl i edrych ar.

794
01:11:00,210 --> 01:11:07,630
>> Mae'r defnydd ar gyfer y pset yw ydych yn rhedeg sillafu gyda geiriadur dewisol

795
01:11:07,630 --> 01:11:12,840
ac yna ffeil destun gorfodol.

796
01:11:12,840 --> 01:11:18,380
Erbyn ddiofyn pan fyddwch yn rhedeg sillafu gyda dim ond ffeil destun ac nid ydynt yn pennu geiriadur,

797
01:11:18,380 --> 01:11:24,410
mae'n mynd i ddefnyddio'r geiriadur, ffeil testun yr un mawr

798
01:11:24,410 --> 01:11:27,920
yn y ffolder cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Bod un dros 100,000 o eiriau.

800
01:11:32,760 --> 01:11:37,950
Mae ganddynt hefyd geiriadur bach sydd â geiriau gryn dipyn yn llai

801
01:11:37,950 --> 01:11:40,730
bod CS50 wedi gwneud i chi.

802
01:11:40,730 --> 01:11:44,050
Fodd bynnag, gallwch yn hawdd iawn yn unig yn gwneud eich geiriadur eich hun

803
01:11:44,050 --> 01:11:47,150
os ydych am fod yn gweithio mewn enghreifftiau bach -

804
01:11:47,150 --> 01:11:51,140
er enghraifft, os ydych chi am ddefnyddio gdb a ydych yn gwybod y gwerthoedd penodol

805
01:11:51,140 --> 01:11:53,560
eich bod am i'ch bwrdd hash i fapio allan i.

806
01:11:53,560 --> 01:12:00,430
Felly, dim ond y gallwch chi wneud eich ffeil testun eich hun yn unig gyda BAR, Baz, FOO, a Foobar,

807
01:12:00,430 --> 01:12:04,860
gwneud hynny mewn ffeil testun, gwahanu'r rheiny pob un ag 1 llinell,

808
01:12:04,860 --> 01:12:12,670
ac yna gwneud eich ffeil destun hun sy'n llythrennol yn unig yn cynnwys efallai 1 neu 2 o eiriau

809
01:12:12,670 --> 01:12:15,950
fel eich bod yn gwybod yn union beth y dylai'r allbwn.

810
01:12:15,950 --> 01:12:21,870
Mae rhai o'r ffeiliau sampl testun y bydd y Bwrdd Big pan fyddwch yn rhedeg her gwirio

811
01:12:21,870 --> 01:12:25,580
yn Rhyfel a Heddwch a nofel Austen Jane neu rywbeth fel 'na.

812
01:12:25,580 --> 01:12:30,450
Felly, pan fyddwch yn dechrau allan, mae'n llawer haws i wneud eich ffeiliau testun eich hun

813
01:12:30,450 --> 01:12:34,160
sy'n cynnwys dim ond ychydig o eiriau neu efallai 10

814
01:12:34,160 --> 01:12:38,280
fel y gallwch ragweld beth ddylai'r canlyniad fod

815
01:12:38,280 --> 01:12:42,880
ac yna ei wirio yn erbyn hynny, felly mae mwy o enghraifft a reolir.

816
01:12:42,880 --> 01:12:45,820
Ac felly ers i ni yn delio â rhagweld a thynnu pethau o gwmpas,

817
01:12:45,820 --> 01:12:48,690
eto yr wyf yn awyddus i annog chi i ddefnyddio pin a phapur

818
01:12:48,690 --> 01:12:50,700
oherwydd ei fod yn wir yn mynd i helpu chi gyda hyn -

819
01:12:50,700 --> 01:12:55,620
tynnu y saethau, sut y tabl hash neu sut mae eich trie yn edrych,

820
01:12:55,620 --> 01:12:57,980
pan fyddwch yn rhyddhau rhywbeth lle mae'r saethau yn mynd,

821
01:12:57,980 --> 01:13:01,730
a ydych yn cynnal ar i ddigon, a ydych yn gweld unrhyw gysylltiadau ddiflannu

822
01:13:01,730 --> 01:13:05,750
a disgyn i'r dibyn o gof a ddatgelwyd.

823
01:13:05,750 --> 01:13:11,070
Felly, os gwelwch yn dda, os gwelwch yn dda ceisio tynnu pethau allan hyd yn oed cyn i chi fynd i ysgrifennu cod i lawr.

824
01:13:11,070 --> 01:13:14,520
Tynnwch bethau fel eich bod yn deall sut mae pethau'n mynd i weithio

825
01:13:14,520 --> 01:13:22,750
oherwydd wedyn wyf yn gwarantu y byddwch yn rhedeg i mewn i Muddles pwyntydd yn llai yno.

826
01:13:24,270 --> 01:13:25,910
>> Mae pob hawl.

827
01:13:25,910 --> 01:13:28,780
Rwyf am ddymuno i chi y gorau o lwc gyda'r pset.

828
01:13:28,780 --> 01:13:31,980
Mae'n debyg yr un anoddaf.

829
01:13:31,980 --> 01:13:40,360
Felly ceisiwch i ddechrau yn gynnar, tynnu pethau allan, tynnu pethau allan, a phob lwc.

830
01:13:40,360 --> 01:13:42,980
Roedd hyn yn Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]