1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Szia.

3
00:00:13,050 --> 00:00:16,210
Én Rob, és hagyja, hogy a hash
e megoldás.

4
00:00:16,210 --> 00:00:20,070
Tehát itt fogunk végrehajtani
általános hash tábla.

5
00:00:20,070 --> 00:00:24,090
Látjuk, hogy a struktúra csomópontja a hash
táblázat fog kinézni, mint ez.

6
00:00:24,090 --> 00:00:28,710
Ezért van, hogy a char szót
tömb mérete hossza plusz 1.

7
00:00:28,710 --> 00:00:32,259
Ne felejtsd el a 1, mivel a maximum
szó a szótárban 45

8
00:00:32,259 --> 00:00:35,110
karaktereket, majd megyünk
szükség van egy extra karakter a

9
00:00:35,110 --> 00:00:37,070
backslash 0-ra.

10
00:00:37,070 --> 00:00:40,870
>> És akkor a hash tábla minden
vödör fog tárolni a

11
00:00:40,870 --> 00:00:42,320
láncolt lista csomópontok.

12
00:00:42,320 --> 00:00:44,420
Nem csináljuk lineáris szondázás itt.

13
00:00:44,420 --> 00:00:48,430
Így annak érdekében, hogy link a következő
elem a vödör, szükségünk van egy

14
00:00:48,430 --> 00:00:51,110
struct node * mellett.

15
00:00:51,110 --> 00:00:53,090
Szóval, ez az, amit a csomópont néz ki.

16
00:00:53,090 --> 00:00:56,180
Nos, itt van a nyilatkozat
a mi hash tábla.

17
00:00:56,180 --> 00:01:01,910
Úgy megy, hogy 16.384 vödör, de
ez a szám nem igazán számít.

18
00:01:01,910 --> 00:01:05,450
És végül, mi lesz, hogy a
globális változó hashtable_size, amely

19
00:01:05,450 --> 00:01:08,640
fog elindul, mint 0, és ez
majd nyomon követni, hogy hány szót

20
00:01:08,640 --> 00:01:10,080
volt a szótár.

21
00:01:10,080 --> 00:01:10,760
Rendben van.

22
00:01:10,760 --> 00:01:13,190
>> Szóval vessünk egy pillantást a terhelés.

23
00:01:13,190 --> 00:01:16,390
Tehát észre, hogy terhelés,
visszatér a bool.

24
00:01:16,390 --> 00:01:20,530
Visszatér igaz, ha sikeresen
betöltött és hamis egyébként.

25
00:01:20,530 --> 00:01:23,990
És ez tart a const char * csillag
szótár, amely a szótárban

26
00:01:23,990 --> 00:01:25,280
hogy meg akarjuk nyitni.

27
00:01:25,280 --> 00:01:27,170
Tehát ez az első dolog,
fogunk csinálni.

28
00:01:27,170 --> 00:01:30,420
Fogunk fopen a szótárban
olvasás, és mi lesz, hogy

29
00:01:30,420 --> 00:01:34,700
, hogy megbizonyosodjon arról, hogy ez sikerült, így ha
visszatért NULL, akkor nem

30
00:01:34,700 --> 00:01:37,440
sikeresen nyitott a szótárban
, és vissza kell térnünk hamis.

31
00:01:37,440 --> 00:01:41,580
>> De feltételezve, hogy nem sikerült
nyitva van, akkor szeretnénk olvasni a

32
00:01:41,580 --> 00:01:42,400
szótárban.

33
00:01:42,400 --> 00:01:46,210
Maradjatok hurok amíg nem találunk valami
ok, hogy kitörjön a jelen

34
00:01:46,210 --> 00:01:47,570
hurok, amely majd meglátjuk.

35
00:01:47,570 --> 00:01:51,780
Maradjatok hurok, és most megyünk
malloc egy csomópont.

36
00:01:51,780 --> 00:01:56,800
És persze, meg kell, hogy hiba ellenőrzése
újra így ha mallocing nem sikerült

37
00:01:56,800 --> 00:02:00,660
és azt akarjuk, hogy kirak olyan csomópont, hogy mi
történt malloc előtt, zárja be a

38
00:02:00,660 --> 00:02:02,590
szótárt, és vissza hamis.

39
00:02:02,590 --> 00:02:07,440
>> De figyelmen kívül hagyva, hogy feltételezve, hogy
sikerült, akkor szeretnénk használni fscanf

40
00:02:07,440 --> 00:02:12,400
olvasni egy szót a
szótárt a mi csomópontot.

41
00:02:12,400 --> 00:02:17,310
Úgy emlékszem, hogy a belépő> szó a char
szó buffer méret hossza plusz

42
00:02:17,310 --> 00:02:20,300
az egyik, hogy fogunk
tárolja a szó be

43
00:02:20,300 --> 00:02:25,280
Tehát fscanf fog visszatérni 1. amíg
mint volt sikeresen olvasni

44
00:02:25,280 --> 00:02:26,750
szó a fájlból.

45
00:02:26,750 --> 00:02:31,030
>> Ha bármelyik hiba történik, vagy elérjük
a végén a fájl, akkor nem

46
00:02:31,030 --> 00:02:34,950
1 visszaút amely esetben, ha ez nem
vissza 1, mi végre fog törni

47
00:02:34,950 --> 00:02:37,280
ebből a while ciklus.

48
00:02:37,280 --> 00:02:42,770
Tehát azt látjuk, hogy ha már sikeresen
olvasni egy szót

49
00:02:42,770 --> 00:02:48,270
entry-> szó, akkor megyünk hash
ez a szó a mi hash függvényt.

50
00:02:48,270 --> 00:02:49,580
Vessünk egy pillantást
a hash függvényt.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> Szóval nem igazán kell
megérteni ezt.

53
00:02:55,610 --> 00:02:59,460
És valóban, csak húzta ezt
hash függvény az interneten.

54
00:02:59,460 --> 00:03:04,010
Az egyetlen dolog, amit meg kell, hogy ismerje el,
hogy ez eltart egy const char * szó,

55
00:03:04,010 --> 00:03:08,960
így tart a sztringet bemeneti és
vissza az unsigned int a kibocsátás.

56
00:03:08,960 --> 00:03:12,360
Szóval ez az egész egy hash funkció, ez
vesz egy bemeneti, ez ad ön egy

57
00:03:12,360 --> 00:03:14,490
index a hash tábla.

58
00:03:14,490 --> 00:03:18,530
Figyeljük meg, hogy mi modding által NUM_BUCKETS
így a hash visszaadott érték

59
00:03:18,530 --> 00:03:21,730
valójában egy index a hash tábla
és nem indexeli túl

60
00:03:21,730 --> 00:03:24,320
határait a tömb.

61
00:03:24,320 --> 00:03:27,855
>> Tehát mivel hash függvényt, megyünk
a hash a szó, hogy olvasunk

62
00:03:27,855 --> 00:03:31,700
a szótárt, és aztán megyünk
használni, amely beszúrni a

63
00:03:31,700 --> 00:03:33,750
belépés a hash tábla.

64
00:03:33,750 --> 00:03:38,830
Most, hash tábla hash a jelenlegi
láncolt lista a hash tábla, és a

65
00:03:38,830 --> 00:03:41,410
ez nagyon valószínű, hogy csak NULL.

66
00:03:41,410 --> 00:03:45,640
Azt szeretné szúrni a belépést a
elején ez a láncolt lista, és így

67
00:03:45,640 --> 00:03:48,910
mi lesz, hogy a jelenlegi bejegyzés
pont, amit a hash tábla jelenleg

68
00:03:48,910 --> 00:03:54,030
pontokat, majd megyünk tárolni
a hash táblában a hash

69
00:03:54,030 --> 00:03:55,350
Az aktuális bejegyzés.

70
00:03:55,350 --> 00:03:59,320
>> Tehát ez a két vonal sikeresen be
belépési elején a

71
00:03:59,320 --> 00:04:02,270
láncolt lista az adott index
a hash táblában.

72
00:04:02,270 --> 00:04:04,900
Miután végeztünk, hogy mi tudjuk,
hogy talált egy másik szót a

73
00:04:04,900 --> 00:04:07,800
szótár és növedék újra.

74
00:04:07,800 --> 00:04:13,960
Így csinálom, hogy amíg fscanf
végül visszatér valami nem 1-es

75
00:04:13,960 --> 00:04:18,560
amely pont ne feledje, hogy meg kell
a belépés ingyenes, így itt, mi malloced egy

76
00:04:18,560 --> 00:04:21,329
belépés és megpróbáltuk olvasni valamit
a szótárban.

77
00:04:21,329 --> 00:04:24,110
És nem sikerült elolvasni
valamit a szótárban, amelyben

78
00:04:24,110 --> 00:04:27,440
esetben fel kell szabadítanunk a bejegyzést, hogy mi
soha nem tesz a hash tábla

79
00:04:27,440 --> 00:04:29,110
és végül a szünet.

80
00:04:29,110 --> 00:04:32,750
>> Amint kitörni, meg kell látni, nos,
tudtunk kitörni, mert

81
00:04:32,750 --> 00:04:35,840
Hiba olvasni a fájlt, vagy
tudtunk kitörni, mert elértük

82
00:04:35,840 --> 00:04:37,120
a végén a fájl?

83
00:04:37,120 --> 00:04:40,150
Ha volt egy hiba, akkor szeretnénk
return false mert terhelés nem

84
00:04:40,150 --> 00:04:43,260
sikerül, és a folyamat, azt akarjuk, hogy
kirak minden szót, amit olvas

85
00:04:43,260 --> 00:04:45,670
és zárja be a szótárban fájlt.

86
00:04:45,670 --> 00:04:48,740
Feltéve, hogy nem sikerül, akkor már csak
továbbra is szükség van, hogy lezárja a szótárban

87
00:04:48,740 --> 00:04:51,970
fájlt, és végül vissza igaz, mert
már sikeresen betöltötte a

88
00:04:51,970 --> 00:04:53,040
szótárban.

89
00:04:53,040 --> 00:04:54,420
És ez a terhelés.

90
00:04:54,420 --> 00:04:59,020
>> Tehát most ellenőrizni, mivel a terhelt hash tábla,
fog kinézni.

91
00:04:59,020 --> 00:05:02,690
Így ellenőrizni, visszatér a bool, amely
fog annak jelzésére, hogy a

92
00:05:02,690 --> 00:05:07,530
telt-in char * szó, hogy a
telt-karakterlánc a mi szótárban.

93
00:05:07,530 --> 00:05:10,530
Tehát, ha a szótárban, ha az
a mi hash tábla, akkor vissza fog térni

94
00:05:10,530 --> 00:05:13,380
igaz, és ha nem,
visszatérünk hamis.

95
00:05:13,380 --> 00:05:17,770
Mivel ez a telt, a szó, mi
fogja hash szó.

96
00:05:17,770 --> 00:05:22,020
>> Nos, egy fontos dolog, hogy ismerje el,
hogy a terhelés, tudtuk, hogy az összes

97
00:05:22,020 --> 00:05:25,820
a szavak lesznek kisbetűs,
de itt, nem vagyunk olyan biztos.

98
00:05:25,820 --> 00:05:29,510
Ha veszünk egy pillantást a hash függvény
a hash függvény valójában

99
00:05:29,510 --> 00:05:32,700
A lowercasing minden karakter
a szó.

100
00:05:32,700 --> 00:05:37,580
Tehát függetlenül attól, hogy a kapitalizációja
szó, a hash funkció fog

101
00:05:37,580 --> 00:05:42,270
vissza ugyanazt index bármilyen
kapitalizáció olyan volna

102
00:05:42,270 --> 00:05:45,280
visszatért egy teljesen kisbetűs
változata a szó.

103
00:05:45,280 --> 00:05:45,950
Rendben van.

104
00:05:45,950 --> 00:05:47,410
>> Szóval ez az index.

105
00:05:47,410 --> 00:05:49,790
Ez a hash tábla ezt a szót.

106
00:05:49,790 --> 00:05:52,940
Nos, ez a for ciklus megy
hogy több mint a láncolt lista

107
00:05:52,940 --> 00:05:55,000
hogy abban az index.

108
00:05:55,000 --> 00:05:59,630
Így észre vagyunk inicializálás bejegyzés
hogy pont, hogy az index.

109
00:05:59,630 --> 00:06:03,480
Megyünk tovább, amíg a bejegyzés nem
nem egyenlő NULL, és ne feledje, hogy

110
00:06:03,480 --> 00:06:08,350
frissítése a mutatót a láncolt lista
belépés egyenlő entry-> kov, így már

111
00:06:08,350 --> 00:06:13,840
a jelenlegi belépési pont a
következő elem a láncolt lista.

112
00:06:13,840 --> 00:06:14,400
Rendben van.

113
00:06:14,400 --> 00:06:19,150
>> Tehát minden bejegyzést a láncolt lista,
fogunk használni strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Nem strcmp mert még egyszer, mi
akar csinálni a dolgokat esetben érzéketlenül.

115
00:06:23,780 --> 00:06:28,830
Így használjuk strcasecmp összehasonlítani a szó
amit át ezt a funkciót

116
00:06:28,830 --> 00:06:31,860
ellen, a szó, hogy
ebben a bejegyzést.

117
00:06:31,860 --> 00:06:35,570
Ha visszatér 0, azt jelenti, hogy nem volt
a meccs, ebben az esetben szeretnénk

118
00:06:35,570 --> 00:06:36,630
vissza igaz.

119
00:06:36,630 --> 00:06:39,590
Sikeresen megtaláltuk a
szó a mi hash tábla.

120
00:06:39,590 --> 00:06:43,040
>> Ha nem egyezik, akkor vagyunk
fog loop újra, és nézd meg a

121
00:06:43,040 --> 00:06:43,990
következő bejegyzés.

122
00:06:43,990 --> 00:06:47,640
És mi is loop míg
vannak bejegyzések ebben a láncolt lista.

123
00:06:47,640 --> 00:06:50,160
Mi történik, ha szünet
ki ez a for ciklus?

124
00:06:50,160 --> 00:06:55,110
Ez azt jelenti, hogy nem találtunk olyan bejegyzést, amely
párosított ezt a szót, amely esetben

125
00:06:55,110 --> 00:07:00,220
visszatérünk a hamis, jelezve, hogy a
hash tábla nem tartalmazza ezt a szót.

126
00:07:00,220 --> 00:07:01,910
És ez a csekk.

127
00:07:01,910 --> 00:07:02,540
Rendben van.

128
00:07:02,540 --> 00:07:04,790
>> Szóval vessünk egy pillantást méretben.

129
00:07:04,790 --> 00:07:09,280
Most, méret lesz nagyon egyszerű
mivel emlékszem terhelés minden egyes szó

130
00:07:09,280 --> 00:07:12,880
találtunk is növekszik a globális
változó hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Tehát a méret funkció csak
majd vissza, hogy a globális

132
00:07:15,830 --> 00:07:18,150
változó, és ennyi.

133
00:07:18,150 --> 00:07:22,300
>> Most végre, meg kell, hogy kirak az
szótár Amint minden kész.

134
00:07:22,300 --> 00:07:25,340
Szóval, hogyan fogjuk csinálni?

135
00:07:25,340 --> 00:07:30,440
Itt, mi a ciklusok egész
vödör a hash tábla.

136
00:07:30,440 --> 00:07:33,240
Tehát vannak NUM_BUCKETS vödör.

137
00:07:33,240 --> 00:07:37,490
És minden egyes láncolt lista a mi hash
asztal, megyünk hurkot a

138
00:07:37,490 --> 00:07:41,070
teljes egészében a láncolt lista
felszabadítása minden elem.

139
00:07:41,070 --> 00:07:46,070
Nos, meg kell, hogy legyen óvatos, ezért itt
van egy átmeneti változó, ami

140
00:07:46,070 --> 00:07:49,740
tárolja a mutatót, hogy a következő
elem a láncolt lista.

141
00:07:49,740 --> 00:07:52,140
És akkor mi lesz ingyenes
Az aktuális elem.

142
00:07:52,140 --> 00:07:55,990
>> Meg kell bizonyosodni arról, hogy ezt mivel
Nem lehet csak kiszabadítani az aktuális elem

143
00:07:55,990 --> 00:07:59,260
, majd próbálja meg elérni a következő mutató
hiszen ha már kiszabadította azt a

144
00:07:59,260 --> 00:08:00,870
memória érvénytelenné válik.

145
00:08:00,870 --> 00:08:04,990
Tehát meg kell tartani körül egy mutatót
A következő elem, akkor mi is szabad a

146
00:08:04,990 --> 00:08:08,360
aktuális elem, és akkor frissíteni
a jelenlegi elem, hogy pont

147
00:08:08,360 --> 00:08:09,590
A következő elem.

148
00:08:09,590 --> 00:08:12,770
>> Majd loop, míg vannak olyan elemei
ebben a láncolt lista.

149
00:08:12,770 --> 00:08:16,450
Majd, hogy minden csatolt listák
A hash tábla, és ha kész is vagyunk

150
00:08:16,450 --> 00:08:20,180
azzal, hogy most már teljesen lemerülni
A hash tábla, és kész is vagyunk.

151
00:08:20,180 --> 00:08:24,050
Tehát lehetetlen eltávolítja valaha
return false, és amikor kész, akkor

152
00:08:24,050 --> 00:08:25,320
csak vissza igaz.

153
00:08:25,320 --> 00:08:27,563