1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Hãy cho
giải pháp này một thử.

3
00:00:03,070 --> 00:00:07,130
Vì vậy, chúng ta hãy nhìn vào những gì chúng tôi
Nút cấu trúc sẽ như thế nào.

4
00:00:07,130 --> 00:00:11,040
Ở đây, chúng ta thấy chúng ta sẽ có một
Bool Word và một nút sao Struct

5
00:00:11,040 --> 00:00:12,990
Trẻ em trong ngoặc bảng chữ cái.

6
00:00:12,990 --> 00:00:18,720
Vì vậy, điều đầu tiên bạn có thể tự hỏi,
tại sao băm bảng chữ cái được xác định là 27?

7
00:00:18,720 --> 00:00:22,540
Vâng, hãy nhớ rằng chúng ta sẽ cần
được xử lý dấu nháy đơn, vì vậy

8
00:00:22,540 --> 00:00:25,610
đó là có được một chút của một đặc biệt
trường hợp trong suốt chương trình này.

9
00:00:25,610 --> 00:00:28,780
>> OK, bây giờ, nhớ làm thế nào một
Trie thực sự hoạt động.

10
00:00:28,780 --> 00:00:33,420
Hãy nói rằng chúng tôi đang lập chỉ mục những con mèo từ,
sau đó từ thư mục gốc của Trie của chúng tôi,

11
00:00:33,420 --> 00:00:36,670
chúng ta sẽ nhìn vào trẻ em
mảng, và chúng ta sẽ xem xét các

12
00:00:36,670 --> 00:00:42,250
chỉ số tương ứng với chữ cái
C. Vì vậy, đó sẽ là chỉ số hai.

13
00:00:42,250 --> 00:00:46,400
Vì vậy, cho rằng, sẽ cung cấp cho chúng tôi
một nút mới, và sau đó chúng tôi sẽ

14
00:00:46,400 --> 00:00:47,880
làm việc từ nút đó.

15
00:00:47,880 --> 00:00:51,830
>> 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,

16
00:00:51,830 --> 00:00:56,170
và chúng ta sẽ nhìn vào chỉ số không
tương ứng với một trong mèo.

17
00:00:56,170 --> 00:01:01,240
Vì vậy, sau đó chúng ta sẽ đi đến nút đó,
và cho nút đó, chúng ta sẽ

18
00:01:01,240 --> 00:01:05,170
nhìn vào các chỉ số tương ứng
T. Và chuyển sang nút đó,

19
00:01:05,170 --> 00:01:09,590
cuối cùng, chúng tôi đã hoàn toàn nhìn
thông qua của chúng tôi từ Cát, và bây giờ Bool

20
00:01:09,590 --> 00:01:15,020
Từ được cho là để cho biết
từ cho điều này thực sự là một từ.

21
00:01:15,020 --> 00:01:17,530
>> Vì vậy, tại sao chúng ta cần phải có trường hợp đặc biệt?

22
00:01:17,530 --> 00:01:21,680
Vâng, những gì nếu thảm họa từ
là trong từ điển của chúng tôi, nhưng

23
00:01:21,680 --> 00:01:24,120
con mèo từ không?

24
00:01:24,120 --> 00:01:29,030
Vì vậy, trong việc tìm kiếm để xem nếu con mèo từ là
trong từ điển của chúng tôi, chúng ta sẽ

25
00:01:29,030 --> 00:01:34,880
xem xét thành công thông qua các chỉ số
C-A-T và đạt được một nút, nhưng đó là

26
00:01:34,880 --> 00:01:39,760
chỉ vì thảm họa đã xảy ra với
tạo ra các nút trên đường từ C-A-T tất cả

27
00:01:39,760 --> 00:01:41,250
đường đến cuối từ.

28
00:01:41,250 --> 00:01:46,520
Vì vậy, Bool Word được sử dụng chỉ ra liệu
địa điểm cụ thể này thực sự

29
00:01:46,520 --> 00:01:48,370
chỉ một từ.

30
00:01:48,370 --> 00:01:52,920
>> Được rồi, vậy bây giờ chúng ta biết những gì một
Trie sẽ như thế nào, chúng ta hãy xem

31
00:01:52,920 --> 00:01:54,800
các chức năng Load.

32
00:01:54,800 --> 00:01:58,670
Vì vậy, tải sẽ trả về một Bool
cho dù chúng ta có thành công hay

33
00:01:58,670 --> 00:02:03,020
từ điển nhưng không thành công và nạp
này là có được từ điển

34
00:02:03,020 --> 00:02:04,520
mà chúng tôi muốn để tải.

35
00:02:04,520 --> 00:02:08,310
Điều đầu tiên để chúng ta sẽ làm là mở
up từ điển để đọc.

36
00:02:08,310 --> 00:02:12,060
Chúng ta phải chắc chắn rằng chúng tôi đã không thất bại,
vì vậy nếu từ điển không

37
00:02:12,060 --> 00:02:15,280
mở thành công, nó sẽ trở lại
Không, trong trường hợp này chúng ta sẽ

38
00:02:15,280 --> 00:02:16,340
trở về False.

39
00:02:16,340 --> 00:02:21,290
Nhưng giả định rằng nó thành công
mở ra, sau đó chúng tôi thực sự có thể đọc

40
00:02:21,290 --> 00:02:22,310
thông qua các từ điển.

41
00:02:22,310 --> 00:02:24,940
>> Điều đầu tiên để chúng ta sẽ
muốn làm là chúng tôi có điều này

42
00:02:24,940 --> 00:02:26,560
gốc biến toàn cầu.

43
00:02:26,560 --> 00:02:30,250
Bây giờ, gốc là có được một ngôi sao nút.

44
00:02:30,250 --> 00:02:33,830
Đó là đầu Trie của chúng tôi rằng chúng tôi
sẽ được lặp lại thông qua.

45
00:02:33,830 --> 00:02:38,200
Điều đầu tiên để chúng ta sẽ muốn
làm là cấp phát bộ nhớ cho người chủ của chúng tôi.

46
00:02:38,200 --> 00:02:42,040
>> Chú ý rằng chúng ta đang sử dụng calloc
chức năng, mà về cơ bản là giống nhau

47
00:02:42,040 --> 00:02:45,560
như chức năng malloc, ngoại trừ nó
đảm bảo để trở về cái gì đó là

48
00:02:45,560 --> 00:02:47,240
hoàn toàn zeroed ra.

49
00:02:47,240 --> 00:02:51,350
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

50
00:02:51,350 --> 00:02:54,220
nút và chắc chắn rằng
tất cả chúng null.

51
00:02:54,220 --> 00:02:56,780
Vì vậy, calloc sẽ làm điều đó cho chúng ta.

52
00:02:56,780 --> 00:03:00,390
>> Bây giờ, giống như malloc, chúng tôi cần phải thực hiện
đảm bảo rằng việc phân bổ thực sự

53
00:03:00,390 --> 00:03:01,580
thành công.

54
00:03:01,580 --> 00:03:04,060
Nếu điều này trở về null, sau đó chúng tôi
cần phải đóng từ điển của chúng tôi

55
00:03:04,060 --> 00:03:06,170
nộp và trả lại sai.

56
00:03:06,170 --> 00:03:11,040
Vì vậy, giả định việc phân bổ được
thành công, chúng ta sẽ sử dụng một nút

57
00:03:11,040 --> 00:03:14,340
sao con trỏ để lặp
thông qua Trie của chúng tôi.

58
00:03:14,340 --> 00:03:17,950
Vì vậy, chúng tôi gốc sẽ không bao giờ thay đổi,
nhưng chúng ta sẽ sử dụng con trỏ để

59
00:03:17,950 --> 00:03:20,770
thực sự đi từ nút đến nút.

60
00:03:20,770 --> 00:03:25,000
>> Được rồi, vậy trong này Đối với loop, chúng tôi
đọc qua các tập tin từ điển,

61
00:03:25,000 --> 00:03:26,965
và chúng tôi đang sử dụng tại fgetc.

62
00:03:26,965 --> 00:03:30,360
Vì vậy, fgetc sẽ lấy một đơn
nhân vật từ tập tin.

63
00:03:30,360 --> 00:03:33,430
Chúng tôi sẽ tiếp tục lấy
ký tự trong khi chúng tôi không đạt được

64
00:03:33,430 --> 00:03:37,540
kết thúc của tập tin, do đó,
hai trường hợp chúng ta cần phải xử lý.

65
00:03:37,540 --> 00:03:41,640
Đầu tiên, nếu nhân vật không phải là một
dòng mới, vì vậy chúng tôi biết nếu đó là một mới

66
00:03:41,640 --> 00:03:44,480
dòng, sau đó chúng tôi sắp sửa
chuyển sang một từ mới.

67
00:03:44,480 --> 00:03:49,300
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

68
00:03:49,300 --> 00:03:52,440
chỉ số chúng ta sẽ chỉ vào
trong mảng trẻ em mà

69
00:03:52,440 --> 00:03:53,890
chúng tôi xem xét trước.

70
00:03:53,890 --> 00:03:57,950
>> 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.

71
00:03:57,950 --> 00:04:01,040
Lưu ý chúng đang sử dụng nhà điều hành ternary
ở đây, vì vậy chúng ta sẽ đọc

72
00:04:01,040 --> 00:04:05,500
này là nếu nhân vật chúng ta đọc trong là
một dấu nháy đơn, sau đó chúng ta sẽ

73
00:04:05,500 --> 00:04:11,740
thiết lập chỉ mục bằng bảng chữ cái trừ
1, đó sẽ là chỉ số 26.

74
00:04:11,740 --> 00:04:15,190
Khác, nếu nó không phải là một dấu nháy đơn,
sau đó chúng ta sẽ thiết lập các chỉ số

75
00:04:15,190 --> 00:04:17,820
bằng c trừ đi một.

76
00:04:17,820 --> 00:04:23,090
Vì vậy, nhớ lại từ bộ p trước,
c trừ đi một sẽ cung cấp cho chúng tôi

77
00:04:23,090 --> 00:04:27,470
vị trí chữ cái của c, vì vậy nếu
c là chữ A, điều này sẽ

78
00:04:27,470 --> 00:04:28,770
cung cấp cho chúng tôi số không.

79
00:04:28,770 --> 00:04:32,180
Đối với chữ B, nó sẽ cung cấp cho
chúng tôi chỉ số 1, và như vậy.

80
00:04:32,180 --> 00:04:37,070
>> 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.

81
00:04:37,070 --> 00:04:42,540
Bây giờ, nếu chỉ số này hiện đang vô giá trị trong
mảng trẻ em, có nghĩa là

82
00:04:42,540 --> 00:04:47,470
một nút hiện không tồn tại từ
con đường đó, vì vậy chúng tôi cần phải phân bổ một

83
00:04:47,470 --> 00:04:49,220
nút cho con đường đó.

84
00:04:49,220 --> 00:04:50,610
Đó là những gì chúng tôi làm ở đây.

85
00:04:50,610 --> 00:04:54,650
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 có

86
00:04:54,650 --> 00:05:00,130
để không ra tất cả các con trỏ, và chúng tôi,
một lần nữa, cần phải kiểm tra calloc mà

87
00:05:00,130 --> 00:05:01,300
đã không thất bại.

88
00:05:01,300 --> 00:05:04,760
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

89
00:05:04,760 --> 00:05:06,880
từ điển, và trở về False.

90
00:05:06,880 --> 00:05:14,110
>> 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,

91
00:05:14,110 --> 00:05:16,000
và sau đó chúng ta sẽ đi đến đứa trẻ.

92
00:05:16,000 --> 00:05:19,030
Con trỏ của chúng tôi sẽ lặp lại
xuống con đó.

93
00:05:19,030 --> 00:05:23,390
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

94
00:05:23,390 --> 00:05:26,650
xuống con đó mà không thực sự
phải phân bổ bất cứ điều gì.

95
00:05:26,650 --> 00:05:30,790
Đây là trường hợp đầu tiên mà chúng tôi đã xảy ra
phân bổ mèo từ, và

96
00:05:30,790 --> 00:05:34,390
đó 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

97
00:05:34,390 --> 00:05:35,720
các nút cho C-A-T một lần nữa.

98
00:05:35,720 --> 00:05:37,620
Họ đã tồn tại.

99
00:05:37,620 --> 00:05:40,140
>> OK, vì vậy đây là những gì khác?

100
00:05:40,140 --> 00:05:44,600
Đâ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.

101
00:05:44,600 --> 00:05:47,780
Điều này có nghĩa rằng chúng ta có thành công
hoàn thành một từ.

102
00:05:47,780 --> 00:05:51,020
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ừ?

103
00:05:51,020 --> 00:05:55,250
Chúng ta sẽ sử dụng trường từ này
bên trong của nút Struct của chúng tôi.

104
00:05:55,250 --> 00:06:00,570
>> Chúng tôi muốn thiết lập đó là True, để
chỉ ra rằng nút này cho thấy một

105
00:06:00,570 --> 00:06:03,320
từ thành công một từ thực tế.

106
00:06:03,320 --> 00:06:05,050
Bây giờ, thiết lập đó là True.

107
00:06:05,050 --> 00:06:09,210
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.

108
00:06:09,210 --> 00:06:13,510
Và cuối cùng, tăng từ điển của chúng tôi
kích thước từ khi chúng tôi tìm thấy một từ khác.

109
00:06:13,510 --> 00:06:16,450
>> Được rồi, vậy chúng ta sẽ tiếp tục làm
rằng, đọc sách trong nhân vật của

110
00:06:16,450 --> 00:06:21,960
nhân vật, xây dựng các nút mới trong
Trie của chúng tôi và cho mỗi từ trong

111
00:06:21,960 --> 00:06:26,810
từ điển, cho đến khi cuối cùng chúng ta đạt c
bằng kết thúc tập tin, trong trường hợp này, chúng ta phá vỡ

112
00:06:26,810 --> 00:06:28,100
ra của tập tin.

113
00:06:28,100 --> 00:06:31,110
Bây giờ, có hai trường hợp dưới
mà chúng tôi có thể nhấn kết thúc tập tin.

114
00:06:31,110 --> 00:06:35,680
Đầu tiên là nếu có một lỗi
đọc từ tập tin, vì vậy nếu có

115
00:06:35,680 --> 00:06:39,280
một lỗi, chúng tôi cần phải làm những điển hình
dỡ bỏ tất cả mọi thứ, đóng tập tin,

116
00:06:39,280 --> 00:06:40,520
trở về False.

117
00:06:40,520 --> 00:06:43,870
Giả sử không có lỗi, mà
chỉ có nghĩa là chúng tôi thực sự đánh cuối

118
00:06:43,870 --> 00:06:47,820
các tập tin, trong trường hợp đó, chúng tôi đóng cửa
nộp và trở lại thật vì chúng ta

119
00:06:47,820 --> 00:06:51,010
nạp thành công từ điển
vào Trie của chúng tôi.

120
00:06:51,010 --> 00:06:54,240
>> Được rồi, vậy bây giờ chúng ta hãy
kiểm tra Kiểm tra.

121
00:06:54,240 --> 00:06:58,780
Nhìn vào Kiểm tra chức năng, chúng ta thấy
Kiểm tra có nghĩa là sẽ trả về một Bool.

122
00:06:58,780 --> 00:07:03,740
Nó trả về True nếu từ này là nó
được thông qua là trong Trie của chúng tôi.

123
00:07:03,740 --> 00:07:06,170
Nó trả về False khác.

124
00:07:06,170 --> 00:07:10,110
>> Vậy làm thế nào chúng ta sẽ xác định xem
từ này là trong Trie của chúng tôi?

125
00:07:10,110 --> 00:07:14,270
Chúng ta thấy ở đây, giống như trước đây,
chúng ta sẽ sử dụng con trỏ để lặp

126
00:07:14,270 --> 00:07:16,010
thông qua Trie của chúng tôi.

127
00:07:16,010 --> 00:07:20,650
Bây giờ, ở đây, chúng ta sẽ lặp
trên toàn bộ từ chúng tôi.

128
00:07:20,650 --> 00:07:24,680
Vì vậy, duyệt qua từ chúng tôi
trôi qua, chúng ta sẽ xác định

129
00:07:24,680 --> 00:07:29,280
chỉ số vào mảng trẻ em mà
tương ứng với khung từ tôi.

130
00:07:29,280 --> 00:07:34,150
Vì vậy, điều này sẽ trông giống hệt như
Tải, mà nếu khung từ tôi là một

131
00:07:34,150 --> 00:07:38,110
dấu nháy đơn, sau đó chúng tôi muốn sử dụng chỉ số
bảng chữ cái trừ 1 vì chúng tôi xác định

132
00:07:38,110 --> 00:07:41,160
đó là nơi mà chúng ta sẽ
để lưu trữ dấu nháy.

133
00:07:41,160 --> 00:07:44,440
>> Khác chúng ta sẽ sử dụng ToLower
khung từ tôi.

134
00:07:44,440 --> 00:07:48,270
Vì vậy, nhớ từ đó có thể có tùy ý
hoa, và vì vậy chúng tôi

135
00:07:48,270 --> 00:07:51,590
muốn chắc chắn rằng chúng ta đang sử dụng
một phiên bản chữ thường của sự vật.

136
00:07:51,590 --> 00:07:55,300
Và sau đó trừ đi từ chữ thường mà
một để, một lần nữa, cho chúng tôi

137
00:07:55,300 --> 00:07:57,940
vị trí chữ cái
của nhân vật đó.

138
00:07:57,940 --> 00:08:01,740
Vì vậy, đó sẽ là chỉ số của chúng tôi
vào mảng trẻ em.

139
00:08:01,740 --> 00:08:06,480
>> Và bây giờ, nếu chỉ số vào trẻ em
mảng là null, có nghĩa là chúng tôi

140
00:08:06,480 --> 00:08:09,050
không còn có thể tiếp tục iterating
xuống Trie của chúng tôi.

141
00:08:09,050 --> 00:08:13,320
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, vì nếu nó

142
00:08:13,320 --> 00:08:18,000
được, mà có nghĩa là sẽ có một
con đường xuống từ đó, và bạn sẽ

143
00:08:18,000 --> 00:08:19,350
không bao giờ gặp phải null.

144
00:08:19,350 --> 00:08:21,910
Vì vậy, gặp phải vô giá trị, chúng tôi trở lại Sai.

145
00:08:21,910 --> 00:08:23,810
Từ không có trong từ điển.

146
00:08:23,810 --> 00:08:28,200
Nếu nó không được null, sau đó chúng ta sẽ
tiếp tục iterating, vì vậy chúng ta sẽ

147
00:08:28,200 --> 00:08:33,150
để cập nhật con trỏ của chúng tôi để trỏ đến đó
nút cụ thể tại chỉ số đó.

148
00:08:33,150 --> 00:08:36,659
>> Vì vậy, chúng tôi tiếp tục làm điều đó trong suốt
toàn bộ từ.

149
00:08:36,659 --> 00:08:40,630
Giả sử chúng ta không bao giờ đánh null, mà phương tiện
chúng tôi có thể để có được thông qua toàn bộ

150
00:08:40,630 --> 00:08:44,840
thế giới và tìm thấy một nút trong Trie của chúng tôi,
nhưng chúng tôi không hoàn toàn thực hiện được nêu ra.

151
00:08:44,840 --> 00:08:46,350
Chúng tôi không muốn chỉ trả lại True.

152
00:08:46,350 --> 00:08:51,400
Chúng tôi muốn trở lại con trỏ từ lỗi
Kể từ đó, nhớ một lần nữa, nếu không phải là con mèo

153
00:08:51,400 --> 00:08:55,140
trong từ điển và thảm họa của chúng tôi là,
sau đó chúng tôi sẽ thành công có được thông qua

154
00:08:55,140 --> 00:08:59,810
con mèo từ, nhưng từ con trỏ
sẽ là sai và không thật.

155
00:08:59,810 --> 00:09:04,990
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 từ,

156
00:09:04,990 --> 00:09:06,530
và đó là nó để kiểm tra.

157
00:09:06,530 --> 00:09:08,310
>> Vì vậy, hãy kiểm tra kích thước.

158
00:09:08,310 --> 00:09:11,410
Vì vậy, Kích là có được khá dễ dàng
Kể từ đó, nhớ trong Load, chúng tôi

159
00:09:11,410 --> 00:09:15,480
cách tăng kích thước từ điển cho
mỗi từ mà chúng ta gặp phải.

160
00:09:15,480 --> 00:09:20,820
Vì vậy, Kích thước chỉ là sẽ quay trở lại
kích thước từ điển, và đó là nó.

161
00:09:20,820 --> 00:09:24,650
>> Được rồi, cuối cùng, chúng tôi có Unload.

162
00:09:24,650 --> 00:09:29,050
Vì vậy, Unload, chúng ta sẽ sử dụng một
hàm đệ quy để thực sự làm tất cả

163
00:09:29,050 --> 00:09:33,390
các công việc cho chúng tôi, vì vậy chức năng của chúng tôi
sẽ được gọi là dỡ.

164
00:09:33,390 --> 00:09:35,830
Dỡ là những gì sẽ làm gì?

165
00:09:35,830 --> 00:09:40,640
Chúng ta thấy ở đây dỡ có nghĩa là sẽ
lặp qua tất cả các trẻ em

166
00:09:40,640 --> 00:09:45,810
nút đặc biệt này, và nếu đứa trẻ
nút không phải là null, sau đó chúng ta sẽ

167
00:09:45,810 --> 00:09:47,760
dỡ bỏ các nút con.

168
00:09:47,760 --> 00:09:52,070
>> Vì vậy, điều này sẽ đệ quy
dỡ bỏ tất cả các trẻ em của chúng tôi.

169
00:09:52,070 --> 00:09:55,140
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

170
00:09:55,140 --> 00:09:58,830
có thể giải phóng mình, vì vậy dỡ bỏ ourself.

171
00:09:58,830 --> 00:10:04,550
Vì vậy, điều này đệ quy sẽ dỡ bỏ các
toàn bộ Trie, và sau đó một khi đó là

172
00:10:04,550 --> 00:10:06,910
thực hiện, chúng tôi chỉ có thể trở lại True.

173
00:10:06,910 --> 00:10:09,770
Dỡ bỏ không thể thất bại, chúng tôi
chỉ giải phóng mọi thứ.

174
00:10:09,770 --> 00:10:12,985
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ề thật.

175
00:10:12,985 --> 00:10:14,380
Và đó là nó.

176
00:10:14,380 --> 00:10:16,792
Tên tôi là Rob, và điều này
là [không nghe được].

177
00:10:16,792 --> 00:10:21,888