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

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

3
00:00:13,050 --> 00:00:16,210
Sunt Rob, și hash Să
această soluție afară.

4
00:00:16,210 --> 00:00:20,070
Deci, aici am de gând să pună în aplicare
un tabel hash general.

5
00:00:20,070 --> 00:00:24,090
Vedem că nodul struct de hash noastre
masă este de gând să arate ca aceasta.

6
00:00:24,090 --> 00:00:28,710
Deci, o să aibă un cuvânt char
matrice de lungime dimensiune plus 1.

7
00:00:28,710 --> 00:00:32,259
Nu uita de 1 la maxim
cuvânt în dicționar este de 45

8
00:00:32,259 --> 00:00:35,110
caractere, iar apoi vom
au nevoie de un caracter suplimentar pentru

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

10
00:00:37,070 --> 00:00:40,870
>> Și apoi masa noastră hash în fiecare
găleată se va stoca un

11
00:00:40,870 --> 00:00:42,320
Lista legate de noduri.

12
00:00:42,320 --> 00:00:44,420
Noi nu facem liniar sondare aici.

13
00:00:44,420 --> 00:00:48,430
Și astfel, în scopul de a lega la alta
Element în găleată, avem nevoie de un

14
00:00:48,430 --> 00:00:51,110
struct nod * viitor.

15
00:00:51,110 --> 00:00:53,090
Deci, asta e ceea ce un nod arata ca.

16
00:00:53,090 --> 00:00:56,180
Acum, aici este declarația
de masa noastră hash.

17
00:00:56,180 --> 00:01:01,910
Se va avea 16.384 de găleți, dar
că numărul nu contează cu adevărat.

18
00:01:01,910 --> 00:01:05,450
Și, în sfârșit, vom avea
hashtable_size global variabilă, care

19
00:01:05,450 --> 00:01:08,640
este de gând să încep ca 0, și este
merge pentru a urmări cât de multe cuvinte

20
00:01:08,640 --> 00:01:10,080
au fost, în dicționarul nostru.

21
00:01:10,080 --> 00:01:10,760
Bine.

22
00:01:10,760 --> 00:01:13,190
>> Deci, haideți să aruncăm o privire la sarcină.

23
00:01:13,190 --> 00:01:16,390
Astfel observa că sarcina,
returnează un bool.

24
00:01:16,390 --> 00:01:20,530
Te vei întoarce true dacă a fost cu succes
încărcat și false în caz contrar.

25
00:01:20,530 --> 00:01:23,990
Și este nevoie de un const char * stele
dicționar, care este dicționarul

26
00:01:23,990 --> 00:01:25,280
pe care ne-o dorim pentru a deschide.

27
00:01:25,280 --> 00:01:27,170
Deci, asta e primul lucru
am de gând să faci.

28
00:01:27,170 --> 00:01:30,420
Vom fopen dicționarul de
lectură, și vom avea

29
00:01:30,420 --> 00:01:34,700
pentru a vă asigura că a reușit, deci, dacă
ea sa întors NULL, atunci nu am

30
00:01:34,700 --> 00:01:37,440
deschide cu succes în dicționar
și avem nevoie pentru a reveni false.

31
00:01:37,440 --> 00:01:41,580
>> Dar presupunând că a făcut-o cu succes
deschis, apoi ne-o dorim pentru a citi

32
00:01:41,580 --> 00:01:42,400
dicționar.

33
00:01:42,400 --> 00:01:46,210
Deci, ține looping până când vom găsi unele
motiv pentru a iesi din aceasta

34
00:01:46,210 --> 00:01:47,570
buclă pe care vom vedea.

35
00:01:47,570 --> 00:01:51,780
Deci, ține looping, iar acum vom merge
la malloc un singur nod.

36
00:01:51,780 --> 00:01:56,800
Și, desigur, avem nevoie pentru a eroare de verificare
din nou, așa că, dacă mallocing nu a reușit

37
00:01:56,800 --> 00:02:00,660
și vrem să descarce orice nod pe care le
sa întâmplat cu malloc înainte, închideți

38
00:02:00,660 --> 00:02:02,590
dicționar și a reveni false.

39
00:02:02,590 --> 00:02:07,440
>> Dar ignorând că, ne-am presupunând
a reușit, atunci vrem sa folosim fscanf

40
00:02:07,440 --> 00:02:12,400
pentru a citi un singur cuvânt de la noastră
dictionar în nodul nostru.

41
00:02:12,400 --> 00:02:17,310
Deci, amintiți-vă că cuvântul de intrare-> este char
tampon cuvânt de lungime dimensiune plus

42
00:02:17,310 --> 00:02:20,300
una care vom
stoca cuvântul inch

43
00:02:20,300 --> 00:02:25,280
Astfel fscanf este de gând să se întoarcă 1, atâta timp
așa cum a fost capabil să citească un succes

44
00:02:25,280 --> 00:02:26,750
cuvânt de la dosar.

45
00:02:26,750 --> 00:02:31,030
>> În cazul în care fie o eroare se întâmplă sau vom ajunge la
sfârșitul fișierului, nu va

46
00:02:31,030 --> 00:02:34,950
reveni 1, caz în care în caz contrar
întoarcă 1, vom în cele din urmă va rupe

47
00:02:34,950 --> 00:02:37,280
din această buclă în timp.

48
00:02:37,280 --> 00:02:42,770
Deci, vom vedea că, odată ce avem succes
citit un cuvânt în

49
00:02:42,770 --> 00:02:48,270
intrare-> cuvânt, atunci vom hash
acest cuvânt utilizând funcția noastră hash.

50
00:02:48,270 --> 00:02:49,580
Să aruncăm o privire la
funcția de distribuire.

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

52
00:02:52,430 --> 00:02:55,610
>> Deci, nu aveți cu adevărat nevoie
să înțeleagă acest lucru.

53
00:02:55,610 --> 00:02:59,460
Și, de fapt, ne-am scos acest
Funcția hash de pe internet.

54
00:02:59,460 --> 00:03:04,010
Singurul lucru pe care trebuie să recunoască este
că acest lucru are un const char * cuvânt,

55
00:03:04,010 --> 00:03:08,960
așa că, luând un șir ca intrare și
revenind un int nesemnate ca ieșire.

56
00:03:08,960 --> 00:03:12,360
Deci, asta e tot o funcție hash este, este
ia într-o intrare, vă oferă o

57
00:03:12,360 --> 00:03:14,490
index în tabelul hash.

58
00:03:14,490 --> 00:03:18,530
Observați că suntem modding de NUM_BUCKETS
astfel încât valoarea hash a revenit

59
00:03:18,530 --> 00:03:21,730
de fapt este un index în tabelul hash
și nu indicele de dincolo de

60
00:03:21,730 --> 00:03:24,320
limitele de matrice.

61
00:03:24,320 --> 00:03:27,855
>> Deci, având în vedere că funcția hash, vom
hash cuvântul pe care am citit

62
00:03:27,855 --> 00:03:31,700
din dicționar și apoi vom merge
să utilizeze care are pentru a insera

63
00:03:31,700 --> 00:03:33,750
intrare în tabelul hash.

64
00:03:33,750 --> 00:03:38,830
Acum, hash Hashtable este curentul
Lista legată în tabelul hash, și

65
00:03:38,830 --> 00:03:41,410
este foarte posibil că este doar NULL.

66
00:03:41,410 --> 00:03:45,640
Vrem să inserați intrarea nostru de la
începând din această listă legată, și așa

67
00:03:45,640 --> 00:03:48,910
vom avea intrarea noastră actuală
punctul de ce tabelul hash în prezent

68
00:03:48,910 --> 00:03:54,030
puncte pentru a și apoi vom stoca
în tabelul hash la hash

69
00:03:54,030 --> 00:03:55,350
intrarea curentă.

70
00:03:55,350 --> 00:03:59,320
>> Deci, aceste două linii se introduce cu succes
intrarea de la începutul

71
00:03:59,320 --> 00:04:02,270
Lista legat la acel index
în tabelul hash.

72
00:04:02,270 --> 00:04:04,900
După ce am terminat cu asta, știm
că am găsit un alt cuvânt în

73
00:04:04,900 --> 00:04:07,800
dicționar și am incrementa din nou.

74
00:04:07,800 --> 00:04:13,960
Așa că am continuăm să facem asta până fscanf
se întoarce în cele din urmă ceva non 1 la

75
00:04:13,960 --> 00:04:18,560
care punct amintiți-vă că trebuie să
intrare liberă, așa că aici, noi malloced o

76
00:04:18,560 --> 00:04:21,329
intrare și am încercat să citesc ceva
din dicționar.

77
00:04:21,329 --> 00:04:24,110
Și nu ne-am citit cu succes
ceva din dicționar, în care

78
00:04:24,110 --> 00:04:27,440
caz, avem nevoie pentru a elibera intrarea pe care le
nu pune de fapt în tabelul hash

79
00:04:27,440 --> 00:04:29,110
și, în final rupe.

80
00:04:29,110 --> 00:04:32,750
>> Odată ce am izbucni, avem nevoie pentru a vedea, de asemenea,
ne-am izbucni deoarece acolo

81
00:04:32,750 --> 00:04:35,840
a fost citit o eroare de fișier, sau
ne-am izbucni că am ajuns

82
00:04:35,840 --> 00:04:37,120
sfârșitul fișierului?

83
00:04:37,120 --> 00:04:40,150
Dacă a existat o eroare, atunci vrem să
return false pentru că sarcina nu a făcut

84
00:04:40,150 --> 00:04:43,260
reuși, și în acest proces, vrem să
descărca toate cuvintele pe care le-am citit

85
00:04:43,260 --> 00:04:45,670
în și închideți fișierul dicționar.

86
00:04:45,670 --> 00:04:48,740
Presupunând că am reușit, atunci ne-am
încă mai trebuie să închidă în dicționar

87
00:04:48,740 --> 00:04:51,970
dosar, și în cele din urmă a reveni adevărat, deoarece
ne-am încărcat cu succes

88
00:04:51,970 --> 00:04:53,040
dicționar.

89
00:04:53,040 --> 00:04:54,420
Și asta este pentru sarcină.

90
00:04:54,420 --> 00:04:59,020
>> Deci, acum, verifica, având în vedere un tabel hash încărcat,
este de gând să arate ca aceasta.

91
00:04:59,020 --> 00:05:02,690
Deci, a verifica, se returnează un bool, care
se va indica dacă

92
00:05:02,690 --> 00:05:07,530
a trecut-in char * cuvânt, indiferent dacă
șir a trecut-in este în dicționar nostru.

93
00:05:07,530 --> 00:05:10,530
Deci, în cazul în care acesta este în dicționar, dacă este
în masa noastră hash, ne vom întoarce

94
00:05:10,530 --> 00:05:13,380
adevărat, și dacă nu e,
ne vom întoarce false.

95
00:05:13,380 --> 00:05:17,770
Având în vedere acest cuvânt a trecut-in, suntem
merge la hash cuvântul.

96
00:05:17,770 --> 00:05:22,020
>> Acum, un lucru important să recunoaștem este
că în sarcină, am știut că toate

97
00:05:22,020 --> 00:05:25,820
cuvintele au fost de gând să fie litere mici,
dar aici, nu suntem așa de sigur.

98
00:05:25,820 --> 00:05:29,510
Dacă ne uităm la funcția noastră hash,
Funcția noastră hash de fapt

99
00:05:29,510 --> 00:05:32,700
este lowercasing fiecare personaj
al cuvântului.

100
00:05:32,700 --> 00:05:37,580
Deci, indiferent de capitalizarea de
cuvânt, funcția noastră hash se va

101
00:05:37,580 --> 00:05:42,270
returneze același indice pentru orice
capitalizare este ca aceasta ar avea

102
00:05:42,270 --> 00:05:45,280
a revenit pentru o complet cu litere mici
versiune a cuvântului.

103
00:05:45,280 --> 00:05:45,950
Bine.

104
00:05:45,950 --> 00:05:47,410
>> Deci, asta e indexul nostru.

105
00:05:47,410 --> 00:05:49,790
Este tabelul hash pentru acest cuvânt.

106
00:05:49,790 --> 00:05:52,940
Acum, acest lucru pentru bucla se întâmplă
la peste lista de legătura

107
00:05:52,940 --> 00:05:55,000
care a fost la acel index.

108
00:05:55,000 --> 00:05:59,630
Deci observa suntem inițializarea intrare
pentru a indica faptul că index.

109
00:05:59,630 --> 00:06:03,480
Vom continua în timp ce intrarea nu
Nu NULL egal, și amintiți-vă că

110
00:06:03,480 --> 00:06:08,350
actualizarea indicatorul în lista noastră legată
de intrare este egal cu intrare-> următor, așa că au

111
00:06:08,350 --> 00:06:13,840
punctul nostru de intrare curent la
următorul element în listă legat.

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

113
00:06:14,400 --> 00:06:19,150
>> Deci, pentru fiecare intrare în lista de legat,
vom folosi strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Nu strcmp pentru că, încă o dată, ne-am
vrei sa faci lucruri caz fără sensibilitate.

115
00:06:23,780 --> 00:06:28,830
Deci, vom folosi strcasecmp pentru a compara cuvântul
care a fost trecut la această funcție

116
00:06:28,830 --> 00:06:31,860
împotriva cuvântul care
este în această intrare.

117
00:06:31,860 --> 00:06:35,570
În cazul în care se întoarce 0, înseamnă că nu a fost
un meci, în cazul în care dorim să

118
00:06:35,570 --> 00:06:36,630
return true.

119
00:06:36,630 --> 00:06:39,590
Am găsit cu succes
cuvânt în masa noastră hash.

120
00:06:39,590 --> 00:06:43,040
>> Dacă nu a fost un meci, atunci suntem
merge la bucla din nou si uita-te la

121
00:06:43,040 --> 00:06:43,990
intrare următor.

122
00:06:43,990 --> 00:06:47,640
Și vom continua looping în timp ce acolo
sunt intrări în această listă legat.

123
00:06:47,640 --> 00:06:50,160
Ce se întâmplă dacă am rupe
din aceasta pentru buclă?

124
00:06:50,160 --> 00:06:55,110
Asta înseamnă că nu am găsit o intrare care
potrivit acest cuvânt, în care caz

125
00:06:55,110 --> 00:07:00,220
ne întoarcem false pentru a indica faptul că noastră
tabel hash nu conțin acest cuvânt.

126
00:07:00,220 --> 00:07:01,910
Și asta este pentru verificare.

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

128
00:07:02,540 --> 00:07:04,790
>> Deci, haideți să aruncăm o privire la dimensiune.

129
00:07:04,790 --> 00:07:09,280
Acum, dimensiunea va fi destul de simplu
amintiți-vă, deoarece în sarcină, pentru fiecare cuvânt

130
00:07:09,280 --> 00:07:12,880
am găsit am incrementat un global
hashtable_size variabilă.

131
00:07:12,880 --> 00:07:15,830
Deci, funcția de dimensiunea este doar
O să se întoarcă că la nivel mondial

132
00:07:15,830 --> 00:07:18,150
variabilă, și asta e tot.

133
00:07:18,150 --> 00:07:22,300
>> Acum, în cele din urmă, avem nevoie pentru a descărca
dicționar dată totul sa terminat.

134
00:07:22,300 --> 00:07:25,340
Deci, cum vom face asta?

135
00:07:25,340 --> 00:07:30,440
Chiar aici, suntem looping peste tot
găleți de masa noastră hash.

136
00:07:30,440 --> 00:07:33,240
Deci, există NUM_BUCKETS galeti.

137
00:07:33,240 --> 00:07:37,490
Și pentru fiecare listă legată în hash nostru
masă, vom bucla peste

138
00:07:37,490 --> 00:07:41,070
întregime din lista de legătura
eliberând fiecare element.

139
00:07:41,070 --> 00:07:46,070
Acum, trebuie să fim atenți, așa că aici am
au o variabilă temporar care este

140
00:07:46,070 --> 00:07:49,740
stocarea indicatorul la alta
element din lista de legătura.

141
00:07:49,740 --> 00:07:52,140
Și apoi vom liber
elementul curent.

142
00:07:52,140 --> 00:07:55,990
>> Avem nevoie pentru a fi sigur că vom face acest lucru, deoarece ne-am
nu se poate elibera doar elementul curent

143
00:07:55,990 --> 00:07:59,260
și apoi încercați să accesați indicatorul următor
deoarece odată ce l-am eliberat

144
00:07:59,260 --> 00:08:00,870
memorie devine invalid.

145
00:08:00,870 --> 00:08:04,990
Deci, avem nevoie pentru a menține în jurul valorii de un pointer la
elementul următor, atunci ne putem elibera

146
00:08:04,990 --> 00:08:08,360
element de curent, și apoi putem actualiza
elementul nostru curent de a indica

147
00:08:08,360 --> 00:08:09,590
elementul următor.

148
00:08:09,590 --> 00:08:12,770
>> Vom buclă în timp ce există elemente
în această listă legat.

149
00:08:12,770 --> 00:08:16,450
Vom face acest lucru pentru toate listele legate în
tabelul hash, și o dată am terminat

150
00:08:16,450 --> 00:08:20,180
cu care, am descărcată complet
tabelul hash, și am terminat.

151
00:08:20,180 --> 00:08:24,050
Deci, este imposibil pentru descarcă de tot
return false, și când am terminat, ne-am

152
00:08:24,050 --> 00:08:25,320
doar return true.

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