1
00:00:00,000 --> 00:00:12,350
>> [MUSIC CHƠI]

2
00:00:12,350 --> 00:00:13,050
>> ROB Bowden: Hi.

3
00:00:13,050 --> 00:00:13,640
Tôi Rob.

4
00:00:13,640 --> 00:00:16,210
Và chúng ta hãy giải pháp này ra.

5
00:00:16,210 --> 00:00:20,070
Vì vậy, ở đây chúng ta sẽ thực hiện
một bảng nói chung.

6
00:00:20,070 --> 00:00:24,090
Chúng ta thấy rằng các nút cấu trúc của chúng tôi
bảng sẽ trông như thế này.

7
00:00:24,090 --> 00:00:28,710
Vì vậy, nó sẽ có một từ char
mảng có kích thước Độ dài + 1.

8
00:00:28,710 --> 00:00:32,259
Đừng quên + 1, vì tối đa
từ trong từ điển là 45

9
00:00:32,259 --> 00:00:33,130
ký tự.

10
00:00:33,130 --> 00:00:37,070
Và sau đó chúng ta sẽ cần một thêm
nhân vật cho không dấu gạch chéo ngược.

11
00:00:37,070 --> 00:00:40,870
>> Và sau đó hashtable của chúng tôi trong mỗi
xô là sẽ lưu một

12
00:00:40,870 --> 00:00:42,320
danh sách liên kết của các nút.

13
00:00:42,320 --> 00:00:44,420
Chúng tôi không làm tuyến tính thăm dò ở đây.

14
00:00:44,420 --> 00:00:48,430
Và như vậy để liên kết đến tiếp theo
yếu tố trong xô, chúng ta cần một

15
00:00:48,430 --> 00:00:50,390
struct node * next.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Vì vậy, đó là những gì một nút như thế nào.

18
00:00:53,090 --> 00:00:56,180
>> Bây giờ ở đây là khai báo
của Hashtable của chúng tôi.

19
00:00:56,180 --> 00:00:59,640
Nó sẽ có 16.834 thùng.

20
00:00:59,640 --> 00:01:01,910
Nhưng con số đó không quan trọng.

21
00:01:01,910 --> 00:01:05,450
Và cuối cùng, chúng ta sẽ có
kích thước hashtable biến toàn cầu, trong đó

22
00:01:05,450 --> 00:01:07,000
sẽ bắt đầu như là số không.

23
00:01:07,000 --> 00:01:10,760
Và nó sẽ theo dõi như thế nào
nhiêu từ trong từ điển của chúng tôi.

24
00:01:10,760 --> 00:01:13,710
>> Vì vậy, chúng ta hãy nhìn vào tải.

25
00:01:13,710 --> 00:01:16,390
Chú ý tải đó, nó trả về một bool.

26
00:01:16,390 --> 00:01:20,530
Bạn trở về đúng nếu nó là thành công
nạp, và sai khác.

27
00:01:20,530 --> 00:01:23,990
Và phải mất một char * const từ điển,
đó là từ điển

28
00:01:23,990 --> 00:01:25,280
mà chúng tôi muốn mở.

29
00:01:25,280 --> 00:01:27,170
Vì vậy, đó là điều đầu tiên
chúng ta sẽ làm.

30
00:01:27,170 --> 00:01:29,500
>> Chúng ta sẽ fopen các
từ điển để đọc.

31
00:01:29,500 --> 00:01:31,680
Và chúng ta sẽ phải làm
chắc chắn rằng nó đã thành công.

32
00:01:31,680 --> 00:01:35,920
Vì vậy, nếu nó trở về NULL, sau đó chúng tôi đã không
mở thành công từ điển.

33
00:01:35,920 --> 00:01:37,440
Và chúng ta cần phải trả về false.

34
00:01:37,440 --> 00:01:41,580
Nhưng giả định rằng nó đã thành công
mở, sau đó chúng tôi muốn đọc

35
00:01:41,580 --> 00:01:42,400
từ điển.

36
00:01:42,400 --> 00:01:46,450
Vì vậy, giữ vòng lặp cho đến khi chúng tôi tìm thấy một số
lý do để thoát ra khỏi vòng lặp này,

37
00:01:46,450 --> 00:01:47,570
mà chúng ta sẽ thấy.

38
00:01:47,570 --> 00:01:48,920
Vì vậy, giữ vòng lặp.

39
00:01:48,920 --> 00:01:51,780
>> Và bây giờ chúng ta sẽ
malloc một nút duy nhất.

40
00:01:51,780 --> 00:01:54,020
Và tất nhiên chúng ta cần
phát sóng kiểm tra lại.

41
00:01:54,020 --> 00:01:58,680
Vì vậy, nếu mallocing đã không thành công, sau đó
chúng tôi muốn dỡ bỏ bất kỳ nút mà chúng ta

42
00:01:58,680 --> 00:02:02,590
đã xảy ra với malloc trước, đóng cửa
từ điển và trả về false.

43
00:02:02,590 --> 00:02:06,830
Nhưng bỏ qua mà, giả sử chúng ta
đã thành công, sau đó chúng tôi muốn sử dụng fscanf

44
00:02:06,830 --> 00:02:12,400
để đọc một từ duy nhất từ ​​chúng tôi
từ điển vào nút của chúng tôi.

45
00:02:12,400 --> 00:02:17,940
Vì vậy, hãy nhớ rằng mục> từ là char
đệm từ kích thước lenghth + 1

46
00:02:17,940 --> 00:02:20,300
rằng chúng ta sẽ lưu trữ các từ in

47
00:02:20,300 --> 00:02:25,070
>> Vì vậy, fscanf sẽ trở về 1, miễn
vì nó đã có thể thành công

48
00:02:25,070 --> 00:02:26,750
đọc một từ từ tập tin.

49
00:02:26,750 --> 00:02:30,460
Nếu một trong hai lỗi xảy ra, hoặc chúng tôi
đến cuối của tập tin, nó

50
00:02:30,460 --> 00:02:31,950
sẽ không trở lại 1.

51
00:02:31,950 --> 00:02:35,180
Trong trường hợp này nó không trả lại 1,
chúng ta cuối cùng sẽ thoát ra khỏi

52
00:02:35,180 --> 00:02:37,280
trong khi vòng lặp này.

53
00:02:37,280 --> 00:02:42,770
Vì vậy, chúng ta thấy rằng một khi chúng ta đã thành công
đọc một từ vào

54
00:02:42,770 --> 00:02:48,270
entry> từ, sau đó chúng ta sẽ có
từ sử dụng hàm băm của chúng tôi.

55
00:02:48,270 --> 00:02:49,580
>> Chúng ta hãy nhìn vào
hàm băm.

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

57
00:02:52,430 --> 00:02:55,610
Vì vậy, bạn không thực sự cần
để hiểu được điều này.

58
00:02:55,610 --> 00:02:59,460
Và thực sự chúng ta chỉ cần kéo băm này
hoạt động từ internet.

59
00:02:59,460 --> 00:03:04,010
Điều duy nhất bạn cần phải nhận ra là
rằng điều này có một const char * từ.

60
00:03:04,010 --> 00:03:08,960
Vì vậy, nó tham gia một chuỗi như là đầu vào, và
trả lại một int unsigned như đầu ra.

61
00:03:08,960 --> 00:03:12,360
Vì vậy, đó là tất cả một hàm băm được, là nó
mất trong một đầu vào và cung cấp cho bạn một

62
00:03:12,360 --> 00:03:14,490
chỉ số vào hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Chú ý rằng chúng ta đang moding bởi NUM_BUCKETS,
nên giá trị trở lại

64
00:03:18,530 --> 00:03:21,730
thực sự là một chỉ số vào hashtable
và không chỉ vượt ra ngoài

65
00:03:21,730 --> 00:03:24,320
giới hạn của mảng.

66
00:03:24,320 --> 00:03:28,060
Vì vậy, cho chức năng đó, chúng ta sẽ
để băm từ đó chúng ta đọc

67
00:03:28,060 --> 00:03:29,390
từ điển.

68
00:03:29,390 --> 00:03:31,700
Và sau đó chúng ta sẽ sử dụng
mà băm để chèn

69
00:03:31,700 --> 00:03:33,750
nhập cảnh vào hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Băm bây giờ Hashtable là hiện tại
danh sách liên kết trong bảng.

71
00:03:38,520 --> 00:03:41,410
Và nó rất có thể
rằng nó chỉ là NULL.

72
00:03:41,410 --> 00:03:44,960
Chúng tôi muốn chèn mục của chúng tôi tại
bắt đầu của danh sách liên kết này.

73
00:03:44,960 --> 00:03:48,600
Và như vậy chúng ta sẽ có hiện tại của chúng tôi
điểm vào những gì hashtable

74
00:03:48,600 --> 00:03:50,380
hiện đang trỏ tới.

75
00:03:50,380 --> 00:03:53,310
Và sau đó chúng ta sẽ lưu trữ,
trong hashtable tại

76
00:03:53,310 --> 00:03:55,350
băm, mục hiện hành.

77
00:03:55,350 --> 00:03:59,320
Vì vậy, hai dòng chèn thành công
nhập cảnh tại các đầu

78
00:03:59,320 --> 00:04:02,260
danh sách liên kết tại chỉ số đó
trong hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Một khi chúng ta đang thực hiện với đó, chúng tôi biết
mà chúng ta tìm thấy một từ khác trong

80
00:04:04,900 --> 00:04:07,790
từ điển, và chúng tôi tăng một lần nữa.

81
00:04:07,790 --> 00:04:13,960
Vì vậy, chúng tôi tiếp tục làm điều đó cho đến khi fscanf
cuối cùng trở về một cái gì đó không-1 tại

82
00:04:13,960 --> 00:04:16,950
thời điểm đó nhớ rằng
chúng ta cần phải giải phóng vào.

83
00:04:16,950 --> 00:04:19,459
Vì vậy, ở đây chúng tôi malloced một mục.

84
00:04:19,459 --> 00:04:21,329
Và chúng tôi cố gắng để đọc một cái gì đó
từ điển.

85
00:04:21,329 --> 00:04:23,910
Và chúng tôi đã không đọc thành công
một cái gì đó từ từ điển, trong

86
00:04:23,910 --> 00:04:26,650
trường hợp mà chúng ta cần để giải phóng các mục
rằng chúng ta không bao giờ thực sự đưa vào

87
00:04:26,650 --> 00:04:29,140
Hashtable, và cuối cùng phá vỡ.

88
00:04:29,140 --> 00:04:32,750
>> Một khi chúng ta thoát ra khỏi chúng ta cần phải nhìn thấy, tốt,
chúng tôi đã phá vỡ ra bởi vì có

89
00:04:32,750 --> 00:04:34,360
được một lỗi đọc từ tập tin?

90
00:04:34,360 --> 00:04:37,120
Hoặc chúng ta đã thoát ra khỏi bởi vì chúng tôi
đạt đến kết thúc của tập tin?

91
00:04:37,120 --> 00:04:39,480
Nếu có một lỗi, sau đó
chúng ta muốn trả về false.

92
00:04:39,480 --> 00:04:40,930
Vì tải không thành công.

93
00:04:40,930 --> 00:04:43,890
Và trong quá trình chúng tôi muốn dỡ bỏ
tất cả các từ mà chúng ta đọc trong, và

94
00:04:43,890 --> 00:04:45,670
đóng tập tin từ điển.

95
00:04:45,670 --> 00:04:48,740
>> Giả sử chúng ta đã thành công, sau đó chúng tôi chỉ
vẫn cần phải đóng cửa từ điển

96
00:04:48,740 --> 00:04:53,040
tập tin, và cuối cùng trở về đúng kể từ khi chúng tôi
nạp thành công từ điển.

97
00:04:53,040 --> 00:04:54,420
Và đó là nó cho tải.

98
00:04:54,420 --> 00:04:59,020
Vì vậy, bây giờ kiểm tra, đưa ra một hashtable tải,
sẽ trông như thế này.

99
00:04:59,020 --> 00:05:03,140
Vì vậy, kiểm tra, nó trả về một bool, đó là
sẽ chỉ ra cho dù thông qua

100
00:05:03,140 --> 00:05:07,530
trong char * từ, cho dù thông qua
trong chuỗi là trong từ điển của chúng tôi.

101
00:05:07,530 --> 00:05:09,890
Vì vậy, nếu nó có trong từ điển,
nếu nó là trong Hashtable của chúng tôi,

102
00:05:09,890 --> 00:05:11,170
chúng tôi sẽ trở lại đúng sự thật.

103
00:05:11,170 --> 00:05:13,380
Và nếu nó không phải, chúng tôi sẽ trả về false.

104
00:05:13,380 --> 00:05:17,740
>> Vì điều này thông qua trong lời nói, chúng tôi
sẽ băm từ.

105
00:05:17,740 --> 00:05:22,110
Bây giờ là một điều quan trọng cần nhận ra là
mà trong tải chúng tôi biết rằng tất cả các

106
00:05:22,110 --> 00:05:23,820
Nói cách chúng ta sẽ được trường hợp thấp hơn.

107
00:05:23,820 --> 00:05:25,820
Nhưng ở đây chúng tôi không như vậy chắc chắn.

108
00:05:25,820 --> 00:05:29,510
Nếu chúng ta hãy nhìn vào hàm băm của chúng tôi,
hàm băm của chúng tôi thực sự

109
00:05:29,510 --> 00:05:32,700
là vỏ thấp hơn mỗi nhân vật
của từ.

110
00:05:32,700 --> 00:05:37,940
Vì vậy, bất kể giá trị vốn hóa của
từ, hàm băm của chúng tôi là sự trở lại

111
00:05:37,940 --> 00:05:42,270
chỉ số tương tự cho bất cứ điều gì
vốn là, vì nó sẽ có

112
00:05:42,270 --> 00:05:45,280
trả lại cho một hoàn toàn chữ thường
phiên bản của từ.

113
00:05:45,280 --> 00:05:46,600
Được rồi.

114
00:05:46,600 --> 00:05:49,790
Đó là chỉ số của chúng tôi là vào
Hashtable cho từ này.

115
00:05:49,790 --> 00:05:52,940
>> Bây giờ điều này cho vòng lặp sẽ
duyệt qua danh sách liên kết

116
00:05:52,940 --> 00:05:55,000
đó là tại chỉ số đó.

117
00:05:55,000 --> 00:05:59,610
Vì vậy, nhận thấy chúng ta đang khởi nhập
để trỏ đến chỉ số.

118
00:05:59,610 --> 00:06:02,750
Chúng tôi sẽ tiếp tục
trong khi nhập cảnh! = NULL.

119
00:06:02,750 --> 00:06:07,770
Và hãy nhớ rằng việc cập nhật con trỏ
trong danh sách của chúng tôi trường liên kết = entry> tiếp theo.

120
00:06:07,770 --> 00:06:14,400
Vì vậy, có điểm vào hiện tại của chúng tôi để
mục tiếp theo trong danh sách liên kết.

121
00:06:14,400 --> 00:06:19,250
>> Vì vậy, cho mỗi mục trong danh sách liên kết,
chúng ta sẽ sử dụng strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Nó không phải strcomp.

123
00:06:20,330 --> 00:06:23,780
Bởi vì một lần nữa, chúng tôi muốn
làm những việc trường hợp insensitively.

124
00:06:23,780 --> 00:06:27,870
Vì vậy, chúng tôi sử dụng strcasecmp để so sánh
từ đó đã được thông qua thông qua này

125
00:06:27,870 --> 00:06:31,860
chức năng chống lại các từ
đó là trong mục này.

126
00:06:31,860 --> 00:06:35,570
Nếu nó trả về số không, có nghĩa là đã có
một trận đấu, trong trường hợp này chúng tôi muốn

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

128
00:06:36,630 --> 00:06:39,590
Chúng tôi tìm thấy thành công
từ trong Hashtable của chúng tôi.

129
00:06:39,590 --> 00:06:43,040
>> Nếu không có một trận đấu, thì chúng ta
đi lặp lại và nhìn vào

130
00:06:43,040 --> 00:06:43,990
mục tiếp theo.

131
00:06:43,990 --> 00:06:47,640
Và chúng tôi sẽ tiếp tục vòng lặp trong khi có
là các mục trong danh sách liên kết này.

132
00:06:47,640 --> 00:06:50,160
Điều gì xảy ra nếu chúng ta phá vỡ
trong số này cho vòng lặp?

133
00:06:50,160 --> 00:06:55,110
Điều đó có nghĩa chúng tôi không tìm thấy một mục mà
kết hợp từ này, trong trường hợp

134
00:06:55,110 --> 00:07:00,220
chúng tôi trả về false để chỉ ra rằng chúng tôi
Hashtable không chứa từ này.

135
00:07:00,220 --> 00:07:02,540
Và đó là một kiểm tra.

136
00:07:02,540 --> 00:07:04,790
>> Vì vậy, chúng ta hãy nhìn vào kích thước.

137
00:07:04,790 --> 00:07:06,970
Bây giờ kích thước sẽ là khá đơn giản.

138
00:07:06,970 --> 00:07:11,080
Kể từ khi nhớ trong tải, cho mỗi từ
chúng tôi tìm thấy, chúng tôi tăng lên một toàn cầu

139
00:07:11,080 --> 00:07:12,880
kích thước hashtable biến.

140
00:07:12,880 --> 00:07:16,480
Vì vậy, các chức năng kích thước là chỉ cần đi
trở lại biến toàn cầu.

141
00:07:16,480 --> 00:07:18,150
Và đó là nó.

142
00:07:18,150 --> 00:07:22,300
>> Bây giờ cuối cùng, chúng ta cần phải dỡ bỏ các
từ điển một lần tất cả mọi thứ được thực hiện.

143
00:07:22,300 --> 00:07:25,340
Vì vậy, làm thế nào chúng tôi sẽ làm điều đó?

144
00:07:25,340 --> 00:07:30,440
Ở đây chúng ta đang Looping trên
tất cả các thùng bảng của chúng tôi.

145
00:07:30,440 --> 00:07:33,240
Vì vậy, có NUM_BUCKETS xô.

146
00:07:33,240 --> 00:07:37,410
Và cho mỗi danh sách liên kết của chúng tôi trong
Hashtable, chúng ta sẽ lặp trên

147
00:07:37,410 --> 00:07:41,070
toàn bộ danh sách liên kết,
giải phóng mỗi yếu tố.

148
00:07:41,070 --> 00:07:42,900
>> Bây giờ chúng ta cần phải cẩn thận.

149
00:07:42,900 --> 00:07:47,910
Vì vậy, ở đây chúng tôi có một biến tạm thời
đó là lưu trữ các con trỏ đến tiếp theo

150
00:07:47,910 --> 00:07:49,730
phần tử trong danh sách liên kết.

151
00:07:49,730 --> 00:07:52,140
Và sau đó chúng tôi sẽ miễn phí
các yếu tố hiện tại.

152
00:07:52,140 --> 00:07:55,990
Chúng tôi cần phải chắc chắn chúng tôi làm điều này vì chúng ta
không thể chỉ giải phóng các yếu tố hiện tại

153
00:07:55,990 --> 00:07:59,180
và sau đó cố gắng truy cập vào các con trỏ tới,
kể từ khi chúng tôi đã giải phóng nó,

154
00:07:59,180 --> 00:08:00,870
bộ nhớ trở nên không hợp lệ.

155
00:08:00,870 --> 00:08:04,990
>> Vì vậy, chúng ta cần phải giữ cho xung quanh một con trỏ tới
các yếu tố tiếp theo, sau đó chúng tôi có thể giải phóng

156
00:08:04,990 --> 00:08:08,360
yếu tố hiện tại, và sau đó chúng tôi có thể cập nhật
phần tử hiện tại của chúng tôi để trỏ đến

157
00:08:08,360 --> 00:08:09,550
các yếu tố tiếp theo.

158
00:08:09,550 --> 00:08:12,800
Chúng tôi sẽ vòng lặp trong khi có những yếu tố
trong danh sách liên kết này.

159
00:08:12,800 --> 00:08:15,620
Chúng tôi sẽ làm điều đó cho tất cả các liên kết
danh sách trong hashtable.

160
00:08:15,620 --> 00:08:19,460
Và một khi chúng tôi đang thực hiện với đó, chúng tôi đã
hoàn toàn dỡ Hashtable, và

161
00:08:19,460 --> 00:08:20,190
chúng tôi đang thực hiện.

162
00:08:20,190 --> 00:08:23,200
Vì vậy, nó không thể dỡ bỏ
bao giờ trở lại sai.

163
00:08:23,200 --> 00:08:26,470
Và khi chúng tôi đang thực hiện, chúng tôi
chỉ trả lại sự thật.

164
00:08:26,470 --> 00:08:29,000
>> Chúng ta hãy đưa ra giải pháp này một thử.

165
00:08:29,000 --> 00:08:33,070
Vì vậy, chúng ta hãy nhìn vào những gì chúng tôi
struct node sẽ như thế nào.

166
00:08:33,070 --> 00:08:36,220
Ở đây chúng ta thấy chúng ta sẽ có một bool
từ và một nút cấu trúc * trẻ em

167
00:08:36,220 --> 00:08:37,470
khung bảng chữ cái.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Vì vậy, điều đầu tiên bạn có thể
tự hỏi, tại sao là bảng chữ cái

170
00:08:42,020 --> 00:08:44,660
ed định nghĩa là 27?

171
00:08:44,660 --> 00:08:47,900
Vâng, hãy nhớ rằng chúng ta sẽ cần
được xử lý dấu nháy đơn.

172
00:08:47,900 --> 00:08:51,910
Vì vậy, đó sẽ là một số của một
trường hợp đặc biệt trong suốt chương trình này.

173
00:08:51,910 --> 00:08:54,710
>> Bây giờ nhớ làm thế nào một Trie
thực sự hoạt động.

174
00:08:54,710 --> 00:08:59,380
Hãy nói rằng chúng tôi đang lập chỉ mục từ
"Mèo". Sau đó từ thư mục gốc của Trie,

175
00:08:59,380 --> 00:09:02,610
chúng ta sẽ nhìn vào trẻ em
mảng, và chúng ta sẽ xem xét các

176
00:09:02,610 --> 00:09:08,090
chỉ số tương ứng với chữ cái
C. Vì vậy, đó sẽ được lập chỉ mục 2.

177
00:09:08,090 --> 00:09:11,530
Vì vậy, cho rằng, điều đó sẽ
cung cấp cho chúng ta một nút mới.

178
00:09:11,530 --> 00:09:13,820
Và sau đó chúng tôi sẽ làm việc từ nút đó.

179
00:09:13,820 --> 00:09:17,770
>> Vì vậy, cho nút đó, chúng tôi lại một lần nữa
sẽ xem xét các mảng trẻ em.

180
00:09:17,770 --> 00:09:22,110
Và chúng ta sẽ nhìn vào chỉ số không
tương ứng với một trong mèo.

181
00:09:22,110 --> 00:09:27,170
Vì vậy, sau đó chúng ta sẽ đi đến nút đó,
và cho nút đó chúng ta sẽ

182
00:09:27,170 --> 00:09:31,090
nhìn ở cuối đó là một tương ứng
T. Và chuyển sang nút đó,

183
00:09:31,090 --> 00:09:35,530
cuối cùng, chúng tôi đã hoàn toàn nhìn
qua lời của chúng tôi "con mèo." Và bây giờ bool

184
00:09:35,530 --> 00:09:40,960
từ được cho là để cho biết
từ cho điều này thực sự là một từ.

185
00:09:40,960 --> 00:09:43,470
>> Vì vậy, tại sao chúng ta cần phải có trường hợp đặc biệt?

186
00:09:43,470 --> 00:09:47,700
Tốt những gì của từ "thảm họa"
là trong từ điển của chúng tôi, nhưng

187
00:09:47,700 --> 00:09:50,150
từ "mèo" không?

188
00:09:50,150 --> 00:09:54,580
Vì vậy, và tìm cách để xem từ "con mèo"
được trong từ điển của chúng tôi, chúng tôi

189
00:09:54,580 --> 00:09:59,970
sẽ xem xét thông qua thành công
các chỉ số C-A-T trong khu vực nút.

190
00:09:59,970 --> 00:10:04,290
Nhưng đó chỉ là vì thảm họa
đã xảy ra để tạo ra các nút trên đường

191
00:10:04,290 --> 00:10:07,190
từ C-A-T, tất cả các cách để
cuối của từ đó.

192
00:10:07,190 --> 00:10:12,020
Vì vậy, bool từ được sử dụng để cho biết
địa điểm cụ thể này

193
00:10:12,020 --> 00:10:14,310
thực sự chỉ ra một từ.

194
00:10:14,310 --> 00:10:15,140
>> Được rồi.

195
00:10:15,140 --> 00:10:19,310
Vì vậy, bây giờ mà chúng ta biết là những gì Trie
sẽ như thế nào, chúng ta hãy nhìn vào

196
00:10:19,310 --> 00:10:20,730
tải chức năng.

197
00:10:20,730 --> 00:10:24,610
Vì vậy, tải sẽ trả về một bool
cho dù chúng ta có thành công hay

198
00:10:24,610 --> 00:10:26,720
không thành công nạp từ điển.

199
00:10:26,720 --> 00:10:30,460
Và điều này là có được từ điển
mà chúng tôi muốn để tải.

200
00:10:30,460 --> 00:10:33,930
>> Điều đầu tiên nên chúng tôi phải làm là mở
up từ điển để đọc.

201
00:10:33,930 --> 00:10:36,160
Và chúng tôi phải chắc chắn
chúng tôi đã không thất bại.

202
00:10:36,160 --> 00:10:39,580
Vì vậy, nếu không phải là từ điển
mở thành công, nó sẽ trở lại

203
00:10:39,580 --> 00:10:42,400
null, trong trường hợp chúng tôi
sẽ trả về false.

204
00:10:42,400 --> 00:10:47,230
Nhưng giả định rằng nó thành công
mở ra, sau đó chúng tôi thực sự có thể đọc

205
00:10:47,230 --> 00:10:48,220
thông qua các từ điển.

206
00:10:48,220 --> 00:10:50,880
>> Điều đầu tiên để chúng ta sẽ
muốn làm là chúng tôi có điều này

207
00:10:50,880 --> 00:10:52,500
gốc biến toàn cầu.

208
00:10:52,500 --> 00:10:56,190
Bây giờ gốc là có được một nút *.

209
00:10:56,190 --> 00:10:59,760
Đó là đầu Trie của chúng tôi rằng chúng tôi
sẽ được lặp lại thông qua.

210
00:10:59,760 --> 00:11:02,660
Vì vậy, điều đầu tiên mà chúng ta sẽ
muốn làm là phân bổ

211
00:11:02,660 --> 00:11:04,140
bộ nhớ cho rễ của chúng tôi.

212
00:11:04,140 --> 00:11:07,980
Chú ý rằng chúng ta đang sử dụng calloc
chức năng, mà về cơ bản là giống nhau

213
00:11:07,980 --> 00:11:11,500
như chức năng malloc, ngoại trừ nó
đảm bảo để trở về cái gì đó là

214
00:11:11,500 --> 00:11:13,180
hoàn toàn zeroed ra.

215
00:11:13,180 --> 00:11:17,290
Vì vậy, nếu chúng tôi sử dụng malloc, chúng tôi sẽ cần phải
đi qua tất cả các con trỏ trong của chúng tôi

216
00:11:17,290 --> 00:11:20,160
nút, và chắc chắn rằng
tất cả chúng null.

217
00:11:20,160 --> 00:11:22,710
Vì vậy, calloc sẽ làm điều đó cho chúng ta.

218
00:11:22,710 --> 00:11:26,330
>> Bây giờ chỉ cần như malloc, chúng tôi cần phải thực hiện
chắc chắn rằng sự phân bổ là thực sự

219
00:11:26,330 --> 00:11:27,520
thành công.

220
00:11:27,520 --> 00:11:29,990
Nếu điều này trở về null, sau đó chúng tôi
cần phải đóng hoặc từ điển

221
00:11:29,990 --> 00:11:32,100
nộp và trả về false.

222
00:11:32,100 --> 00:11:36,835
Vì vậy, giả định phân bổ được
thành công, chúng ta sẽ sử dụng một nút *

223
00:11:36,835 --> 00:11:40,270
con trỏ để lặp qua Trie của chúng tôi.

224
00:11:40,270 --> 00:11:43,890
Vì vậy, nguồn gốc của mình sẽ không bao giờ thay đổi,
nhưng chúng ta sẽ sử dụng con trỏ đến

225
00:11:43,890 --> 00:11:47,875
thực sự đi từ nút đến nút.

226
00:11:47,875 --> 00:11:50,940
>> Vì vậy, trong này cho vòng lặp chúng ta đang đọc
thông qua các tập tin từ điển.

227
00:11:50,940 --> 00:11:53,670
Và chúng tôi đang sử dụng fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc sẽ lấy một đơn
nhân vật từ tập tin.

229
00:11:56,290 --> 00:11:59,370
Chúng tôi sẽ tiếp tục lấy
ký tự trong khi chúng tôi không đạt được

230
00:11:59,370 --> 00:12:01,570
cuối của tập tin.

231
00:12:01,570 --> 00:12:03,480
>> Có hai trường hợp chúng ta cần phải xử lý.

232
00:12:03,480 --> 00:12:06,610
Đầu tiên, nếu nhân vật
không phải là một dòng mới.

233
00:12:06,610 --> 00:12:10,450
Vì vậy chúng tôi biết nếu nó là một dòng mới, sau đó
chúng tôi về để chuyển sang một từ mới.

234
00:12:10,450 --> 00:12:15,240
Nhưng giả sử nó không phải là một dòng mới, sau đó
ở đây chúng tôi muốn tìm ra

235
00:12:15,240 --> 00:12:18,380
chỉ số chúng ta sẽ chỉ vào
trong mảng trẻ em

236
00:12:18,380 --> 00:12:19,810
chúng tôi xem xét trước.

237
00:12:19,810 --> 00:12:23,880
>> Vì vậy, như tôi đã nói, chúng ta cần phải
trường hợp đặc biệt các dấu nháy đơn.

238
00:12:23,880 --> 00:12:26,220
Lưu ý chúng đang sử dụng ba yếu tố
điều hành ở đây.

239
00:12:26,220 --> 00:12:29,580
Vì vậy, chúng ta sẽ đọc như, nếu
nhân vật chúng ta đọc trong là một

240
00:12:29,580 --> 00:12:35,330
dấu nháy đơn, sau đó chúng ta sẽ thiết lập
index = "bảng chữ cái" -1, mà sẽ

241
00:12:35,330 --> 00:12:37,680
là chỉ số 26.

242
00:12:37,680 --> 00:12:41,130
>> Khác, nếu nó không phải là một dấu nháy đơn, có
chúng ta sẽ thiết lập các chỉ số

243
00:12:41,130 --> 00:12:43,760
bằng c - a.

244
00:12:43,760 --> 00:12:49,030
Vì vậy, nhớ lại từ trước đó p-bộ,
c - một sẽ cung cấp cho chúng tôi

245
00:12:49,030 --> 00:12:53,410
vị trí chữ cái của C. Vì vậy, nếu
C là ký tự A, điều này sẽ

246
00:12:53,410 --> 00:12:54,700
cung cấp cho chúng tôi số không.

247
00:12:54,700 --> 00:12:58,120
Đối với chữ B, nó sẽ cho
chúng tôi chỉ số 1, và như vậy.

248
00:12:58,120 --> 00:13:03,010
>> Vì vậy, điều này cho phép chúng ta chỉ mục vào
trẻ em mảng mà chúng ta muốn.

249
00:13:03,010 --> 00:13:08,890
Bây giờ nếu chỉ số này hiện đang vô giá trị trong
trẻ em, đó có nghĩa là một nút

250
00:13:08,890 --> 00:13:11,830
hiện không tồn tại
từ con đường đó.

251
00:13:11,830 --> 00:13:15,160
Vì vậy, chúng ta cần phải phân bổ
một nút cho con đường đó.

252
00:13:15,160 --> 00:13:16,550
Đó là những gì chúng tôi sẽ làm ở đây.

253
00:13:16,550 --> 00:13:20,690
>> Vì vậy, chúng ta sẽ một lần nữa sử dụng calloc
chức năng, để chúng ta không phải

254
00:13:20,690 --> 00:13:22,880
không ra tất cả các con trỏ.

255
00:13:22,880 --> 00:13:27,240
Và chúng tôi một lần nữa cần phải kiểm tra
calloc mà không thất bại.

256
00:13:27,240 --> 00:13:30,700
Nếu calloc đã thất bại, sau đó chúng ta cần
dỡ bỏ tất cả mọi thứ, đóng cửa của chúng tôi

257
00:13:30,700 --> 00:13:32,820
từ điển, và trả về false.

258
00:13:32,820 --> 00:13:40,050
Vì vậy, giả định rằng nó đã không thất bại, sau đó
điều này sẽ tạo ra một đứa trẻ mới cho chúng tôi.

259
00:13:40,050 --> 00:13:41,930
Và sau đó chúng ta sẽ đi đến đứa trẻ.

260
00:13:41,930 --> 00:13:44,960
Con trỏ của chúng tôi sẽ lặp lại
xuống con đó.

261
00:13:44,960 --> 00:13:49,330
>> Bây giờ, nếu đây không phải là vô giá trị để bắt đầu với,
sau đó con trỏ chỉ có thể lặp lại

262
00:13:49,330 --> 00:13:52,590
xuống con đó mà không thực sự
phải phân bổ bất cứ điều gì.

263
00:13:52,590 --> 00:13:56,730
Đây là trường hợp đầu tiên mà chúng tôi đã xảy ra
phân bổ từ "con mèo." Và

264
00:13:56,730 --> 00:14:00,330
đó có nghĩa là khi chúng tôi đi để phân bổ
"Thảm họa", chúng tôi không cần phải tạo ra

265
00:14:00,330 --> 00:14:01,680
các nút cho C-A-T một lần nữa.

266
00:14:01,680 --> 00:14:04,830
Họ đã tồn tại.

267
00:14:04,830 --> 00:14:06,080
>> Này khác là gì?

268
00:14:06,080 --> 00:14:10,480
Đây là điều kiện mà c là
dấu gạch chéo ngược n, trong đó c là một dòng mới.

269
00:14:10,480 --> 00:14:13,710
Điều này có nghĩa rằng chúng ta có thành công
hoàn thành một từ.

270
00:14:13,710 --> 00:14:16,860
Bây giờ những gì chúng tôi muốn làm khi chúng ta
Hoàn thành một từ?

271
00:14:16,860 --> 00:14:21,100
Chúng ta sẽ sử dụng trường từ này
bên trong của nút cấu trúc của chúng tôi.

272
00:14:21,100 --> 00:14:23,390
Chúng tôi muốn thiết lập đó là đúng sự thật.

273
00:14:23,390 --> 00:14:27,150
Vì vậy, đó chỉ ra rằng nút này
cho thấy một thành công

274
00:14:27,150 --> 00:14:29,250
từ, một từ thực tế.

275
00:14:29,250 --> 00:14:30,940
>> Bây giờ thiết lập đó là đúng sự thật.

276
00:14:30,940 --> 00:14:35,150
Chúng tôi muốn thiết lập lại con trỏ của chúng tôi đến thời điểm
để đầu Trie một lần nữa.

277
00:14:35,150 --> 00:14:40,160
Và cuối cùng, tăng từ điển của chúng tôi
kích thước, kể từ khi chúng tôi tìm được việc làm khác.

278
00:14:40,160 --> 00:14:43,230
Vì vậy, chúng tôi sẽ tiếp tục làm điều đó,
đọc trong nhân vật của nhân vật,

279
00:14:43,230 --> 00:14:49,150
xây dựng các nút mới trong Trie của chúng tôi và
cho mỗi từ trong từ điển, cho đến khi

280
00:14:49,150 --> 00:14:54,020
cuối cùng chúng ta đạt C! = EOF, trong đó
trường hợp chúng tôi thoát ra khỏi các tập tin.

281
00:14:54,020 --> 00:14:57,050
>> Hiện nay có hai trường hợp dưới
mà chúng tôi có thể nhấn kết thúc tập tin.

282
00:14:57,050 --> 00:15:00,980
Đầu tiên là nếu có một lỗi
đọc từ tập tin.

283
00:15:00,980 --> 00:15:03,470
Vì vậy, nếu có một lỗi, chúng tôi
cần phải làm điển hình.

284
00:15:03,470 --> 00:15:06,460
Dỡ bỏ tất cả mọi thứ, gần
các tập tin, trả về false.

285
00:15:06,460 --> 00:15:09,810
Giả sử không có lỗi, mà
chỉ có nghĩa là chúng tôi thực sự đánh cuối

286
00:15:09,810 --> 00:15:13,750
các tập tin, trong trường hợp đó, chúng tôi đóng cửa
nộp và trả lại đúng kể từ khi chúng tôi

287
00:15:13,750 --> 00:15:17,330
từ điển nạp thành công
vào Trie của chúng tôi.

288
00:15:17,330 --> 00:15:20,170
>> Vì vậy, bây giờ chúng ta hãy xem.

289
00:15:20,170 --> 00:15:25,156
Nhìn vào chức năng kiểm tra, chúng tôi thấy
kiểm tra có nghĩa là sẽ trả về một bool.

290
00:15:25,156 --> 00:15:29,680
Nó trả về true nếu từ này là nó
được thông qua là trong Trie của chúng tôi.

291
00:15:29,680 --> 00:15:32,110
Nó trả về false nếu không.

292
00:15:32,110 --> 00:15:36,050
Vì vậy, làm thế nào bạn xác định xem
từ này là trong Trie của chúng tôi?

293
00:15:36,050 --> 00:15:40,190
>> Chúng ta thấy ở đây, giống như trước đây,
chúng ta sẽ sử dụng con trỏ để lặp

294
00:15:40,190 --> 00:15:41,970
thông qua Trie của chúng tôi.

295
00:15:41,970 --> 00:15:46,600
Bây giờ đây chúng ta sẽ lặp
trên toàn bộ từ chúng tôi.

296
00:15:46,600 --> 00:15:50,620
Vì vậy, duyệt qua từ chúng tôi trong quá khứ,
chúng ta sẽ xác định

297
00:15:50,620 --> 00:15:56,400
chỉ số vào mảng trẻ em
tương ứng với khung chữ I. Vì vậy, đây

298
00:15:56,400 --> 00:15:59,670
sẽ trông giống hệt như
tải, mà nếu từ [i]

299
00:15:59,670 --> 00:16:03,310
là một dấu nháy đơn, sau đó chúng tôi muốn
sử dụng chỉ số "bảng chữ cái" - 1.

300
00:16:03,310 --> 00:16:05,350
Bởi vì chúng tôi xác định rằng
là nơi mà chúng ta sẽ lưu trữ

301
00:16:05,350 --> 00:16:07,100
dấu nháy.

302
00:16:07,100 --> 00:16:11,780
>> Khác chúng ta sẽ sử dụng hai từ thấp
khung I. Vì vậy, nhớ từ đó có thể

303
00:16:11,780 --> 00:16:13,920
có vốn hóa tùy ý.

304
00:16:13,920 --> 00:16:17,540
Và vì vậy chúng tôi muốn chắc chắn rằng chúng tôi
sử dụng một phiên bản chữ thường của sự vật.

305
00:16:17,540 --> 00:16:21,920
Và sau đó trừ đi từ đó 'a' một lần
một lần nữa cho chúng ta những chữ cái

306
00:16:21,920 --> 00:16:23,880
vị trí của nhân vật đó.

307
00:16:23,880 --> 00:16:27,680
Vì vậy, đó sẽ là chỉ số của chúng tôi
vào mảng trẻ em.

308
00:16:27,680 --> 00:16:32,420
>> Và bây giờ nếu chỉ số vào trẻ em
mảng là null, có nghĩa là chúng tôi

309
00:16:32,420 --> 00:16:34,990
không còn có thể tiếp tục iterating
xuống Trie của chúng tôi.

310
00:16:34,990 --> 00:16:38,870
Nếu đó là trường hợp, từ này có thể không
có thể là trong Trie của chúng tôi.

311
00:16:38,870 --> 00:16:42,340
Vì nếu nó được, mà có thể
có nghĩa là sẽ có một con đường

312
00:16:42,340 --> 00:16:43,510
xuống từ đó.

313
00:16:43,510 --> 00:16:45,290
Và bạn sẽ không bao giờ gặp phải null.

314
00:16:45,290 --> 00:16:47,850
Vì vậy, gặp phải vô giá trị, chúng tôi trả về false.

315
00:16:47,850 --> 00:16:49,840
Từ không có trong từ điển.

316
00:16:49,840 --> 00:16:53,660
Nếu nó không được null, sau đó chúng tôi
sẽ tiếp tục iterating.

317
00:16:53,660 --> 00:16:57,220
>> Vì vậy, chúng ta sẽ ra có con trỏ
để trỏ đến đó đặc biệt

318
00:16:57,220 --> 00:16:59,760
nút tại chỉ số đó.

319
00:16:59,760 --> 00:17:03,150
Chúng tôi tiếp tục làm điều đó trong suốt
toàn bộ văn bản, giả định

320
00:17:03,150 --> 00:17:03,950
chúng tôi không bao giờ đánh null.

321
00:17:03,950 --> 00:17:07,220
Điều đó có nghĩa chúng tôi có thể nhận được thông qua
toàn bộ văn bản và tìm thấy

322
00:17:07,220 --> 00:17:08,920
một nút trong thử của chúng tôi.

323
00:17:08,920 --> 00:17:10,770
Nhưng chúng tôi không hoàn toàn thực hiện được nêu ra.

324
00:17:10,770 --> 00:17:12,290
>> Chúng tôi không muốn chỉ trở thành sự thật.

325
00:17:12,290 --> 00:17:14,770
Chúng tôi muốn trở lại con trỏ> từ.

326
00:17:14,770 --> 00:17:18,980
Kể từ khi nhớ lại, là "con mèo" không
trong từ điển của chúng tôi, và "thảm họa"

327
00:17:18,980 --> 00:17:22,935
được, thì chúng ta sẽ thành công, chúng tôi có được
thông qua từ "con mèo." Nhưng con trỏ

328
00:17:22,935 --> 00:17:25,760
từ đó sẽ là sai lầm và không đúng sự thật.

329
00:17:25,760 --> 00:17:30,930
Vì vậy, chúng tôi trở lại từ con trỏ để chỉ
cho dù nút này thực sự là một lời.

330
00:17:30,930 --> 00:17:32,470
Và đó là nó để kiểm tra.

331
00:17:32,470 --> 00:17:34,250
>> Vì vậy, hãy kiểm tra kích thước.

332
00:17:34,250 --> 00:17:37,350
Vì vậy, kích thước sẽ là khá dễ dàng
Kể từ đó, nhớ trong tải, chúng tôi

333
00:17:37,350 --> 00:17:41,430
cách tăng kích thước từ điển cho
mỗi từ mà chúng ta gặp phải.

334
00:17:41,430 --> 00:17:45,350
Vì vậy, kích thước chỉ là sẽ
trở về kích thước từ điển.

335
00:17:45,350 --> 00:17:47,390
Và đó là nó.

336
00:17:47,390 --> 00:17:50,590
>> Vì vậy, cuối cùng chúng tôi đã dỡ bỏ.

337
00:17:50,590 --> 00:17:55,100
Vì vậy, dỡ bỏ, chúng ta sẽ sử dụng một
hàm đệ quy để thực sự làm tất cả

338
00:17:55,100 --> 00:17:56,530
các công việc cho chúng tôi.

339
00:17:56,530 --> 00:17:59,340
Vì vậy, chức năng của chúng tôi sẽ
được gọi là ngày không tải.

340
00:17:59,340 --> 00:18:01,650
Những gì đang không tải sẽ làm gì?

341
00:18:01,650 --> 00:18:06,580
Chúng ta thấy ở đây không tải có nghĩa là sẽ
lặp qua tất cả các trẻ em

342
00:18:06,580 --> 00:18:08,410
nút đặc biệt này.

343
00:18:08,410 --> 00:18:11,750
Và nếu nút con không phải là
null, sau đó chúng ta sẽ

344
00:18:11,750 --> 00:18:13,730
dỡ bỏ các nút con.

345
00:18:13,730 --> 00:18:18,010
>> Vì vậy, đây là bạn đệ quy dỡ bỏ
tất cả các trẻ em của chúng tôi.

346
00:18:18,010 --> 00:18:21,080
Một khi chúng tôi chắc chắn rằng tất cả các trẻ em của chúng tôi
đã được dỡ xuống, sau đó chúng tôi

347
00:18:21,080 --> 00:18:25,210
có thể giải phóng mình, vì vậy
dỡ bỏ bản thân mình.

348
00:18:25,210 --> 00:18:29,460
Điều này sẽ làm việc đệ quy
dỡ bỏ toàn bộ Trie.

349
00:18:29,460 --> 00:18:32,850
Và sau đó một khi đã xong,
chúng tôi chỉ có thể trở thành sự thật.

350
00:18:32,850 --> 00:18:34,210
Dỡ bỏ không thể thất bại.

351
00:18:34,210 --> 00:18:35,710
Chúng tôi chỉ giải phóng mọi thứ.

352
00:18:35,710 --> 00:18:38,870
Vì vậy, khi chúng tôi đang thực hiện giải phóng
tất cả mọi thứ, trở về đúng.

353
00:18:38,870 --> 00:18:40,320
Và đó là nó.

354
00:18:40,320 --> 00:18:41,080
Tên tôi là Rob.

355
00:18:41,080 --> 00:18:42,426
Và đây là Speller.

356
00:18:42,426 --> 00:18:47,830
>> [MUSIC CHƠI]