1
00:00:00,000 --> 00:00:09,700

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Hãy làm cho
kiểm tra chính tả.

3
00:00:12,140 --> 00:00:16,900
Nếu bạn mở speller.c, sau đó bạn sẽ thấy
rằng hầu hết các chức năng cho

4
00:00:16,900 --> 00:00:20,810
kiểm tra một tập tin văn bản với một
từ điển đã được thực hiện cho bạn.

5
00:00:20,810 --> 00:00:26,330
. / Speller, đi qua trong một văn bản từ điển
nộp và sau đó một tập tin văn bản,

6
00:00:26,330 --> 00:00:28,960
sẽ kiểm tra xem file văn bản
so với từ điển.

7
00:00:28,960 --> 00:00:34,160
>> Bây giờ, tập tin văn bản từ điển sẽ chứa
từ hợp lệ, mỗi dòng.

8
00:00:34,160 --> 00:00:37,910
Sau đó sẽ gọi speller.c tải
trên các tập tin văn bản từ điển.

9
00:00:37,910 --> 00:00:43,650
Nó sẽ gọi một chức năng được gọi là Kiểm tra
mỗi từ trong các tập tin văn bản đầu vào,

10
00:00:43,650 --> 00:00:46,460
in ấn tất cả các từ sai chính tả.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c cũng sẽ gọi Kích để
xác định số từ trong

12
00:00:50,030 --> 00:00:53,500
Từ điển và gọi Unload
để giải phóng bộ nhớ.

13
00:00:53,500 --> 00:00:57,600
speller.c cũng sẽ theo dõi như thế nào
nhiều thời gian được sử dụng để tiến hành các

14
00:00:57,600 --> 00:01:00,560
quy trình, nhưng chúng tôi sẽ
nhận được để mà sau.

15
00:01:00,560 --> 00:01:02,440
>> Vì vậy, những gì chúng ta cần phải làm gì?

16
00:01:02,440 --> 00:01:05,110
Chúng ta cần phải điền vào dictionary.c.

17
00:01:05,110 --> 00:01:09,940
Trong dictionary.c, chúng tôi có người giúp đỡ
chức năng Load, mà tải

18
00:01:09,940 --> 00:01:10,855
từ điển.

19
00:01:10,855 --> 00:01:15,490
Kiểm tra chức năng, trong đó kiểm tra nếu
một từ được đưa ra là trong từ điển.

20
00:01:15,490 --> 00:01:19,150
Chức năng Kích trả về số
các từ trong từ điển.

21
00:01:19,150 --> 00:01:24,870
Và cuối cùng, chúng tôi đã Dỡ bỏ, mà
giải phóng từ điển từ bộ nhớ.

22
00:01:24,870 --> 00:01:27,070
>> Vì vậy, đầu tiên, hãy giải quyết Load.

23
00:01:27,070 --> 00:01:32,110
Đối với mỗi từ trong văn bản từ điển
tập tin, tải sẽ lưu trữ những từ đó trong

24
00:01:32,110 --> 00:01:34,860
cấu trúc dữ liệu từ điển
lựa chọn của bạn, hoặc là một

25
00:01:34,860 --> 00:01:36,750
băm bảng hoặc một Trie.

26
00:01:36,750 --> 00:01:39,440
Tôi sẽ đi qua cả
này đi qua.

27
00:01:39,440 --> 00:01:43,150
>> Đầu tiên hãy nói về bảng băm.

28
00:01:43,150 --> 00:01:47,050
Giả sử bạn có 10 quả bóng bi-a và
bạn muốn để lưu trữ chúng.

29
00:01:47,050 --> 00:01:50,420
Bạn có thể đặt tất cả chúng trong một cái xô,
và khi bạn cần một người cụ thể

30
00:01:50,420 --> 00:01:54,010
số quả bóng, bạn sẽ mất một
ngoài những xô tại một thời điểm

31
00:01:54,010 --> 00:01:55,880
tìm kiếm quả bóng đó.

32
00:01:55,880 --> 00:01:59,370
Và chỉ có 10 quả bóng, bạn sẽ có
có thể tìm thấy bóng của bạn một cách hợp lý

33
00:01:59,370 --> 00:02:01,160
số lượng thời gian.

34
00:02:01,160 --> 00:02:03,180
>> Nhưng nếu bạn đã có 20 quả bóng?

35
00:02:03,180 --> 00:02:05,480
Nó có thể mất một ít lâu hơn bây giờ.

36
00:02:05,480 --> 00:02:06,180
Những gì về 100?

37
00:02:06,180 --> 00:02:07,880
1000?

38
00:02:07,880 --> 00:02:11,590
Bây giờ, nó sẽ dễ dàng hơn nhiều nếu
bạn có nhiều thùng.

39
00:02:11,590 --> 00:02:15,890
Có lẽ một xô cho bi số không
thông qua chín, một xô cho

40
00:02:15,890 --> 00:02:18,800
bi số 10 thông qua
19, và như vậy.

41
00:02:18,800 --> 00:02:22,330
>> Bây giờ khi bạn cần thiết để tìm kiếm cụ thể
bóng, bạn có thể tự động

42
00:02:22,330 --> 00:02:26,320
đi đến một xô cụ thể và
tìm kiếm thông qua thùng đó.

43
00:02:26,320 --> 00:02:29,840
Và nếu mỗi thùng có khoảng 10
quả bóng, sau đó bạn có thể dễ dàng tìm kiếm

44
00:02:29,840 --> 00:02:31,790
thông qua nó.

45
00:02:31,790 --> 00:02:34,960
>> Bây giờ, kể từ khi chúng tôi đang làm việc với
từ điển, một xô duy nhất cho

46
00:02:34,960 --> 00:02:41,970
tất cả các từ có trong từ điển sẽ
có lẽ là quá ít thùng.

47
00:02:41,970 --> 00:02:44,370
Vì vậy, chúng ta hãy nhìn vào bảng băm.

48
00:02:44,370 --> 00:02:46,940
>> Nghĩ về nó như một mảng xô.

49
00:02:46,940 --> 00:02:50,370
Và trong trường hợp này, xô
là danh sách liên kết của chúng tôi.

50
00:02:50,370 --> 00:02:54,770
Và chúng tôi sẽ phân phối tất cả các từ của chúng tôi
trong số các danh sách liên kết nhiều trong

51
00:02:54,770 --> 00:02:58,940
một cách có tổ chức sử dụng một hàm băm,
mà sẽ cho chúng tôi biết

52
00:02:58,940 --> 00:03:03,720
xô một khóa nhất định, một định
từ, thuộc về.

53
00:03:03,720 --> 00:03:05,960
>> Chúng ta hãy đại diện này đồ.

54
00:03:05,960 --> 00:03:11,320
Các ô màu xanh ở đây chứa các giá trị và
hộp màu đỏ trỏ đến giá trị khác

55
00:03:11,320 --> 00:03:12,280
cặp con trỏ.

56
00:03:12,280 --> 00:03:14,800
Chúng tôi sẽ gọi các nút cặp.

57
00:03:14,800 --> 00:03:18,260
Bây giờ, mỗi nhóm, như tôi đã nói
trước đó, là một danh sách liên kết.

58
00:03:18,260 --> 00:03:21,820
Trong danh sách liên kết, mỗi nút có giá trị,
cũng như một con trỏ đến

59
00:03:21,820 --> 00:03:23,170
giá trị tiếp theo.

60
00:03:23,170 --> 00:03:26,150
>> Bây giờ, đối phó với danh sách liên kết,
nó rất quan trọng là bạn

61
00:03:26,150 --> 00:03:28,120
không bị mất bất kỳ liên kết.

62
00:03:28,120 --> 00:03:32,250
Và một thực tế cần ghi nhớ là các
nút cuối cùng, nếu nó không trỏ đến

63
00:03:32,250 --> 00:03:35,120
một nút khác, chỉ để null.

64
00:03:35,120 --> 00:03:37,970
>> Vì vậy, làm thế nào để chúng tôi đại diện này trong C?

65
00:03:37,970 --> 00:03:40,540
Chúng tôi xác định cấu trúc của chúng tôi ở đây.

66
00:03:40,540 --> 00:03:44,850
Và giá trị trong trường hợp này là
một mảng char chiều dài.

67
00:03:44,850 --> 00:03:48,880
Chiều dài cộng với 1, nơi mà chiều dài là
Chiều dài tối đa của bất kỳ văn bản, cộng thêm 1 cho

68
00:03:48,880 --> 00:03:50,380
terminator null.

69
00:03:50,380 --> 00:03:54,210
Và sau đó chúng tôi có một con trỏ đến
một nút gọi là Next.

70
00:03:54,210 --> 00:03:56,730
>> Vì vậy, chúng ta hãy làm một danh sách liên kết nhỏ.

71
00:03:56,730 --> 00:04:00,390
Trước tiên, bạn sẽ muốn malloc nút của bạn,
mà tạo ra không gian trong bộ nhớ

72
00:04:00,390 --> 00:04:04,010
kích thước của loại nút của bạn.

73
00:04:04,010 --> 00:04:06,100
Và làm cho một nút khác,
một lần nữa mallocing.

74
00:04:06,100 --> 00:04:09,370

75
00:04:09,370 --> 00:04:14,340
>> Bây giờ nếu bạn muốn chỉ định một giá trị cho một
từ, sau đó chúng tôi có thể nói mũi tên node1

76
00:04:14,340 --> 00:04:18,820
từ bằng "Xin chào." Điều hành mũi tên này
dereferences con trỏ và

77
00:04:18,820 --> 00:04:20,620
truy cập các biến của cấu trúc.

78
00:04:20,620 --> 00:04:24,330
Bằng cách này, chúng ta không cần phải sử dụng cả hai
các dấu chấm và các nhà điều hành sao.

79
00:04:24,330 --> 00:04:30,100
>> Vì vậy, sau đó tôi có node2 mũi tên từ bằng
"Thế giới." Và ở đó, các giá trị

80
00:04:30,100 --> 00:04:33,110
dân cư trong các nút của tôi.

81
00:04:33,110 --> 00:04:38,780
Để làm cho các liên kết, tôi sẽ vượt qua trong node1
mũi tên bên cạnh, tiếp cận ngôi sao nút,

82
00:04:38,780 --> 00:04:44,160
rằng con trỏ nút, bằng node2,
chỉ node1 node2 để hai.

83
00:04:44,160 --> 00:04:46,360
Và chúng tôi đã có một danh sách liên kết.

84
00:04:46,360 --> 00:04:51,480
>> Vì vậy, đó chỉ là một danh sách liên kết, nhưng
một bảng băm là một mảng toàn bộ

85
00:04:51,480 --> 00:04:52,520
danh sách liên kết.

86
00:04:52,520 --> 00:04:55,920
Vâng, chúng ta sẽ có cùng một nút
cấu trúc như trước.

87
00:04:55,920 --> 00:05:00,140
Nhưng nếu chúng ta muốn có một bảng băm thực tế,
sau đó chúng tôi chỉ có thể làm cho một con trỏ nút

88
00:05:00,140 --> 00:05:01,330
mảng ở đây.

89
00:05:01,330 --> 00:05:04,940
Ví dụ, kích thước 500.

90
00:05:04,940 --> 00:05:08,910
>> Bây giờ thông báo, có sẽ là một thương mại
bằng giữa kích thước của bạn

91
00:05:08,910 --> 00:05:11,280
bảng băm và kích thước
của danh sách liên kết của bạn.

92
00:05:11,280 --> 00:05:15,640
Nếu bạn có một số thực sự cao
xô, tưởng tượng phải chạy trở lại

93
00:05:15,640 --> 00:05:18,230
và ra trong một dòng
tìm xô của bạn.

94
00:05:18,230 --> 00:05:21,530
Nhưng bạn cũng không muốn có một số lượng nhỏ
xô, bởi vì sau đó chúng tôi trở lại

95
00:05:21,530 --> 00:05:26,850
vấn đề ban đầu như thế nào có
quá nhiều quả bóng trong xô của chúng tôi.

96
00:05:26,850 --> 00:05:30,480
>> OK, nhưng nơi nào bóng của chúng tôi đi đâu?

97
00:05:30,480 --> 00:05:33,150
Vâng, đầu tiên chúng ta cần phải
có một quả bóng, phải không?

98
00:05:33,150 --> 00:05:39,130
Vì vậy, hãy malloc một nút cho mỗi
từ mới mà chúng ta có.

99
00:05:39,130 --> 00:05:42,900
nút * new_node bình đẳng
malloc (sizeof (node)).

100
00:05:42,900 --> 00:05:46,760
>> Bây giờ chúng ta có cấu trúc này, chúng tôi
có thể quét trong, bằng cách sử dụng chức năng

101
00:05:46,760 --> 00:05:51,850
fscanf, một chuỗi từ tập tin của chúng tôi, nếu
đó là một tập tin từ điển, vào

102
00:05:51,850 --> 00:05:55,780
new_node mũi tên từ nơi new_node
từ mũi tên là của chúng tôi

103
00:05:55,780 --> 00:05:58,110
điểm đến của từ đó.

104
00:05:58,110 --> 00:06:01,900
>> Tiếp theo, chúng ta sẽ muốn băm mà
từ sử dụng một hàm băm.

105
00:06:01,900 --> 00:06:05,860
Một hàm băm phải mất một chuỗi
và trả về một chỉ số.

106
00:06:05,860 --> 00:06:09,760
Trong trường hợp này, chỉ số này có đến
ít hơn số lượng

107
00:06:09,760 --> 00:06:11,440
xô mà bạn có.

108
00:06:11,440 --> 00:06:14,600
>> Bây giờ, hàm băm, khi bạn đang cố gắng
để tìm kiếm và tạo ra một trong

109
00:06:14,600 --> 00:06:17,890
của riêng bạn, hãy nhớ rằng họ
phải xác định.

110
00:06:17,890 --> 00:06:22,420
Điều đó có nghĩa rằng cùng một giá trị cần
bản đồ để xô giống nhau mỗi lần

111
00:06:22,420 --> 00:06:23,800
mà bạn băm nó.

112
00:06:23,800 --> 00:06:25,300
>> Nó giống như một thư viện.

113
00:06:25,300 --> 00:06:28,560
Khi bạn có một cuốn sách, dựa trên
tác giả, bạn biết được thời hạn sử dụng là cần

114
00:06:28,560 --> 00:06:31,890
đi vào, cho dù đó là số kệ
một, hai, hoặc ba.

115
00:06:31,890 --> 00:06:36,280
Và cuốn sách đó sẽ luôn luôn thuộc về
hoặc kệ một, hai, hoặc ba.

116
00:06:36,280 --> 00:06:39,460

117
00:06:39,460 --> 00:06:43,810
>> Vì vậy, nếu new_node mũi tên từ có
từ từ từ điển của bạn, sau đó

118
00:06:43,810 --> 00:06:47,770
băm new_node mũi tên từ sẽ
cho chúng ta những chỉ số của

119
00:06:47,770 --> 00:06:49,370
xô bảng băm.

120
00:06:49,370 --> 00:06:54,040
Và sau đó chúng tôi sẽ chèn vào đó mà
danh sách liên kết cụ thể chỉ định bởi các

121
00:06:54,040 --> 00:06:56,060
giá trị của hàm băm của chúng tôi trở lại.

122
00:06:56,060 --> 00:06:59,070
>> Hãy xem xét một ví dụ về
chèn một nút vào

123
00:06:59,070 --> 00:07:01,750
bắt đầu của một danh sách liên kết.

124
00:07:01,750 --> 00:07:06,930
Nếu người đứng đầu là một con trỏ nút cho biết
khởi đầu của một liên kết

125
00:07:06,930 --> 00:07:12,420
danh sách, và new_node cho biết mới
nút mà bạn muốn nhập vào, chỉ cần

126
00:07:12,420 --> 00:07:17,340
giao đầu đến new_node sẽ mất
các liên kết đến các phần còn lại của danh sách.

127
00:07:17,340 --> 00:07:19,330
Vì vậy, chúng tôi không muốn làm điều này.

128
00:07:19,330 --> 00:07:22,160
>> Thay vào đó, chúng tôi muốn chắc chắn
rằng chúng ta giữ cho mỗi

129
00:07:22,160 --> 00:07:23,550
nút duy nhất trong chương trình của chúng tôi.

130
00:07:23,550 --> 00:07:29,560
Vì vậy, chạy new_node mũi tên ngang hàng tiếp theo
đầu và sau đó đầu bằng new_node

131
00:07:29,560 --> 00:07:34,470
sẽ bảo vệ tất cả các
liên kết và không mất bất kỳ.

132
00:07:34,470 --> 00:07:39,330
>> Nhưng nếu bạn muốn danh sách của bạn được
sắp xếp, bởi vì có một sắp xếp liên kết

133
00:07:39,330 --> 00:07:42,910
danh sách có thể được dễ dàng hơn cho
tìm kiếm nó sau này?

134
00:07:42,910 --> 00:07:46,020
Vâng, cho rằng, bạn sẽ cần phải biết
làm thế nào để đi qua danh sách liên kết.

135
00:07:46,020 --> 00:07:51,210
>> Đi qua một danh sách liên kết, chúng ta hãy có
một con trỏ nút, một nút *, làm

136
00:07:51,210 --> 00:07:54,120
con trỏ của bạn, cho thấy đó
nút bạn đang ở, bắt đầu

137
00:07:54,120 --> 00:07:55,460
ở phần tử đầu tiên.

138
00:07:55,460 --> 00:08:01,070
Vòng lặp cho đến khi con trỏ là null, chúng ta có thể
tiến hành quy trình nhất định và sau đó

139
00:08:01,070 --> 00:08:04,330
thúc đẩy con trỏ khi chúng ta cần
sử dụng con trỏ giá trị mũi tên.

140
00:08:04,330 --> 00:08:08,820
>> Hãy nhớ rằng, đây là điều tương tự như
nói con trỏ sao, dereferencing

141
00:08:08,820 --> 00:08:13,480
con trỏ, sau đó sử dụng
giá trị dấu chấm.

142
00:08:13,480 --> 00:08:19,000
Để cập nhật con trỏ bằng cách gán
con trỏ đến con trỏ mũi tên bên cạnh.

143
00:08:19,000 --> 00:08:24,960
>> Giả sử bạn xác định rằng D sẽ trở thành trong
giữa C và E. Để chèn các nút,

144
00:08:24,960 --> 00:08:30,030
có điểm D new_node đến
nút E, đó là con trỏ tới.

145
00:08:30,030 --> 00:08:36,409
Và sau đó C, con trỏ, có thể sau đó điểm
D. Bằng cách đó, bạn duy trì một danh sách.

146
00:08:36,409 --> 00:08:41,080
Hãy cẩn thận không để mất liên kết của bạn bằng cách
di chuyển mũi tên trỏ bên cạnh D

147
00:08:41,080 --> 00:08:43,929
ngay lập tức.

148
00:08:43,929 --> 00:08:44,620
>> Được rồi.

149
00:08:44,620 --> 00:08:48,920
Vì vậy, đó là cách bạn có thể chèn các nút,
tải chúng trong, từ tải vào những

150
00:08:48,920 --> 00:08:51,600
các nút, và chèn chúng
vào bảng băm của bạn.

151
00:08:51,600 --> 00:08:53,580
Vì vậy, bây giờ chúng ta hãy nhìn vào cố gắng.

152
00:08:53,580 --> 00:08:58,540
>> Trong một Trie, mỗi nút sẽ chứa một
mảng của con trỏ nút, một cho mỗi

153
00:08:58,540 --> 00:09:02,260
thư trong bảng chữ cái
cộng với một dấu nháy đơn.

154
00:09:02,260 --> 00:09:06,150
Và mỗi phần tử trong mảng
sẽ trỏ đến một nút khác.

155
00:09:06,150 --> 00:09:10,130
Nếu nút đó là vô giá trị, sau đó lá thư
sẽ không được thư tiếp theo của

156
00:09:10,130 --> 00:09:15,690
bất kỳ từ nào trong một chuỗi, bởi vì mỗi
từ chỉ ra cho dù đó là người cuối cùng

157
00:09:15,690 --> 00:09:18,160
nhân vật của một từ hay không.

158
00:09:18,160 --> 00:09:19,750
>> Hãy nhìn vào một sơ đồ.

159
00:09:19,750 --> 00:09:22,260
Hy vọng rằng những điều sẽ
là một chút rõ ràng hơn.

160
00:09:22,260 --> 00:09:27,210
Trong sơ đồ này, chúng ta thấy rằng chỉ
một số chữ cái và chuỗi con nhất định

161
00:09:27,210 --> 00:09:28,190
đang được liệt kê ra.

162
00:09:28,190 --> 00:09:32,500
Vì vậy, bạn có thể làm theo những con đường nhất định, và
tất cả những con đường sẽ dẫn bạn đến

163
00:09:32,500 --> 00:09:34,020
Nói cách khác nhau.

164
00:09:34,020 --> 00:09:37,630
>> Vì vậy, làm thế nào để chúng tôi đại diện này trong C?

165
00:09:37,630 --> 00:09:41,910
Vâng, tất cả các nút bây giờ là sẽ có
một giá trị logic Boolean cho biết

166
00:09:41,910 --> 00:09:46,580
nút đó là kết thúc của
một từ được hay không.

167
00:09:46,580 --> 00:09:50,690
Và sau đó nó cũng sẽ có một loạt các
con trỏ nút được gọi là trẻ em, và

168
00:09:50,690 --> 00:09:53,440
có đang có được 27 trong số họ.

169
00:09:53,440 --> 00:09:56,510
Và hãy nhớ, bạn cũng sẽ muốn
theo dõi các nút đầu tiên của bạn.

170
00:09:56,510 --> 00:09:59,830
Chúng ta sẽ gọi gốc mà.

171
00:09:59,830 --> 00:10:01,690
>> Vì vậy, đó là cấu trúc của một Trie.

172
00:10:01,690 --> 00:10:05,630
Làm thế nào để chúng tôi đại diện này
như một từ điển?

173
00:10:05,630 --> 00:10:09,890
Vâng, để tải từ trong, cho mỗi
từ trong từ điển, bạn sẽ muốn

174
00:10:09,890 --> 00:10:11,960
để lặp qua các Trie.

175
00:10:11,960 --> 00:10:16,170
Và mỗi phần tử trong trẻ em
tương ứng với một thư khác nhau.

176
00:10:16,170 --> 00:10:21,660
>> Vì vậy, kiểm tra giá trị ở trẻ em
chỉ số i, nơi mà tôi đại diện cho

177
00:10:21,660 --> 00:10:24,840
chỉ số cụ thể của bức thư
bạn đang cố gắng để chèn.

178
00:10:24,840 --> 00:10:28,980
Vâng, nếu đó là vô giá trị, sau đó bạn sẽ muốn
malloc một nút mới và có con

179
00:10:28,980 --> 00:10:31,110
i trỏ đến nút đó.

180
00:10:31,110 --> 00:10:35,630
>> Nếu nó không phải là vô giá trị, thì đó có nghĩa là
mà ngành đưa ra, mà được

181
00:10:35,630 --> 00:10:37,350
chuỗi con, đã tồn tại.

182
00:10:37,350 --> 00:10:40,160
Vì vậy, sau đó bạn sẽ chỉ di chuyển đến
nút mới và tiếp tục.

183
00:10:40,160 --> 00:10:43,220
Nếu bạn đang ở cuối của từ đó
bạn đang cố gắng để tải trong

184
00:10:43,220 --> 00:10:48,120
từ điển, sau đó bạn có thể thiết lập mà
nút hiện tại mà bạn đang ở trên là đúng sự thật.

185
00:10:48,120 --> 00:10:51,550
>> Vì vậy, chúng ta hãy xem một ví dụ về chèn
từ "con cáo" thành của chúng tôi

186
00:10:51,550 --> 00:10:53,070
từ điển.

187
00:10:53,070 --> 00:10:56,110
Giả vờ chúng tôi bắt đầu với
một từ điển rỗng.

188
00:10:56,110 --> 00:11:01,610
Chữ cái đầu tiên, F, sẽ được đặt
ở trẻ em chỉ số năm của các gốc

189
00:11:01,610 --> 00:11:03,700
trẻ em mảng.

190
00:11:03,700 --> 00:11:05,430
Vì vậy, chúng ta chèn rằng in

191
00:11:05,430 --> 00:11:14,610
>> Chữ O sau đó sẽ là ở trẻ em
chỉ số 15, sau đó F. Và sau đó X

192
00:11:14,610 --> 00:11:20,180
sẽ còn thấp hơn, phân nhánh
tắt của trẻ em của O.

193
00:11:20,180 --> 00:11:24,120
Và sau đó bởi vì X là ký tự cuối cùng
của từ "con cáo", sau đó tôi sẽ

194
00:11:24,120 --> 00:11:27,210
màu xanh để chỉ ra rằng
đó là cuối từ.

195
00:11:27,210 --> 00:11:32,880
Trong C, mà có thể được thiết lập Is
Từ Boolean với giá trị thực.

196
00:11:32,880 --> 00:11:36,780
>> Bây giờ những gì nếu từ tiếp theo mà bạn
tải trong là từ "foo"?

197
00:11:36,780 --> 00:11:41,490
Vâng, bạn không cần phải malloc nữa
không gian cho F hoặc O, bởi vì

198
00:11:41,490 --> 00:11:42,990
những người đã tồn tại.

199
00:11:42,990 --> 00:11:45,910
Nhưng cuối cùng O trong foo?

200
00:11:45,910 --> 00:11:47,320
Một trong đó, bạn sẽ phải malloc.

201
00:11:47,320 --> 00:11:52,390
Làm cho một nút mới cho rằng, thiết lập
các Is Lời Boolean true.

202
00:11:52,390 --> 00:11:57,340
>> Vì vậy, bây giờ chúng ta hãy chèn "con chó". Con chó sẽ
bắt đầu với chỉ số ba của các gốc

203
00:11:57,340 --> 00:12:00,520
trẻ em, bởi vì D có không
được tạo ra chưa.

204
00:12:00,520 --> 00:12:04,990
Và chúng tôi sẽ theo một quy trình tương tự như
trước đây, tạo ra con chó chuỗi,

205
00:12:04,990 --> 00:12:10,400
nơi của G là màu xanh vì
đó là kết thúc của một từ.

206
00:12:10,400 --> 00:12:13,160
>> Bây giờ, nếu chúng ta muốn chèn "làm"?

207
00:12:13,160 --> 00:12:17,150
Vâng, đây là một chuỗi con của con chó, vì vậy
chúng tôi không cần phải malloc nữa.

208
00:12:17,150 --> 00:12:20,800
Nhưng chúng tôi cần phải chỉ ra nơi chúng tôi đã
đến cuối của từ đó.

209
00:12:20,800 --> 00:12:24,020
Vì vậy, các O sẽ được tô màu xanh lá cây.

210
00:12:24,020 --> 00:12:27,810
Tiếp tục quá trình cho mỗi đơn
từ trong từ điển của bạn, bạn đã

211
00:12:27,810 --> 00:12:32,120
nạp chúng vào một trong hai của bạn
băm bảng hoặc Trie của bạn.

212
00:12:32,120 --> 00:12:37,530
>> speller.c sẽ vượt qua trong chuỗi cho
dictionary.c để kiểm tra xem chúng.

213
00:12:37,530 --> 00:12:41,140
Bây giờ, Kiểm tra chức năng có hoạt động
dưới trường hợp vô cảm.

214
00:12:41,140 --> 00:12:45,980
Điều đó có nghĩa rằng chữ in hoa và
chữ thường và một kết hợp của cả hai

215
00:12:45,980 --> 00:12:50,670
tất cả phải tương đương với sự thật nếu có
sự kết hợp của đó là trong

216
00:12:50,670 --> 00:12:51,880
từ điển.

217
00:12:51,880 --> 00:12:55,580
Bạn cũng có thể giả định rằng dây là
sẽ chỉ chứa chữ cái

218
00:12:55,580 --> 00:12:58,200
ký tự hoặc dấu nháy.

219
00:12:58,200 --> 00:13:02,490
>> Vì vậy, chúng ta hãy xem làm thế nào bạn có thể kiểm tra
với một cấu trúc bảng băm.

220
00:13:02,490 --> 00:13:07,330
Vâng, nếu từ tồn tại, sau đó nó
có thể được tìm thấy trong bảng băm.

221
00:13:07,330 --> 00:13:12,240
Vì vậy, sau đó bạn có thể thử để thấy rằng
từ trong xô có liên quan.

222
00:13:12,240 --> 00:13:14,480
>> Vì vậy, mà xô sẽ từ đó được?

223
00:13:14,480 --> 00:13:20,060
Vâng, bạn sẽ nhận được số lượng, chỉ số
các xô, bằng cách băm từ đó

224
00:13:20,060 --> 00:13:23,690
và sau đó tìm kiếm trong danh sách liên kết mà,
đi ngang qua toàn bộ

225
00:13:23,690 --> 00:13:28,060
danh sách liên kết, sử dụng String
So sánh chức năng.

226
00:13:28,060 --> 00:13:31,940
>> Nếu kết thúc của danh sách liên kết là
đạt, có nghĩa là con trỏ của bạn

227
00:13:31,940 --> 00:13:36,030
đạt null, sau đó từ không phải là
được tìm thấy trong từ điển.

228
00:13:36,030 --> 00:13:39,090
Nó sẽ không được ở bất kỳ thùng khác.

229
00:13:39,090 --> 00:13:43,020
Vì vậy, ở đây, bạn có thể xem như thế nào có thể có
là một thương mại-off giữa có hoặc

230
00:13:43,020 --> 00:13:46,280
danh sách liên kết được sắp xếp hoặc những người được phân loại.

231
00:13:46,280 --> 00:13:51,180
Hoặc sẽ mất thời gian nhiều hơn trong
tải hoặc thêm thời gian trong quá trình kiểm tra.

232
00:13:51,180 --> 00:13:53,560
>> Làm thế nào bạn có thể kiểm tra trong
một cấu trúc Trie?

233
00:13:53,560 --> 00:13:56,370
Chúng ta sẽ đi xuống
trong Trie.

234
00:13:56,370 --> 00:14:00,390
Cho mỗi chữ cái trong từ đầu vào
mà chúng tôi đang kiểm tra, chúng tôi sẽ đi đến đó

235
00:14:00,390 --> 00:14:03,280
tương ứng với phần tử trong trẻ em.

236
00:14:03,280 --> 00:14:07,770
>> Nếu yếu tố đó là vô giá trị, sau đó phương tiện
rằng không có chuỗi con

237
00:14:07,770 --> 00:14:11,110
có chứa từ đầu vào của chúng tôi, vì vậy
từ viết sai chính tả.

238
00:14:11,110 --> 00:14:15,140
Nếu nó không phải là vô giá trị, chúng ta có thể di chuyển đến
thư từ tiếp theo mà chúng tôi

239
00:14:15,140 --> 00:14:18,850
kiểm tra và tiếp tục quá trình này
cho đến khi chúng tôi đạt được kết thúc

240
00:14:18,850 --> 00:14:20,350
của từ đầu vào.

241
00:14:20,350 --> 00:14:23,330
Và sau đó chúng tôi có thể kiểm tra
nếu Is Word là sự thật.

242
00:14:23,330 --> 00:14:24,610
Nếu có, sau đó tuyệt vời.

243
00:14:24,610 --> 00:14:25,590
Từ chính xác.

244
00:14:25,590 --> 00:14:30,890
Nhưng nếu không, mặc dù chuỗi đó
tồn tại trong Trie, từ đó

245
00:14:30,890 --> 00:14:32,250
sai chính tả.

246
00:14:32,250 --> 00:14:36,590
>> Khi chức năng Kích thước được gọi là, kích thước
nên trả lại số lượng từ mà

247
00:14:36,590 --> 00:14:39,110
là trong từ điển cho bạn
cấu trúc dữ liệu.

248
00:14:39,110 --> 00:14:42,780
Vì vậy, nếu bạn đang sử dụng một bảng băm, bạn
có thể đi qua tất cả các đơn

249
00:14:42,780 --> 00:14:45,860
danh sách liên kết trong mỗi đơn
xô đếm số

250
00:14:45,860 --> 00:14:47,130
các từ ở đó.

251
00:14:47,130 --> 00:14:49,940
Nếu bạn đang sử dụng một Trie, bạn có thể
đi qua tất cả không vô

252
00:14:49,940 --> 00:14:52,030
đường dẫn trong Trie của bạn.

253
00:14:52,030 --> 00:14:56,420
Hoặc trong khi bạn đang tải từ điển
trong, có thể bạn có thể theo dõi như thế nào

254
00:14:56,420 --> 00:14:58,760
nhiều từ bạn đang tải nhập

255
00:14:58,760 --> 00:15:03,180
>> Sau khi kết thúc kiểm tra speller.c
tập tin văn bản với từ điển, sau đó

256
00:15:03,180 --> 00:15:08,010
nó được thực hiện và do đó, nó gọi Unload, nơi
công việc của bạn là để giải phóng bất cứ điều gì

257
00:15:08,010 --> 00:15:09,500
mà bạn đã malloced.

258
00:15:09,500 --> 00:15:14,420
Vì vậy, nếu bạn sử dụng một bảng băm, sau đó bạn
cần phải đặc biệt cẩn thận để tránh

259
00:15:14,420 --> 00:15:18,830
rò rỉ bộ nhớ bằng cách không giải phóng bất cứ điều gì
sớm và nắm giữ tất cả

260
00:15:18,830 --> 00:15:20,780
liên kết duy nhất trước khi bạn miễn phí.

261
00:15:20,780 --> 00:15:24,680

262
00:15:24,680 --> 00:15:30,100
>> Vì vậy, cho mọi phần tử trong bảng băm
và cho tất cả các nút trong danh sách liên kết,

263
00:15:30,100 --> 00:15:32,370
bạn sẽ muốn giải phóng nút đó.

264
00:15:32,370 --> 00:15:34,970
Làm thế nào để bạn đi về giải phóng
một danh sách liên kết?

265
00:15:34,970 --> 00:15:38,570
Thiết lập nút của bạn con trỏ trỏ đến
người đứng đầu, với sự khởi đầu của

266
00:15:38,570 --> 00:15:43,100
danh sách liên kết, sau đó trong khi con trỏ của bạn
không phải là vô giá trị, bạn có thể đặt tạm thời

267
00:15:43,100 --> 00:15:45,610
nút con trỏ đến con trỏ của bạn.

268
00:15:45,610 --> 00:15:48,370
Sau đó tiến con trỏ.

269
00:15:48,370 --> 00:15:52,950
Và sau đó bạn có thể tự do mà tạm thời
giá trị trong khi vẫn giữ trên để

270
00:15:52,950 --> 00:15:55,650
tất cả mọi thứ sau đó.

271
00:15:55,650 --> 00:15:57,800
>> Nếu bạn đang sử dụng một Trie?

272
00:15:57,800 --> 00:16:00,410
Sau đó, cách tốt nhất để làm điều này
là dỡ bỏ từ rất

273
00:16:00,410 --> 00:16:02,290
dưới lên trên.

274
00:16:02,290 --> 00:16:06,920
Bằng cách đi xuống mức thấp nhất có thể
nút, bạn có thể tự do tất cả các con trỏ trong

275
00:16:06,920 --> 00:16:11,430
rằng trẻ em và sau đó quay lại
trở lên, giải phóng tất cả các yếu tố trong tất cả

276
00:16:11,430 --> 00:16:15,610
của trẻ em mảng, cho đến khi
bạn nhấn nút gốc hàng đầu của bạn.

277
00:16:15,610 --> 00:16:18,920
Đây là nơi Đệ quy
sẽ có ích.

278
00:16:18,920 --> 00:16:22,780
>> Để đảm bảo rằng bạn đã có thể giải thoát
tất cả mọi thứ mà bạn đã malloced,

279
00:16:22,780 --> 00:16:24,400
bạn có thể sử dụng Valgrind.

280
00:16:24,400 --> 00:16:28,640
Chạy Valgrind sẽ chạy chương trình của bạn
đếm bao nhiêu byte bộ nhớ

281
00:16:28,640 --> 00:16:32,440
bạn đang sử dụng và đảm bảo rằng bạn đã
giải thoát tất cả, nói cho bạn

282
00:16:32,440 --> 00:16:34,530
nơi bạn có thể có
quên miễn phí.

283
00:16:34,530 --> 00:16:38,390
Vì vậy, chạy đó và một lần Valgrind cho bạn
và cung cấp cho bạn đi trước, sau đó

284
00:16:38,390 --> 00:16:41,160
bạn đã hoàn tất dỡ bỏ.

285
00:16:41,160 --> 00:16:44,420
>> Bây giờ, một vài lời khuyên trước khi bạn đi
ra và bắt đầu thực hiện của bạn

286
00:16:44,420 --> 00:16:46,260
từ điển.

287
00:16:46,260 --> 00:16:49,650
Tôi muốn khuyên bạn nên để vượt qua trong một nhỏ hơn
từ điển khi bạn đang cố gắng để kiểm tra

288
00:16:49,650 --> 00:16:52,620
những điều trên và gỡ lỗi với GDP.

289
00:16:52,620 --> 00:16:58,550
Việc sử dụng Speller là. / Speller, một
từ điển tùy chọn, và sau đó là một văn bản.

290
00:16:58,550 --> 00:17:01,550
>> Theo mặc định, nó tải trong
từ điển lớn.

291
00:17:01,550 --> 00:17:06,670
Vì vậy, bạn có thể muốn vượt qua trong nhỏ
từ điển, hoặc thậm chí có thể làm cho bạn

292
00:17:06,670 --> 00:17:11,819
riêng, tùy biến từ điển của bạn
và tập tin văn bản của bạn.

293
00:17:11,819 --> 00:17:15,950
>> Và cuối cùng, tôi cũng khuyên bạn nên
để có một cây bút và giấy và vẽ

294
00:17:15,950 --> 00:17:20,490
những điều trên trước, trong, và sau khi
bạn đã viết tất cả các mã của bạn.

295
00:17:20,490 --> 00:17:24,170
Chỉ cần chắc chắn rằng bạn đã có
những con trỏ vừa phải.

296
00:17:24,170 --> 00:17:26,480
>> Tôi muốn bạn tốt nhất của may mắn.

297
00:17:26,480 --> 00:17:29,690
Và một khi bạn đã hoàn tất, nếu bạn muốn
để thách thức các tàu lớn và

298
00:17:29,690 --> 00:17:34,390
xem cách nhanh chóng chương trình của bạn được so sánh với
bạn cùng lớp của bạn, sau đó tôi khuyến khích

299
00:17:34,390 --> 00:17:35,960
bạn kiểm tra mà ra.

300
00:17:35,960 --> 00:17:39,220
>> Cùng với đó, bạn đã hoàn tất
các PSet Speller.

301
00:17:39,220 --> 00:17:41,800
Tên tôi là Zamyla, và đây là CS50.

302
00:17:41,800 --> 00:17:49,504