1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Vấn đề Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Đại học Harvard]

3
00:00:04,870 --> 00:00:07,190
[Đây là CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Được rồi. Xin chào, tất cả mọi người, và được chào đón để Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 là Lỗi chính tả, trong đó chúng ta sẽ được thực hiện một kiểm tra chính tả.

6
00:00:17,400 --> 00:00:21,030
Chính tả cờ là cực kỳ quan trọng.

7
00:00:21,030 --> 00:00:23,390
Này đã từng xảy ra với bạn?

8
00:00:23,390 --> 00:00:27,170
Bạn làm việc rất, rất tích trữ trên một tờ giấy cho một cuộc đụng độ

9
00:00:27,170 --> 00:00:33,120
và sau đó vẫn sẽ nhận được một Rade ánh sáng rất giống như một D hoặc a = D

10
00:00:33,120 --> 00:00:39,390
và tất cả bởi vì bạn là spoiler liverwurst từ cá voi rộng.

11
00:00:39,390 --> 00:00:44,710
Có, hiệu đính ớt của bạn là một vấn đề, bất lực tối đa.

12
00:00:44,710 --> 00:00:49,140
Đây là một vấn đề có ảnh hưởng đến các sinh viên nam tính, nam tính.

13
00:00:49,140 --> 00:00:56,260
Tôi đã một lần nói với sith lớp tra tấn của tôi mà tôi sẽ không bao giờ nhận được vào một đồng nghiệp tốt.

14
00:00:56,260 --> 00:01:00,250
Và đó là tất cả những gì tôi muốn, đó là tất cả các đứa trẻ nào muốn ở tuổi của tôi,

15
00:01:00,250 --> 00:01:04,569
chỉ để có được vào một đồng nghiệp tốt.

16
00:01:04,569 --> 00:01:12,720
Và không chỉ cần bất kỳ đồng nghiệp. Tôi muốn đi đến một đồng nghiệp pháp lý Ngà.

17
00:01:12,720 --> 00:01:18,360
Vì vậy, nếu tôi đã không cải thiện, đi sẽ là giấc mơ của tôi đi học ở Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, hoặc nhà tù - bạn biết đấy, trong nhà tù, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Vì vậy, tôi nhận bản thân mình một kiểm tra chính tả.

20
00:01:25,170 --> 00:01:29,380
Đó là một đoạn trích từ một trong những nghệ sĩ yêu thích lời nói của tôi, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Dù sao, như ông nói, tầm quan trọng của việc có một kiểm tra chính tả là rất quan trọng.

22
00:01:34,630 --> 00:01:39,440
>> Vì vậy, chào mừng bạn đến Walkthrough 5, trong đó chúng ta sẽ nói về pset5: Lỗi chính tả,

23
00:01:39,440 --> 00:01:44,300
trong đó chúng ta sẽ được thực hiện rất riêng của chúng tôi kiểm tra chính tả.

24
00:01:44,300 --> 00:01:50,880
Hộp công cụ cho tuần này, các mã phân phối, sẽ là quan trọng để xem xét

25
00:01:50,880 --> 00:01:54,950
chỉ để hiểu các chức năng khác nhau mà từ điển của bạn là sẽ có.

26
00:01:54,950 --> 00:02:01,500
Chúng tôi đang thực sự sẽ có nhiều c tập tin rằng cùng nhau làm cho pset của chúng tôi.

27
00:02:01,500 --> 00:02:05,420
Và vì thế tìm kiếm thông qua các khía cạnh khác nhau, mặc dù chúng ta đang thực sự không chỉnh sửa

28
00:02:05,420 --> 00:02:10,770
một trong các tập tin, speller.c, biết nó hoạt động như thế nào với mối quan hệ để dictionary.c,

29
00:02:10,770 --> 00:02:14,100
mà chúng ta sẽ viết, sẽ là khá quan trọng.

30
00:02:14,100 --> 00:02:16,970
Các spec pset cũng chứa rất nhiều thông tin hữu ích

31
00:02:16,970 --> 00:02:21,360
về những điều mà bạn có thể giả định, quy tắc và những điều như thế,

32
00:02:21,360 --> 00:02:24,710
vì vậy hãy chắc chắn để đọc các spec pset cẩn thận cho lời khuyên.

33
00:02:24,710 --> 00:02:29,310
Và khi nghi ngờ của một quy tắc hoặc một cái gì đó như thế, sau đó luôn luôn tham khảo spec pset

34
00:02:29,310 --> 00:02:31,550
hoặc thảo luận.

35
00:02:31,550 --> 00:02:34,060
Này pset sẽ phải dựa rất nhiều trên con trỏ,

36
00:02:34,060 --> 00:02:37,890
vì vậy chúng tôi muốn đảm bảo rằng chúng tôi hiểu sự khác biệt giữa các ngôi sao thêm

37
00:02:37,890 --> 00:02:41,680
ở phía trước tên và ampersands của con trỏ, làm thế nào để giải thoát họ, vv ...

38
00:02:41,680 --> 00:02:47,550
Vì vậy, là một bậc thầy của các con trỏ sẽ rất hữu ích trong vấn đề thiết lập này.

39
00:02:47,550 --> 00:02:50,460
Chúng ta sẽ nhìn vào danh sách liên kết nhiều hơn một chút,

40
00:02:50,460 --> 00:02:57,790
nơi mà chúng tôi có những yếu tố mà chúng ta gọi là các nút có cả một giá trị cũng như một con trỏ

41
00:02:57,790 --> 00:03:02,520
đến nút tiếp theo, và như vậy chủ yếu là liên kết các yếu tố khác nhau một sau khi khác.

42
00:03:02,520 --> 00:03:07,190
Có một vài lựa chọn khác nhau thực hiện từ điển thực tế của bạn.

43
00:03:07,190 --> 00:03:13,150
Chúng ta sẽ xem xét hai phương pháp chính, đó là bảng băm và sau đó cố gắng.

44
00:03:13,150 --> 00:03:17,660
Trong cả hai, liên quan đến một số loại khái niệm của một danh sách liên kết

45
00:03:17,660 --> 00:03:20,790
, nơi bạn có yếu tố liên kết với nhau.

46
00:03:20,790 --> 00:03:25,640
Và vì vậy chúng ta sẽ xem xét làm thế nào bạn có thể có thể hoạt động xung quanh danh sách liên kết,

47
00:03:25,640 --> 00:03:29,680
tạo ra chúng, điều hướng về làm thế nào để, ví dụ, chèn một nút vào nó

48
00:03:29,680 --> 00:03:32,760
hoặc miễn phí tất cả các nút như đây.

49
00:03:32,760 --> 00:03:34,740
Trong điều kiện của các nút giải phóng, đó là thực sự quan trọng

50
00:03:34,740 --> 00:03:37,700
rằng bất cứ khi nào chúng ta malloc bộ nhớ, sau đó chúng tôi giải phóng nó.

51
00:03:37,700 --> 00:03:42,910
Vì vậy, chúng tôi muốn đảm bảo rằng con trỏ không đi unfreed, chúng tôi không có bất kỳ rò rỉ bộ nhớ.

52
00:03:42,910 --> 00:03:48,330
Chúng tôi sẽ giới thiệu một công cụ được gọi là Valgrind chạy chương trình của bạn

53
00:03:48,330 --> 00:03:52,260
và kiểm tra tất cả các bộ nhớ mà bạn được giao sau đó được giải phóng.

54
00:03:52,260 --> 00:03:59,080
Pset của bạn chỉ được hoàn thành khi nó hoạt động và nó có đầy đủ chức năng,

55
00:03:59,080 --> 00:04:03,990
mà còn, Valgrind nói với bạn rằng bạn đã không tìm thấy bất kỳ rò rỉ bộ nhớ.

56
00:04:03,990 --> 00:04:06,690
Cuối cùng, cho pset này, tôi thực sự muốn nhấn mạnh -

57
00:04:06,690 --> 00:04:11,360
Ý tôi là, như thường lệ, tôi chắc chắn là một người ủng hộ bằng cách sử dụng bút và giấy cho các bộ vấn đề của bạn,

58
00:04:11,360 --> 00:04:14,840
nhưng đối với một trong những điều này, tôi nghĩ rằng cây bút và giấy là có được đặc biệt quan trọng

59
00:04:14,840 --> 00:04:19,000
khi bạn muốn được vẽ mũi tên để điều và hiểu những điều làm việc như thế nào.

60
00:04:19,000 --> 00:04:24,440
Vì vậy, chắc chắn cố gắng sử dụng bút và giấy để vẽ ra trước khi bạn nhận được mã hóa

61
00:04:24,440 --> 00:04:26,970
vì nó có thể có được một chút lộn xộn.

62
00:04:26,970 --> 00:04:30,700
>> Trước tiên, chúng ta hãy đi vào danh sách liên kết một chút.

63
00:04:30,700 --> 00:04:35,510
Danh sách liên kết bao gồm các nút, mỗi nút có giá trị liên kết với nó,

64
00:04:35,510 --> 00:04:39,810
cũng như một con trỏ đến nút tiếp theo sau khi nó.

65
00:04:39,810 --> 00:04:43,680
Một vài điều quan trọng với các danh sách liên kết mà chúng ta cần nhớ

66
00:04:43,680 --> 00:04:48,810
nút đầu tiên của chúng tôi là, và sau đó một khi chúng ta biết được nơi nút đầu tiên,

67
00:04:48,810 --> 00:04:52,990
như vậy chúng ta có thể truy cập các nút nút đầu tiên

68
00:04:52,990 --> 00:04:55,850
và sau đó một sau đó và sau đó.

69
00:04:55,850 --> 00:05:00,340
Và sau đó là yếu tố cuối cùng trong danh sách liên kết của bạn là con trỏ của nút đó

70
00:05:00,340 --> 00:05:02,340
luôn luôn để trỏ đến NULL.

71
00:05:02,340 --> 00:05:08,230
Khi một điểm nút NULL, sau đó bạn biết rằng bạn đã đạt đến cuối danh sách,

72
00:05:08,230 --> 00:05:12,320
nút đó là một trong những cuối cùng, rằng không có gì sau đó.

73
00:05:12,320 --> 00:05:16,970
Trong sơ đồ này, bạn thấy rằng các mũi tên con trỏ,

74
00:05:16,970 --> 00:05:20,290
và phần màu xanh là nơi mà giá trị được lưu giữ,

75
00:05:20,290 --> 00:05:24,420
và sau đó hộp màu đỏ với con trỏ đến nó là con trỏ của nút

76
00:05:24,420 --> 00:05:27,050
trỏ đến nút tiếp theo sau khi nó.

77
00:05:27,050 --> 00:05:33,730
Và như vậy bạn thấy ở đây, nút D sẽ chỉ để NULL bởi vì nó là yếu tố cuối cùng trong danh sách.

78
00:05:33,730 --> 00:05:38,240
>> Chúng ta hãy xem làm thế nào chúng ta có thể định nghĩa một cấu trúc cho một nút.

79
00:05:38,240 --> 00:05:40,130
Và kể từ khi chúng tôi muốn có nhiều nút,

80
00:05:40,130 --> 00:05:43,180
điều này sẽ trở thành một cấu trúc typedef

81
00:05:43,180 --> 00:05:46,870
trong đó chúng ta sẽ có một số trường hợp khác nhau của các nút.

82
00:05:46,870 --> 00:05:50,850
Và vì vậy chúng ta định nghĩa nó như là một kiểu dữ liệu mới.

83
00:05:50,850 --> 00:05:53,630
Ở đây, chúng tôi có một nút typedef struct.

84
00:05:53,630 --> 00:05:56,160
Trong ví dụ này, chúng ta đang đối phó với các nút số nguyên,

85
00:05:56,160 --> 00:06:00,490
vì vậy chúng tôi có một giá trị có tên là số nguyên và sau đó chúng tôi có một con trỏ,

86
00:06:00,490 --> 00:06:07,390
và trong trường hợp này, đó là một con trỏ tới một nút, vì vậy chúng tôi có một nút struct * gọi tiếp theo.

87
00:06:07,390 --> 00:06:09,520
Và sau đó chúng tôi đang gọi nút này toàn bộ điều.

88
00:06:09,520 --> 00:06:11,110
Hãy chắc chắn rằng bạn làm theo cú pháp này.

89
00:06:11,110 --> 00:06:17,940
Chú ý rằng nút là thực sự tham chiếu lên trên cũng như dưới các dấu ngoặc nhọn.

90
00:06:17,940 --> 00:06:23,400
Sau đó, để theo dõi các nút đầu tiên của tôi là trong danh sách liên kết này,

91
00:06:23,400 --> 00:06:29,390
sau đó tôi có một con trỏ được gọi là nút đầu, và không gian malloc Tôi đủ cho kích thước của một nút.

92
00:06:29,390 --> 00:06:36,240
Thông báo, tuy nhiên, người đứng đầu đó thực sự là một con trỏ nút như trái ngược với một nút thực tế bản thân.

93
00:06:36,240 --> 00:06:40,130
Vì vậy, người đứng đầu thực sự không chứa bất kỳ giá trị,

94
00:06:40,130 --> 00:06:45,590
nó chỉ chỉ vào bất cứ nút đầu tiên trong danh sách liên kết của tôi là.

95
00:06:55,080 --> 00:06:58,340
>> Để có được một cảm giác tốt hơn của danh sách liên kết, bởi vì nó rất quan trọng

96
00:06:58,340 --> 00:07:02,220
để theo dõi đảm bảo rằng bạn duy trì chuỗi,

97
00:07:02,220 --> 00:07:09,990
Tôi thích nghĩ về nó như những người trong một dòng nắm tay,

98
00:07:09,990 --> 00:07:14,330
nơi mà mỗi người đang tay trong tay với một trong những kế tiếp.

99
00:07:14,330 --> 00:07:18,350
Bạn không thể nhìn thấy trong bản vẽ này, nhưng về cơ bản họ chỉ cho người kế tiếp

100
00:07:18,350 --> 00:07:23,760
đó là trong dây chuyền của họ.

101
00:07:23,760 --> 00:07:29,270
Và vì vậy nếu bạn muốn đi qua một danh sách liên kết nơi mà những người

102
00:07:29,270 --> 00:07:32,830
tưởng tượng tất cả những người có giá trị liên kết với chúng

103
00:07:32,830 --> 00:07:36,590
và cũng chỉ ra những người tiếp theo trong dòng -

104
00:07:36,590 --> 00:07:40,810
nếu bạn muốn đi qua các danh sách liên kết, ví dụ, hoặc chỉnh sửa các giá trị

105
00:07:40,810 --> 00:07:42,830
hoặc tìm kiếm một giá trị hay một cái gì đó như thế,

106
00:07:42,830 --> 00:07:48,270
sau đó bạn sẽ muốn có một con trỏ đến người cụ thể.

107
00:07:48,270 --> 00:07:52,670
Vì vậy, chúng ta sẽ có một con trỏ dữ liệu Loại nút.

108
00:07:52,670 --> 00:07:55,580
Đối với trường hợp này, chúng ta hãy gọi nó là con trỏ.

109
00:07:55,580 --> 00:07:59,630
Một cách thông thường để tên này sẽ là iterator hoặc một cái gì đó như thế

110
00:07:59,630 --> 00:08:05,130
bởi vì nó iterating trên và thực sự di chuyển nút nó trỏ đến.

111
00:08:05,130 --> 00:08:14,410
Đây sẽ là con trỏ của chúng tôi.

112
00:08:14,410 --> 00:08:20,180
Con trỏ của chúng tôi đầu tiên sẽ trỏ đến phần tử đầu tiên trong danh sách của chúng tôi.

113
00:08:20,180 --> 00:08:26,910
Và do đó, những gì chúng tôi muốn làm là chúng ta về cơ bản sẽ được tiếp tục con trỏ,

114
00:08:26,910 --> 00:08:29,130
di chuyển từ bên này sang bên kia.

115
00:08:29,130 --> 00:08:33,409
Trong trường hợp này, chúng tôi muốn di chuyển nó đến phần tử tiếp theo trong danh sách.

116
00:08:33,409 --> 00:08:38,480
Với mảng, những gì chúng tôi làm là chúng ta sẽ chỉ nói rằng chúng ta tăng chỉ số bằng 1.

117
00:08:38,480 --> 00:08:46,020
Trong trường hợp này, những gì chúng ta cần làm là thực sự tìm thấy người người này hiện tại đang trỏ đến,

118
00:08:46,020 --> 00:08:48,930
và đó sẽ là giá trị tiếp theo.

119
00:08:48,930 --> 00:08:53,230
Vì vậy, nếu con trỏ chỉ là một con trỏ nút, sau đó những gì chúng tôi muốn làm

120
00:08:53,230 --> 00:08:56,320
là chúng tôi muốn để có được giá trị mà con trỏ đang trỏ đến.

121
00:08:56,320 --> 00:09:01,350
Chúng tôi muốn để có được nút đó và sau đó, khi chúng tôi đang ở nút đó, tìm thấy nơi nó trỏ đến.

122
00:09:01,350 --> 00:09:05,820
Để có được đến nút thực tế mà con trỏ đang trỏ đến,

123
00:09:05,820 --> 00:09:13,160
thông thường chúng ta chỉ ra nó (con trỏ).

124
00:09:13,160 --> 00:09:19,160
Điều đó sẽ cung cấp cho bạn các nút thực tế mà con trỏ đang trỏ đến.

125
00:09:19,160 --> 00:09:21,730
Và rồi sau đó, những gì chúng tôi muốn làm là chúng ta muốn truy cập

126
00:09:21,730 --> 00:09:25,680
bất cứ điều gì là giá trị tiếp theo của nút.

127
00:09:25,680 --> 00:09:32,820
Để làm điều đó, để truy cập vào các giá trị bên trong các cấu trúc, chúng tôi có các nhà điều hành chấm.

128
00:09:32,820 --> 00:09:39,530
Vì vậy, sau đó nó sẽ là (* con trỏ). Tiếp theo.

129
00:09:39,530 --> 00:09:44,840
Nhưng đây là một chút lộn xộn về có dấu ngoặc xung quanh con trỏ *

130
00:09:44,840 --> 00:09:56,800
và do đó, chúng tôi thay thế toàn bộ tuyên bố này với con trỏ->.

131
00:09:56,800 --> 00:10:02,700
Đây là một dấu gạch ngang và sau đó là một dấu hiệu lớn hơn, do đó, một mũi tên.

132
00:10:02,700 --> 00:10:05,840
con trỏ-> tiếp theo.

133
00:10:05,840 --> 00:10:12,390
Điều đó thực sự sẽ giúp bạn có được các nút con trỏ điểm. Đó là giá trị tiếp theo.

134
00:10:12,390 --> 00:10:16,790
Vì vậy, thay vì có ngôi sao và dấu chấm, bạn thay thế mà với một mũi tên.

135
00:10:16,790 --> 00:10:24,820
Hãy rất cẩn thận để đảm bảo rằng bạn hãy thử sử dụng cú pháp này.

136
00:10:33,550 --> 00:10:37,620
>> Bây giờ chúng ta có con trỏ của chúng tôi, nếu chúng ta muốn truy cập vào các giá trị,

137
00:10:37,620 --> 00:10:40,450
trước, chúng tôi đã có con trỏ-> tiếp theo,

138
00:10:40,450 --> 00:10:46,260
nhưng để truy cập các giá trị tại nút mà con trỏ đang trỏ đến, chúng tôi chỉ đơn giản là nói

139
00:10:46,260 --> 00:10:48,070
node-> giá trị.

140
00:10:48,070 --> 00:10:53,600
Từ đó, nó là kiểu dữ liệu bất cứ điều gì chúng tôi đã xác định các giá trị và các nút được.

141
00:10:53,600 --> 00:10:59,620
Nếu nó là một nút int, sau đó con trỏ-> giá trị chỉ là sẽ là một số nguyên.

142
00:10:59,620 --> 00:11:04,870
Vì vậy, chúng ta có thể làm các hoạt động về điều đó, hãy kiểm tra đẳng, gán cho nó giá trị khác nhau, vv

143
00:11:04,870 --> 00:11:11,090
Vì vậy, sau đó những gì bạn muốn làm gì nếu bạn muốn di chuyển con trỏ của bạn cho người kế tiếp,

144
00:11:11,090 --> 00:11:15,270
bạn thực sự thay đổi giá trị của con trỏ.

145
00:11:15,270 --> 00:11:19,340
Kể từ khi con trỏ là một con trỏ nút, bạn thay đổi địa chỉ con trỏ thực tế

146
00:11:19,340 --> 00:11:23,890
đến địa chỉ của nút tiếp theo trong danh sách của bạn.

147
00:11:23,890 --> 00:11:28,930
Đây chỉ là một số mã nơi bạn có thể lặp đi lặp lại.

148
00:11:28,930 --> 00:11:31,230
Tôi có những nhận xét làm điều gì đó,

149
00:11:31,230 --> 00:11:33,850
đó là nơi bạn có thể sẽ để truy cập vào các giá trị

150
00:11:33,850 --> 00:11:37,850
hoặc làm điều gì đó để làm với nút cụ thể đó.

151
00:11:37,850 --> 00:11:43,050
Để bắt đầu, tôi nói rằng con trỏ chuột của tôi ban đầu

152
00:11:43,050 --> 00:11:48,430
để trỏ đến phần tử đầu tiên trong danh sách liên kết.

153
00:11:48,430 --> 00:11:52,910
Và phía trước, tôi xác định là người đứng đầu của các nút.

154
00:11:52,910 --> 00:11:57,610
>> Như tôi đã đề cập trước đây, giải phóng thực sự là quan trọng.

155
00:11:57,610 --> 00:12:02,440
Bạn muốn làm cho chắc chắn rằng bạn miễn phí mọi phần tử trong danh sách, một khi bạn đã kết thúc với nó.

156
00:12:02,440 --> 00:12:04,940
Khi bạn không cần phải tham khảo bất kỳ của những người con trỏ nữa,

157
00:12:04,940 --> 00:12:10,620
bạn muốn làm cho chắc chắn rằng bạn giải phóng tất cả các con trỏ.

158
00:12:10,620 --> 00:12:14,460
Nhưng bạn phải rất cẩn thận trong đó bạn muốn để tránh bất kỳ rò rỉ bộ nhớ.

159
00:12:14,460 --> 00:12:25,080
Nếu bạn miễn phí một người sớm, sau đó tất cả các con trỏ mà rằng nút điểm

160
00:12:25,080 --> 00:12:26,900
sẽ bị mất.

161
00:12:26,900 --> 00:12:32,070
Trở lại ví dụ người để làm cho nó cổ phần cao hơn một chút,

162
00:12:32,070 --> 00:12:49,600
chúng ta hãy có những người này, ngoại trừ trong trường hợp này họ đang lơ lửng trên một hồ nước với một con quái vật.

163
00:12:49,600 --> 00:12:53,200
Chúng tôi muốn đảm bảo rằng bất cứ khi nào chúng ta tự do, chúng tôi không bị mất

164
00:12:53,200 --> 00:12:58,920
và để cho đi của bất kỳ nút trước khi chúng tôi đã thực sự giải phóng họ.

165
00:12:58,920 --> 00:13:05,730
Ví dụ, nếu bạn chỉ đơn giản là gọi miễn phí trên anh chàng này ở đây,

166
00:13:05,730 --> 00:13:15,350
sau đó ông sẽ được giải thoát, nhưng sau đó tất cả những kẻ sau đó sẽ bị mất

167
00:13:15,350 --> 00:13:18,450
và họ sẽ trôi đi và rơi xuống.

168
00:13:18,450 --> 00:13:24,900
Vì vậy, chúng tôi muốn chắc chắn rằng thay vào đó, chúng tôi muốn duy trì một liên kết đến phần còn lại.

169
00:13:37,630 --> 00:13:42,480
Con trỏ đầu của chúng tôi, chỉ vào phần tử đầu tiên trong danh sách.

170
00:13:42,480 --> 00:13:49,990
Nó là loại giống như một sợi dây thừng neo người đầu tiên.

171
00:13:52,870 --> 00:13:57,470
Những gì bạn có thể muốn làm gì khi bạn giải phóng một danh sách có -

172
00:13:57,470 --> 00:14:04,520
Nếu bạn muốn miễn phí các yếu tố đầu tiên đầu tiên, sau đó bạn có thể có một con trỏ tạm thời

173
00:14:04,520 --> 00:14:07,370
điểm mà bất cứ các yếu tố đầu tiên.

174
00:14:07,370 --> 00:14:11,420
Vì vậy, bạn có con trỏ tạm thời của bạn chỉ ở đây.

175
00:14:11,420 --> 00:14:15,840
Bằng cách đó, chúng tôi có một tổ chức của nút đầu tiên.

176
00:14:15,840 --> 00:14:18,930
Và sau đó, kể từ khi chúng ta biết rằng nút đầu tiên sẽ được giải thoát,

177
00:14:18,930 --> 00:14:24,890
sau đó chúng ta có thể di chuyển dây thừng, neo, người đứng đầu của chúng tôi,

178
00:14:24,890 --> 00:14:31,930
để thực sự trỏ đến bất cứ điều gì một trong những đầu tiên được trỏ đến.

179
00:14:31,930 --> 00:14:38,760
Vì vậy, đầu này thực sự chỉ vào phần tử thứ hai.

180
00:14:38,760 --> 00:14:43,980
Bây giờ chúng tôi được phép để giải phóng bất cứ điều gì được lưu trữ ở nhiệt độ,

181
00:14:43,980 --> 00:14:53,360
và vì vậy chúng tôi có thể xóa mà không gây nguy hiểm cho tất cả các nút khác trong danh sách của chúng tôi.

182
00:14:54,140 --> 00:15:05,020
Một cách khác mà bạn có thể làm điều này có thể được

183
00:15:05,020 --> 00:15:08,650
mỗi khi bạn chỉ cần miễn phí các phần tử cuối cùng trong danh sách

184
00:15:08,650 --> 00:15:11,010
bởi vì họ sẽ được bảo đảm không được chỉ tới bất cứ điều gì.

185
00:15:11,010 --> 00:15:15,570
Vì vậy, bạn chỉ có thể miễn phí này, sau đó tự do này, sau đó miễn phí này.

186
00:15:15,570 --> 00:15:21,900
Điều đó chắc chắn làm việc nhưng chậm hơn một chút bởi vì bản chất của các danh sách liên kết,

187
00:15:21,900 --> 00:15:24,670
chúng ta không thể ngay lập tức nhảy đến người cuối cùng.

188
00:15:24,670 --> 00:15:28,030
Chúng tôi phải đi qua từng phần tử trong danh sách liên kết

189
00:15:28,030 --> 00:15:31,020
và kiểm tra xem liệu đó có phải là một trong những chỉ để NULL, kiểm tra tất cả các thời gian,

190
00:15:31,020 --> 00:15:33,780
và sau đó một khi chúng ta đạt được kết thúc, sau đó miễn phí mà.

191
00:15:33,780 --> 00:15:40,270
Nếu bạn đã làm quá trình này, bạn thực sự sẽ được kiểm tra ở đây,

192
00:15:40,270 --> 00:15:44,190
kiểm tra ở đây, sau đó kiểm tra ở đây, giải phóng nó,

193
00:15:44,190 --> 00:15:47,470
sau đó sẽ trở lại, kiểm tra ở đây, kiểm tra ở đây, giải phóng nó,

194
00:15:47,470 --> 00:15:49,660
kiểm tra ở đây, và sau đó giải phóng nó.

195
00:15:49,660 --> 00:15:52,880
Điều đó cần có thời gian nhiều hơn một chút. Yeah.

196
00:15:52,880 --> 00:15:59,060
>> [Sinh viên] nó có thể sẽ được để thực hiện một danh sách liên kết mà các cửa hàng một con trỏ xuất cảnh để kết thúc?

197
00:15:59,060 --> 00:16:01,320
Điều đó chắc chắn sẽ là có thể.

198
00:16:01,320 --> 00:16:08,340
Để lặp lại câu hỏi, là nó có thể có một cấu trúc danh sách liên kết

199
00:16:08,340 --> 00:16:12,490
như vậy mà bạn có một con trỏ trỏ đến cuối của danh sách liên kết?

200
00:16:12,490 --> 00:16:18,090
Tôi muốn nói đó là có thể, và mỗi lần bạn chèn một cái gì đó vào danh sách liên kết của bạn

201
00:16:18,090 --> 00:16:21,470
bạn sẽ phải cập nhật con trỏ và vật như thế.

202
00:16:21,470 --> 00:16:26,640
Bạn sẽ có một cái đuôi * nút, ví dụ.

203
00:16:26,640 --> 00:16:29,840
Nhưng khi bạn đang thực hiện tính năng này, bạn phải suy nghĩ của off-thương mại,

204
00:16:29,840 --> 00:16:32,700
như bao nhiêu lần tôi sẽ được lặp lại trên này,

205
00:16:32,700 --> 00:16:36,100
khó khăn như thế nào là nó sẽ được theo dõi của đuôi cũng như đầu

206
00:16:36,100 --> 00:16:38,400
cũng như iterator của tôi, và những thứ như thế.

207
00:16:40,730 --> 00:16:42,480
Điều đó? >> [Sinh viên] Yeah.

208
00:16:42,480 --> 00:16:48,270
Có thể, nhưng về các quyết định thiết kế, bạn phải cân nhắc các lựa chọn.

209
00:16:53,850 --> 00:17:01,090
>> Dưới đây là một bộ xương của mã đó sẽ cho phép bạn để giải phóng mọi phần tử trong một danh sách liên kết.

210
00:17:01,090 --> 00:17:05,460
Một lần nữa, kể từ khi tôi iterating trên một danh sách liên kết, tôi sẽ muốn có một số loại của con trỏ

211
00:17:05,460 --> 00:17:08,670
iterator.

212
00:17:08,670 --> 00:17:14,640
Chúng tôi đang lặp lại cho đến khi con trỏ là NULL.

213
00:17:14,640 --> 00:17:17,640
Bạn không muốn để lặp lại khi con trỏ của bạn là NULL

214
00:17:17,640 --> 00:17:20,579
bởi vì điều đó có nghĩa rằng không có bất cứ điều gì trong danh sách.

215
00:17:20,579 --> 00:17:25,069
Vì vậy, sau đó ở đây tôi làm cho một nút tạm thời *

216
00:17:25,069 --> 00:17:29,610
chỉ với những gì tôi đang xem xét đầu tiên trong danh sách của tôi,

217
00:17:29,610 --> 00:17:35,340
và sau đó tôi di chuyển con trỏ chuột của tôi trước 1 và sau đó miễn phí bất cứ điều gì tôi đã có trong lưu trữ tạm thời.

218
00:17:38,460 --> 00:17:43,650
>> Bây giờ chúng ta chèn vào danh sách liên kết.

219
00:18:00,200 --> 00:18:09,660
Tôi có ba nút trong danh sách liên kết của tôi, và chúng ta hãy đi với trường hợp đơn giản

220
00:18:09,660 --> 00:18:18,970
nơi mà chúng tôi muốn chèn một nút vào cuối danh sách liên kết của chúng tôi.

221
00:18:18,970 --> 00:18:25,980
Để làm được điều đó, tất cả chúng ta sẽ làm là chúng ta sẽ đi qua

222
00:18:25,980 --> 00:18:32,100
để tìm nơi kết thúc hiện tại của danh sách liên kết, do đó, tùy theo điều kiện nào nút được trỏ đến NULL -

223
00:18:32,100 --> 00:18:33,850
đó là một trong những điều này -

224
00:18:33,850 --> 00:18:37,260
và sau đó nói, trên thực tế, điều này là một trong những sẽ không phải là nút cuối cùng;

225
00:18:37,260 --> 00:18:39,830
chúng tôi đang thực sự sẽ có một số khác.

226
00:18:39,830 --> 00:18:46,260
Vì vậy, chúng ta sẽ có một trong hiện tại thời điểm này để bất cứ điều gì chúng tôi đang chèn.

227
00:18:46,260 --> 00:18:50,080
Vì vậy, bây giờ người này màu đỏ ở đây sẽ trở thành nút cuối cùng trong danh sách liên kết.

228
00:18:50,080 --> 00:18:56,080
Và do đó, các đặc tính của nút cuối cùng trong danh sách liên kết là nó trỏ đến NULL.

229
00:18:56,080 --> 00:19:09,380
Vì vậy, sau đó chúng tôi sẽ phải làm là thiết lập con trỏ của anh chàng này màu đỏ là NULL. Ở đó.

230
00:19:09,380 --> 00:19:25,370
>> Nhưng điều gì sẽ xảy ra nếu chúng ta muốn chèn một nút ở giữa một trong những thứ hai và thứ ba?

231
00:19:25,370 --> 00:19:28,960
Một trong đó không phải là khá đơn giản bởi vì chúng tôi muốn chắc chắn

232
00:19:28,960 --> 00:19:34,290
mà chúng ta không để cho bất kỳ nút trong danh sách liên kết của chúng tôi.

233
00:19:34,290 --> 00:19:43,450
Những gì chúng tôi sẽ phải làm là đảm bảo rằng chúng tôi neo mình với mỗi một.

234
00:19:43,450 --> 00:19:49,900
Ví dụ, chúng ta hãy gọi đây là thứ hai.

235
00:19:49,900 --> 00:19:54,390
Nếu bạn nói một trong những thứ hai tại điểm này mới

236
00:19:54,390 --> 00:20:02,520
và bạn chỉ cần thực hiện một con trỏ ở đó, sau đó sẽ dẫn đến việc anh chàng này bị mất

237
00:20:02,520 --> 00:20:07,830
bởi vì không có bất cứ liên kết nào với anh ta.

238
00:20:07,830 --> 00:20:18,970
Thay vào đó tôi sẽ vẽ này một lần nữa. Xin lỗi khả năng nghệ thuật của tôi.

239
00:20:18,970 --> 00:20:26,570
Chúng ta biết rằng chúng ta có thể không trực tiếp liên kết 2 mới.

240
00:20:26,570 --> 00:20:30,480
Chúng tôi phải đảm bảo rằng chúng tôi giữ đến người cuối cùng.

241
00:20:30,480 --> 00:20:39,200
Những gì chúng tôi có thể muốn làm là có một con trỏ tạm thời

242
00:20:39,200 --> 00:20:42,650
các yếu tố đó sẽ được nối trên.

243
00:20:42,650 --> 00:20:45,140
Vì vậy, sau đó chúng tôi có một con trỏ tạm thời.

244
00:20:45,140 --> 00:20:50,780
Kể từ khi chúng ta biết rằng 1/3 này đang được lưu giữ theo dõi,

245
00:20:50,780 --> 00:20:53,680
2 bây giờ có thể liên kết sang cái mới của chúng tôi.

246
00:20:53,680 --> 00:20:57,490
Và nếu anh chàng này màu đỏ mới là có được giữa 2 và 3,

247
00:20:57,490 --> 00:21:05,550
sau đó của anh chàng đó con trỏ để trỏ đến những gì? >> [Sinh viên] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Yeah.

249
00:21:07,490 --> 00:21:15,430
Vì vậy, sau đó giá trị tiếp theo của anh chàng này màu đỏ sẽ là tạm thời.

250
00:21:26,090 --> 00:21:33,010
Khi bạn chèn vào danh sách liên kết, chúng tôi thấy rằng chúng tôi có thể

251
00:21:33,010 --> 00:21:38,260
dễ dàng thêm một cái gì đó để kết thúc bằng cách tạo ra một mảng tạm thời,

252
00:21:38,260 --> 00:21:42,850
hoặc nếu chúng tôi muốn thêm một cái gì đó vào giữa mảng của chúng tôi,

253
00:21:42,850 --> 00:21:46,810
sau đó nó sẽ mất một chút xáo trộn xung quanh.

254
00:21:46,810 --> 00:21:50,240
Nếu bạn muốn, ví dụ, có một danh sách được sắp xếp liên kết,

255
00:21:50,240 --> 00:21:54,880
sau đó bạn phải loại cân nhắc chi phí và lợi ích của thế

256
00:21:54,880 --> 00:21:59,720
bởi vì nếu bạn muốn có một mảng được sắp xếp, điều đó có nghĩa là mỗi khi bạn chèn vào nó,

257
00:21:59,720 --> 00:22:01,630
nó sẽ mất thời gian nhiều hơn một chút.

258
00:22:01,630 --> 00:22:05,500
Tuy nhiên, nếu bạn muốn sau này, như chúng ta sẽ thấy chúng ta sẽ muốn,

259
00:22:05,500 --> 00:22:10,280
tìm kiếm thông qua một danh sách liên kết, sau đó nó có thể được dễ dàng hơn nếu bạn biết rằng tất cả mọi thứ là theo thứ tự.

260
00:22:10,280 --> 00:22:15,340
Vì vậy, bạn có thể muốn cân nhắc chi phí và lợi ích của thế.

261
00:22:20,150 --> 00:22:27,740
>> Một cách khác để chèn vào một danh sách liên kết là để chèn vào đầu của một danh sách.

262
00:22:27,740 --> 00:22:34,700
Nếu chúng ta rút ra neo của chúng tôi ở đây - đây là người đứng đầu của chúng tôi -

263
00:22:34,700 --> 00:22:40,960
và sau đó có những người này liên kết với nó,

264
00:22:40,960 --> 00:22:48,460
và sau đó chúng tôi có một nút mới được chèn vào đầu,

265
00:22:48,460 --> 00:22:52,590
sau đó những gì chúng ta có thể muốn làm gì?

266
00:22:55,220 --> 00:23:03,580
Điều gì sẽ là sai với chỉ nói rằng tôi muốn để liên kết các màu đỏ sang màu xanh,

267
00:23:03,580 --> 00:23:05,790
bởi vì đó là một trong những đầu tiên?

268
00:23:05,790 --> 00:23:08,570
Điều gì sẽ xảy ra ở đây?

269
00:23:08,570 --> 00:23:12,130
Tất cả ba sẽ bị lạc.

270
00:23:12,130 --> 00:23:14,140
Vì vậy, chúng tôi không muốn làm điều đó.

271
00:23:14,140 --> 00:23:21,430
Một lần nữa, chúng tôi đã học được rằng chúng ta cần phải có một số loại của con trỏ tạm thời.

272
00:23:21,430 --> 00:23:34,470
Hãy lựa chọn để có một điểm tạm thời với anh chàng này.

273
00:23:34,470 --> 00:23:39,640
Sau đó, chúng ta có thể có một điểm màu xanh để tạm thời

274
00:23:39,640 --> 00:23:43,240
và sau đó các điểm màu đỏ sang màu xanh.

275
00:23:43,240 --> 00:23:47,830
Lý do tại sao tôi đang sử dụng người dân ở đây là bởi vì chúng tôi thực sự muốn hình dung

276
00:23:47,830 --> 00:23:53,180
giữ cho người dân và đảm bảo rằng chúng tôi có một liên kết đến họ

277
00:23:53,180 --> 00:23:57,590
trước khi chúng ta để cho đi của một tay hoặc một cái gì đó như thế.

278
00:24:05,630 --> 00:24:10,650
>> Bây giờ chúng ta có một cảm giác của danh sách liên kết - làm thế nào chúng ta có thể tạo ra một danh sách liên kết

279
00:24:10,650 --> 00:24:15,090
và tạo ra các cấu trúc đó bao gồm các định nghĩa kiểu cho nút

280
00:24:15,090 --> 00:24:19,060
và sau đó đảm bảo rằng chúng ta có một con trỏ đến đầu của danh sách liên kết đó -

281
00:24:19,060 --> 00:24:23,210
một khi chúng tôi đã có và chúng tôi biết làm thế nào để đi qua thông qua một mảng,

282
00:24:23,210 --> 00:24:28,200
yếu tố khác nhau, chúng tôi biết làm thế nào để chèn và chúng tôi biết làm thế nào để giải thoát họ,

283
00:24:28,200 --> 00:24:30,260
sau đó chúng ta có thể nhận được vào các lỗi chính tả.

284
00:24:30,260 --> 00:24:38,150
Như thường lệ, chúng tôi có một phần của câu hỏi sẽ giúp bạn có được sử dụng để hoạt động với danh sách liên kết

285
00:24:38,150 --> 00:24:41,750
và cấu trúc khác nhau như hàng đợi và ngăn xếp.

286
00:24:41,750 --> 00:24:46,000
Sau đó, chúng ta có thể di chuyển vào các lỗi chính tả.

287
00:24:46,000 --> 00:24:55,170
>> Lỗi chính tả có trong mã phân phối một vài các tập tin quan trọng.

288
00:24:55,170 --> 00:24:58,850
Trước tiên, chúng tôi nhận thấy rằng chúng ta có Makefile này đây,

289
00:24:58,850 --> 00:25:03,040
mà chúng tôi đã không thực sự gặp phải trước đây.

290
00:25:03,040 --> 00:25:10,090
Nếu bạn nhìn vào bên trong thư mục pset5, bạn sẽ thấy rằng bạn có một tập tin h,

291
00:25:10,090 --> 00:25:12,530
sau đó bạn có hai c tập tin.

292
00:25:12,530 --> 00:25:18,920
Makefile này không có gì là trước đây, chúng ta chỉ nên gõ thực hiện và sau đó là tên chương trình

293
00:25:18,920 --> 00:25:25,550
và sau đó chúng ta sẽ thấy tất cả những lập luận này và cờ thông qua để trình biên dịch.

294
00:25:25,550 --> 00:25:30,580
Makefile không cho phép chúng tôi biên dịch tập tin cùng một lúc

295
00:25:30,580 --> 00:25:34,650
và vượt qua trong những lá cờ mà chúng tôi muốn.

296
00:25:34,650 --> 00:25:41,300
Ở đây chúng ta chỉ thấy có một tập tin tiêu đề ở đây.

297
00:25:41,300 --> 00:25:43,730
Sau đó, chúng tôi thực sự có hai tập tin nguồn.

298
00:25:43,730 --> 00:25:47,520
Chúng tôi có speller.c và dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Bạn được chào đón để chỉnh sửa các Makefile nếu bạn muốn.

300
00:25:54,560 --> 00:26:03,310
Chú ý rằng nếu bạn gõ sạch, sau đó những gì nó thực sự là loại bỏ bất cứ điều gì

301
00:26:03,310 --> 00:26:06,340
đó là cốt lõi.

302
00:26:06,340 --> 00:26:09,190
Nếu bạn nhận được một lỗi phân khúc, về cơ bản bạn sẽ có được một bãi chứa lõi.

303
00:26:09,190 --> 00:26:13,260
Vì vậy, xấu xí ít tập tin này sẽ xuất hiện trong thư mục của bạn lõi được gọi là.

304
00:26:13,260 --> 00:26:16,310
Bạn sẽ muốn loại bỏ để làm cho nó sạch.

305
00:26:16,310 --> 00:26:20,940
Nó loại bỏ bất kỳ tập tin exe và các tập tin o.

306
00:26:27,900 --> 00:26:30,220
>> Hãy có một cái nhìn vào dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Điều này nói rằng tuyên bố chức năng của từ điển.

308
00:26:34,410 --> 00:26:39,530
Chúng tôi có một chiều dài tối đa cho bất kỳ từ nào trong từ điển.

309
00:26:39,530 --> 00:26:45,130
Chúng tôi nói rằng điều này là có được lâu nhất có thể từ. Nó có chiều dài 45.

310
00:26:45,130 --> 00:26:48,900
Vì vậy, chúng tôi sẽ không có bất kỳ từ nào vượt quá độ dài.

311
00:26:48,900 --> 00:26:50,980
Ở đây chúng ta chỉ có các nguyên mẫu chức năng.

312
00:26:50,980 --> 00:26:55,290
Chúng tôi không có việc thực hiện thực tế bởi vì đó là những gì chúng tôi sẽ làm cho pset này.

313
00:26:55,290 --> 00:26:59,940
Nhưng điều này không có gì kể từ khi chúng tôi đang làm việc với các tập tin lớn hơn ở đây

314
00:26:59,940 --> 00:27:06,650
và chức năng trên một quy mô lớn hơn, đó là hữu ích để có một h tập tin.

315
00:27:06,650 --> 00:27:11,290
để người khác đọc hoặc sử dụng mã của bạn có thể hiểu những gì đang xảy ra.

316
00:27:11,290 --> 00:27:17,910
Và có lẽ họ muốn thực hiện cố gắng nếu bạn đã làm các bảng băm hoặc ngược lại.

317
00:27:17,910 --> 00:27:21,850
Sau đó, họ sẽ nói chức năng tải của tôi,

318
00:27:21,850 --> 00:27:26,950
việc thực hiện thực tế sẽ khác nhau, nhưng nguyên mẫu này sẽ không thay đổi.

319
00:27:26,950 --> 00:27:33,280
Ở đây chúng tôi đã kiểm tra, mà trả về true nếu một từ có trong từ điển.

320
00:27:33,280 --> 00:27:39,800
Sau đó, chúng tôi có tải, mà về cơ bản có trong một tập tin từ điển

321
00:27:39,800 --> 00:27:44,360
và sau đó tải nó vào một số cấu trúc dữ liệu.

322
00:27:44,360 --> 00:27:47,500
Chúng tôi có kích thước, trong đó, khi được gọi, trả về kích thước của từ điển của bạn,

323
00:27:47,500 --> 00:27:50,310
bao nhiêu từ được lưu trong đó,

324
00:27:50,310 --> 00:27:54,390
và sau đó dỡ bỏ, mà giải phóng tất cả các bộ nhớ mà bạn có thể đã đưa lên

325
00:27:54,390 --> 00:27:57,900
trong khi làm cho từ điển của bạn.

326
00:28:01,070 --> 00:28:03,590
>> Chúng ta hãy nhìn vào dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Chúng tôi thấy rằng nó trông rất tương tự như dictionary.h, ngoại trừ bây giờ nó chỉ có tất cả các todos nó.

328
00:28:10,490 --> 00:28:16,980
Và vì vậy đó là công việc của bạn. Cuối cùng, bạn sẽ được điền speller.c với tất cả các mã này.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, khi chạy, không thực sự sẽ làm bất cứ điều gì,

330
00:28:21,540 --> 00:28:29,590
do đó, chúng ta nhìn về phía speller.c thấy việc thực hiện thực tế của kiểm tra chính tả.

331
00:28:29,590 --> 00:28:32,060
Mặc dù bạn sẽ không thể chỉnh sửa bất kỳ của mã này,

332
00:28:32,060 --> 00:28:38,050
điều quan trọng là để đọc, hiểu khi được gọi là tải trọng, khi tôi gọi điện thoại kiểm tra,

333
00:28:38,050 --> 00:28:42,350
chỉ để hiểu, bản đồ nó ra, chức năng hoạt động như thế nào.

334
00:28:42,350 --> 00:28:49,860
Chúng tôi thấy rằng nó kiểm tra cho việc sử dụng chính xác.

335
00:28:49,860 --> 00:28:55,200
Về cơ bản, khi một ai đó chạy speller, điều này chỉ ra rằng nó là tùy chọn

336
00:28:55,200 --> 00:29:00,950
họ phải vượt qua trong một tập tin từ điển, vì sẽ là một từ điển mặc định tập tin.

337
00:29:00,950 --> 00:29:05,410
Và sau đó họ phải vượt qua trong văn bản để kiểm tra chính tả.

338
00:29:05,410 --> 00:29:11,410
các giao dịch rusage với thời gian vì một phần của pset này chúng tôi sẽ đối phó với sau

339
00:29:11,410 --> 00:29:14,790
không chỉ nhận được một chức năng kiểm tra chính tả làm việc

340
00:29:14,790 --> 00:29:17,190
nhưng thực sự nhận được nó để được nhanh chóng.

341
00:29:17,190 --> 00:29:22,040
Và như vậy thì đó là nơi rusage sẽ đến.

342
00:29:22,040 --> 00:29:28,740
Ở đây, chúng ta thấy cuộc gọi đầu tiên một các tập tin dictionary.c của chúng tôi, đó là tải.

343
00:29:28,740 --> 00:29:34,720
Tải trả về đúng hay sai - đúng khi thành công, false khi thất bại.

344
00:29:34,720 --> 00:29:41,400
Vì vậy, nếu từ điển không load được, sau đó speller.c sẽ trở về 1 và bỏ thuốc lá.

345
00:29:41,400 --> 00:29:47,920
Nhưng nếu nó không tải đúng cách, sau đó nó sẽ để tiếp tục.

346
00:29:47,920 --> 00:29:50,740
Chúng tôi tiếp tục, và chúng ta thấy một số tập tin I / O ở đây,

347
00:29:50,740 --> 00:29:56,210
mà nó sẽ được giao dịch với mở các tập tin văn bản.

348
00:29:56,210 --> 00:30:04,640
Ở đây, điều này không là spell-kiểm tra tất cả các từ duy nhất trong văn bản.

349
00:30:04,640 --> 00:30:09,270
Vì vậy, những gì speller.c làm ngay tại đây iterating trên mỗi từ trong các tập tin văn bản

350
00:30:09,270 --> 00:30:12,790
và sau đó kiểm tra trong từ điển.

351
00:30:24,680 --> 00:30:32,350
Ở đây, chúng tôi có một Boolean sai chính tả sẽ thấy nếu kiểm tra trả về đúng hay không.

352
00:30:32,350 --> 00:30:37,110
Nếu từ đó thực sự có trong từ điển, sau đó kiểm tra sẽ trở lại đúng sự thật.

353
00:30:37,110 --> 00:30:39,760
Điều đó có nghĩa rằng từ ngữ này không sai chính tả.

354
00:30:39,760 --> 00:30:45,330
Vì vậy, sai chính tả sẽ là sai lầm, và đó là lý do tại sao chúng tôi có các bang ở đó, chỉ định.

355
00:30:45,330 --> 00:30:56,320
Chúng tôi tiếp tục đi, và sau đó nó theo dõi có bao nhiêu từ sai chính tả

356
00:30:56,320 --> 00:30:58,910
có trong tập tin.

357
00:30:58,910 --> 00:31:03,870
Nó tiếp tục và đóng file.

358
00:31:03,870 --> 00:31:09,250
Sau đó, ở đây, nó báo cáo bạn đã có bao nhiêu từ sai chính tả.

359
00:31:09,250 --> 00:31:12,680
Nó tính toán mất bao nhiêu thời gian để tải các từ điển,

360
00:31:12,680 --> 00:31:15,080
mất bao nhiêu thời gian để kiểm tra xem nó,

361
00:31:15,080 --> 00:31:18,510
bao nhiêu thời gian đã mất để tính toán kích thước,

362
00:31:18,510 --> 00:31:21,260
, như chúng ta sẽ đi về, nên rất nhỏ,

363
00:31:21,260 --> 00:31:25,390
và sau đó mất bao nhiêu thời gian để dỡ bỏ các từ điển.

364
00:31:25,390 --> 00:31:27,700
Ở đây lên trên chúng ta thấy các cuộc gọi dỡ bỏ ở đây.

365
00:31:27,700 --> 00:31:52,690
Nếu chúng ta kiểm tra các kích thước ở đây,

366
00:31:52,690 --> 00:31:59,050
sau đó chúng ta thấy rằng đây là các cuộc gọi đến kích thước, nơi đó xác định kích thước của từ điển.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Nhiệm vụ của chúng tôi cho pset này là để thực hiện tải, mà sẽ được tải từ điển

369
00:32:10,920 --> 00:32:15,480
cấu trúc dữ liệu nào mà bạn chọn, có thể là một bảng băm hoặc một thử -

370
00:32:15,480 --> 00:32:18,810
từ tập tin từ điển.

371
00:32:18,810 --> 00:32:25,290
Sau đó, bạn có kích thước, mà sẽ trả về số từ trong từ điển.

372
00:32:25,290 --> 00:32:29,860
Và nếu bạn thực hiện tải một cách thông minh, sau đó kích thước nên được khá dễ dàng.

373
00:32:29,860 --> 00:32:33,860
Sau đó, bạn đã kiểm tra, đó sẽ kiểm tra nếu một từ có trong từ điển.

374
00:32:33,860 --> 00:32:38,690
Vì vậy, speller.c qua trong một chuỗi, và sau đó bạn phải kiểm tra xem chuỗi đó

375
00:32:38,690 --> 00:32:41,610
được chứa trong từ điển của bạn.

376
00:32:41,610 --> 00:32:46,750
Chú ý rằng chúng ta thường có từ điển tiêu chuẩn,

377
00:32:46,750 --> 00:32:53,020
nhưng trong pset này, về cơ bản bất kỳ từ điển thông qua trong bất kỳ ngôn ngữ.

378
00:32:53,020 --> 00:32:57,040
Vì vậy, chúng ta không thể giả định rằng từ bên trong.

379
00:32:57,040 --> 00:33:03,090
FOOBAR từ có thể được định nghĩa trong từ điển nào đó mà chúng tôi vượt qua.

380
00:33:03,090 --> 00:33:07,920
Và sau đó chúng tôi đã dỡ bỏ, mà giải phóng từ điển từ bộ nhớ.

381
00:33:07,920 --> 00:33:11,930
>> Trước tiên, tôi muốn đi qua các phương pháp bảng băm

382
00:33:11,930 --> 00:33:14,630
về làm thế nào chúng ta có thể thực hiện tất cả những bốn chức năng,

383
00:33:14,630 --> 00:33:18,650
và sau đó tôi sẽ đi qua cố gắng phương pháp, làm thế nào chúng ta thực hiện bốn chức năng,

384
00:33:18,650 --> 00:33:22,720
và nói chuyện cuối cùng về một số lời khuyên chung khi bạn đang làm cho pset

385
00:33:22,720 --> 00:33:27,870
và cũng có thể làm thế nào bạn có thể có thể sử dụng Valgrind để kiểm tra rò rỉ bộ nhớ.

386
00:33:27,870 --> 00:33:30,550
>> Chúng ta hãy vào phương pháp bảng băm.

387
00:33:30,550 --> 00:33:35,910
Một bảng băm bao gồm một danh sách các nhóm.

388
00:33:35,910 --> 00:33:43,010
Mỗi giá trị, từng chữ, để đi vào một trong những xô.

389
00:33:43,010 --> 00:33:53,200
Một bảng băm lý tưởng phân phối đều tất cả các giá trị mà bạn đang đi qua trong

390
00:33:53,200 --> 00:33:57,160
và sau đó phổ biến nhất trong xô như vậy mà mỗi thùng

391
00:33:57,160 --> 00:34:02,000
có khoảng một số lượng tương đương giá trị trong nó.

392
00:34:02,000 --> 00:34:09,630
Cấu trúc cho một bảng băm, chúng tôi có một loạt các danh sách liên kết.

393
00:34:09,630 --> 00:34:17,900
Những gì chúng tôi làm là khi chúng tôi vượt qua một giá trị, chúng ta kiểm tra giá trị đó phải thuộc về,

394
00:34:17,900 --> 00:34:23,840
xô nó thuộc về, và sau đó đặt nó vào danh sách liên kết liên quan đến thùng đó.

395
00:34:23,840 --> 00:34:28,199
Ở đây, những gì tôi có là một hàm băm.

396
00:34:28,199 --> 00:34:31,320
Đây là một bảng băm int.

397
00:34:31,320 --> 00:34:38,540
Vì vậy, đối với nhóm đầu tiên, bất kỳ số nguyên dưới 10 đi vào xô đầu tiên.

398
00:34:38,540 --> 00:34:42,190
Bất kỳ số nguyên trên 10 nhưng dưới đi 20 vào thứ hai,

399
00:34:42,190 --> 00:34:44,179
và sau đó vv và vv.

400
00:34:44,179 --> 00:34:52,370
Đối với tôi, với mỗi nhóm đại diện cho những con số này.

401
00:34:52,370 --> 00:34:59,850
Tuy nhiên, nói rằng tôi đã phải vượt qua trong 50, ví dụ.

402
00:34:59,850 --> 00:35:07,490
Nó xuất hiện như là người đầu tiên ba có chứa một loạt các số mười.

403
00:35:07,490 --> 00:35:12,570
Nhưng tôi muốn để cho phép bảng băm của tôi để có trong bất kỳ loại số nguyên,

404
00:35:12,570 --> 00:35:19,860
như vậy thì tôi sẽ phải để lọc ra tất cả các số trên 30 vào nhóm cuối cùng.

405
00:35:19,860 --> 00:35:26,660
Và như vậy thì sẽ dẫn đến một loại bảng băm không cân bằng.

406
00:35:31,330 --> 00:35:35,640
Nói cách khác, một bảng băm chỉ là một mảng của các nhóm

407
00:35:35,640 --> 00:35:38,590
xô hàng là một danh sách liên kết.

408
00:35:38,590 --> 00:35:43,730
Và do đó, để xác định giá trị mỗi đi, mà xô nó đi vào,

409
00:35:43,730 --> 00:35:46,260
bạn sẽ muốn những gì được gọi là một hàm băm

410
00:35:46,260 --> 00:35:55,010
mà phải mất một giá trị và sau đó nói rằng giá trị này tương ứng với một xô nhất định.

411
00:35:55,010 --> 00:36:00,970
Vì vậy, lên phía trên trong ví dụ này, hàm băm của tôi mỗi giá trị.

412
00:36:00,970 --> 00:36:03,020
Kiểm tra xem nó đã được ít hơn 10.

413
00:36:03,020 --> 00:36:05,360
Nếu nó được, nó sẽ đặt nó vào xô đầu tiên.

414
00:36:05,360 --> 00:36:08,910
Nó kiểm tra cho dù đó là ít hơn 20, đặt nó vào thứ hai nếu đúng,

415
00:36:08,910 --> 00:36:12,880
kiểm tra nếu nó ít hơn 30, và sau đó đặt nó vào xô thứ ba,

416
00:36:12,880 --> 00:36:16,990
và sau đó tất cả các khác chỉ rơi vào xô thứ tư.

417
00:36:16,990 --> 00:36:20,110
Vì vậy, bất cứ khi nào bạn có một giá trị, hàm băm của bạn

418
00:36:20,110 --> 00:36:25,420
sẽ đặt giá trị đó vào xô thích hợp.

419
00:36:25,420 --> 00:36:32,430
Hàm băm cơ bản cần biết bạn có bao nhiêu xô.

420
00:36:32,430 --> 00:36:37,960
Kích thước bảng băm của bạn, số lượng thùng mà bạn có,

421
00:36:37,960 --> 00:36:41,190
đó sẽ là một số cố định đó là cho bạn, để bạn quyết định,

422
00:36:41,190 --> 00:36:43,590
nhưng nó sẽ là một con số cố định.

423
00:36:43,590 --> 00:36:51,840
Vì vậy, hàm băm của bạn sẽ được dựa vào đó để xác định xô mỗi phím đi vào

424
00:36:51,840 --> 00:36:54,450
như vậy mà nó phân bố đều.

425
00:36:56,150 --> 00:37:03,820
Tương tự như việc thực hiện của chúng ta về danh sách liên kết, bây giờ tất cả các nút trong bảng băm

426
00:37:03,820 --> 00:37:07,000
thực sự là sẽ có một char.

427
00:37:07,000 --> 00:37:14,340
Vì vậy, chúng tôi có một mảng char từ và sau đó con trỏ khác đến nút tiếp theo,

428
00:37:14,340 --> 00:37:19,010
có ý nghĩa bởi vì nó sẽ là một danh sách liên kết.

429
00:37:19,010 --> 00:37:24,350
Nhớ khi chúng tôi đã có danh sách liên kết, tôi đã thực hiện một đầu nút *

430
00:37:24,350 --> 00:37:31,060
đã được trỏ đến nút đầu tiên trong danh sách liên kết.

431
00:37:31,060 --> 00:37:34,020
Nhưng đối với bảng băm của chúng tôi, bởi vì chúng tôi có nhiều danh sách liên kết,

432
00:37:34,020 --> 00:37:37,520
những gì chúng tôi muốn là chúng tôi muốn bảng băm của chúng tôi được như thế, "một xô là gì?"

433
00:37:37,520 --> 00:37:43,340
Xô chỉ là một danh sách các nút con trỏ,

434
00:37:43,340 --> 00:37:50,620
và do đó, tất cả các phần tử trong xô là thực sự chỉ vào danh sách các liên kết tương ứng.

435
00:37:56,180 --> 00:38:01,520
Để trở lại sơ đồ này, bạn thấy rằng bản thân xô là các mũi tên,

436
00:38:01,520 --> 00:38:06,980
không thực tế các nút.

437
00:38:11,680 --> 00:38:16,420
Một trong những tài sản thiết yếu của hàm băm là họ đang xác định.

438
00:38:16,420 --> 00:38:19,440
Điều đó có nghĩa rằng bất cứ khi nào bạn băm số 2,

439
00:38:19,440 --> 00:38:22,270
nó luôn luôn phải trả lại cùng một thùng.

440
00:38:22,270 --> 00:38:26,440
Mỗi giá trị duy nhất mà đi vào hàm băm, nếu lặp đi lặp lại,

441
00:38:26,440 --> 00:38:29,690
để có được các chỉ số tương tự.

442
00:38:29,690 --> 00:38:34,210
Vì vậy, hàm băm của bạn trả về chỉ số của mảng

443
00:38:34,210 --> 00:38:38,530
nơi mà giá trị đó thuộc về.

444
00:38:38,530 --> 00:38:41,790
Như tôi đã đề cập trước đây, số lượng nhóm là cố định,

445
00:38:41,790 --> 00:38:49,630
và do đó, chỉ số của bạn mà bạn quay trở lại có thể ít hơn so với số lượng nhóm

446
00:38:49,630 --> 00:38:52,680
nhưng lớn hơn 0.

447
00:38:52,680 --> 00:39:00,780
Lý do tại sao chúng tôi có chức năng băm thay vì chỉ một danh sách liên kết đơn

448
00:39:00,780 --> 00:39:09,290
hoặc một mảng là chúng tôi muốn để có thể nhảy đến một phần nhất định một cách dễ dàng nhất

449
00:39:09,290 --> 00:39:11,720
nếu chúng ta biết đặc tính của một giá trị -

450
00:39:11,720 --> 00:39:14,760
thay vì phải tìm kiếm thông qua toàn bộ toàn bộ từ điển,

451
00:39:14,760 --> 00:39:18,320
có thể nhảy đến một phần nhất định của nó.

452
00:39:19,880 --> 00:39:24,440
Hàm băm của bạn nên đưa vào tài khoản mà lý tưởng,

453
00:39:24,440 --> 00:39:28,980
mỗi nhóm có khoảng cùng một số phím.

454
00:39:28,980 --> 00:39:35,040
Kể từ khi bảng băm là một loạt các danh sách liên kết,

455
00:39:35,040 --> 00:39:38,480
sau đó là danh sách liên kết bản thân mình sẽ có nhiều hơn một nút.

456
00:39:38,480 --> 00:39:43,210
Trong ví dụ trước, hai số khác nhau, mặc dù họ đã không bằng nhau,

457
00:39:43,210 --> 00:39:46,950
khi băm, sẽ trở lại cùng một chỉ số.

458
00:39:46,950 --> 00:39:53,620
Vì vậy, khi bạn đang đối phó với các từ, một từ khi băm

459
00:39:53,620 --> 00:39:57,450
sẽ là giá trị hash giống nhau như một từ khác.

460
00:39:57,450 --> 00:40:04,140
Đó là những gì chúng ta gọi là một vụ va chạm, khi chúng ta có một nút, khi băm,

461
00:40:04,140 --> 00:40:09,610
danh sách liên kết thùng đó không phải là sản phẩm nào.

462
00:40:09,610 --> 00:40:14,180
Kỹ thuật mà chúng ta gọi là tuyến tính thăm dò,

463
00:40:14,180 --> 00:40:22,550
nơi bạn đi vào các danh sách liên kết và sau đó tìm nơi bạn muốn chèn nút

464
00:40:22,550 --> 00:40:25,520
bởi vì bạn có một vụ va chạm.

465
00:40:25,520 --> 00:40:28,070
Bạn có thể thấy rằng có thể có một thương mại-off ở đây, phải không?

466
00:40:28,070 --> 00:40:33,760
Nếu bạn có một bảng rất nhỏ băm, một số lượng rất nhỏ của thùng,

467
00:40:33,760 --> 00:40:36,380
sau đó bạn sẽ có rất nhiều va chạm.

468
00:40:36,380 --> 00:40:40,460
Nhưng sau đó nếu bạn thực hiện một bảng rất lớn băm,

469
00:40:40,460 --> 00:40:44,110
bạn có thể sẽ giảm thiểu các va chạm,

470
00:40:44,110 --> 00:40:47,170
nhưng nó sẽ là một dữ liệu rất lớn.

471
00:40:47,170 --> 00:40:49,310
Có sẽ là thương mại-off với điều đó.

472
00:40:49,310 --> 00:40:51,310
Vì vậy, khi bạn đang làm cho pset của bạn, hãy thử để chơi xung quanh

473
00:40:51,310 --> 00:40:54,210
giữa có thể làm cho một bảng băm nhỏ

474
00:40:54,210 --> 00:41:02,100
nhưng sau đó biết rằng nó sẽ mất một chút thời gian để đi qua các yếu tố khác nhau

475
00:41:02,100 --> 00:41:04,270
của những danh sách liên kết.

476
00:41:04,270 --> 00:41:09,500
>> Tải sẽ làm là lặp qua tất cả các từ trong từ điển.

477
00:41:09,500 --> 00:41:13,180
Nó vượt qua trong một con trỏ đến các tập tin từ điển.

478
00:41:13,180 --> 00:41:18,050
Vì vậy, bạn sẽ tận dụng lợi thế của tập tin I / O chức năng mà bạn làm chủ pset4

479
00:41:18,050 --> 00:41:23,010
và duyệt qua tất cả các từ trong từ điển.

480
00:41:23,010 --> 00:41:26,620
Bạn muốn mỗi từ trong từ điển để trở thành một nút mới,

481
00:41:26,620 --> 00:41:32,730
và bạn sẽ đặt mỗi một trong những nút bên trong cấu trúc dữ liệu từ điển của bạn.

482
00:41:32,730 --> 00:41:36,560
Bất cứ khi nào bạn nhận được một từ mới, bạn biết rằng nó sẽ trở thành một nút.

483
00:41:36,560 --> 00:41:46,590
Vì vậy, bạn có thể đi thẳng và malloc một con trỏ nút cho mỗi từ mới mà bạn có.

484
00:41:46,590 --> 00:41:52,610
Ở đây tôi gọi new_node nút con trỏ của tôi và tôi đang mallocing những gì? Kích thước của một node.

485
00:41:52,610 --> 00:41:59,190
Sau đó, để đọc những chuỗi từ một tập tin thực tế, bởi vì từ điển được thực sự được lưu trữ

486
00:41:59,190 --> 00:42:03,340
một từ và sau đó một dòng mới, những gì chúng ta có thể tận dụng

487
00:42:03,340 --> 00:42:06,520
là fscanf chức năng,

488
00:42:06,520 --> 00:42:10,280
theo đó các tập tin là tập tin từ điển mà chúng tôi đang thông qua,

489
00:42:10,280 --> 00:42:18,900
do đó, nó quét các tập tin cho một chuỗi và những nơi mà chuỗi thành đối số cuối cùng.

490
00:42:18,900 --> 00:42:26,890
Nếu bạn nhớ lại trở lại một trong các bài giảng, khi chúng tôi đã đi qua

491
00:42:26,890 --> 00:42:29,320
và loại bóc các lớp trở lại trên thư viện CS50,

492
00:42:29,320 --> 00:42:33,430
chúng ta đã thấy một thực hiện fscanf.

493
00:42:33,430 --> 00:42:37,700
Để trở lại fscanf, chúng tôi có các tập tin mà chúng tôi đang đọc từ,

494
00:42:37,700 --> 00:42:42,570
chúng tôi đang tìm kiếm một chuỗi trong tập tin đó, và sau đó chúng ta đặt nó vào

495
00:42:42,570 --> 00:42:48,340
ở đây tôi có new_node-> từ vì new_node là một con trỏ nút,

496
00:42:48,340 --> 00:42:50,380
không phải là một nút thực tế.

497
00:42:50,380 --> 00:42:57,100
Vì vậy, sau đó tôi nói new_node, tôi muốn đi tới nút mà nó trỏ đến

498
00:42:57,100 --> 00:43:01,190
và sau đó gán giá trị từ.

499
00:43:01,190 --> 00:43:08,540
Chúng tôi muốn để rồi mất từ ​​đó và chèn nó vào bảng băm.

500
00:43:08,540 --> 00:43:13,750
Nhận ra rằng chúng tôi đã thực hiện new_node một con trỏ nút

501
00:43:13,750 --> 00:43:18,230
bởi vì chúng ta sẽ muốn biết địa chỉ của nút đó là những gì

502
00:43:18,230 --> 00:43:23,940
khi chúng ta chèn nó vào bởi vì cấu trúc của bản thân các nút, cấu trúc,

503
00:43:23,940 --> 00:43:26,380
là họ có một con trỏ đến một nút mới.

504
00:43:26,380 --> 00:43:30,820
Vì vậy, sau đó địa chỉ của nút đó để trỏ đến là gì?

505
00:43:30,820 --> 00:43:34,550
Địa chỉ đó sẽ được new_node.

506
00:43:34,550 --> 00:43:42,140
Đó có ý nghĩa, tại sao chúng tôi đang làm new_node * nút như trái ngược với một nút?

507
00:43:43,700 --> 00:43:45,700
Okay.

508
00:43:45,700 --> 00:43:52,840
Chúng tôi có một lời. Đó là giá trị new_node-> từ.

509
00:43:52,840 --> 00:43:55,970
Có chứa một từ trong từ điển mà chúng tôi muốn đầu vào.

510
00:43:55,970 --> 00:44:00,210
Vì vậy, những gì chúng tôi muốn làm là chúng tôi muốn gọi hàm băm của chúng tôi trên chuỗi đó

511
00:44:00,210 --> 00:44:03,780
bởi vì hàm băm của chúng tôi có trong một chuỗi và sau đó trả về cho chúng tôi một số nguyên,

512
00:44:03,780 --> 00:44:12,090
số nguyên đó là chỉ số hashtable tại chỉ số đó đại diện cho rằng xô.

513
00:44:12,090 --> 00:44:18,260
Chúng tôi muốn đi mà chỉ số và sau đó đi rằng chỉ số của bảng băm

514
00:44:18,260 --> 00:44:26,960
và sau đó sử dụng danh sách liên kết để chèn các nút new_node.

515
00:44:26,960 --> 00:44:31,950
Hãy nhớ rằng tuy nhiên bạn quyết định để chèn nút của bạn,

516
00:44:31,950 --> 00:44:34,370
cho dù đó là ở giữa nếu bạn muốn sắp xếp nó

517
00:44:34,370 --> 00:44:39,650
hoặc ở đầu hoặc ở cuối, chỉ cần đảm bảo rằng nút cuối cùng của bạn luôn luôn chỉ là NULL

518
00:44:39,650 --> 00:44:46,730
bởi vì đó là cách duy nhất mà chúng ta biết nơi mà các phần tử cuối cùng của danh sách liên kết của chúng tôi.

519
00:44:50,790 --> 00:44:59,710
>> Nếu kích thước là một số nguyên đại diện cho số lượng từ trong một từ điển,

520
00:44:59,710 --> 00:45:03,060
sau đó một trong những cách để làm điều này là bất cứ khi nào kích thước được gọi là

521
00:45:03,060 --> 00:45:05,840
chúng tôi đi qua mọi phần tử trong bảng băm của chúng tôi

522
00:45:05,840 --> 00:45:09,410
và sau đó lặp qua tất cả các danh sách liên kết trong bảng băm

523
00:45:09,410 --> 00:45:13,770
và sau đó tính toán chiều dài đó, tăng 1 truy cập của chúng tôi bằng 1.

524
00:45:13,770 --> 00:45:16,580
Nhưng mỗi khi kích thước được gọi là, sẽ mất một thời gian dài

525
00:45:16,580 --> 00:45:22,120
bởi vì chúng ta sẽ là tuyến tính thăm dò tất cả các danh sách liên kết duy nhất.

526
00:45:22,120 --> 00:45:30,530
Thay vào đó, nó sẽ dễ dàng hơn nhiều nếu bạn theo dõi bao nhiêu từ được thông qua.

527
00:45:30,530 --> 00:45:36,330
Vì vậy, sau đó nếu bạn bao gồm một truy cập trong phạm vi chức năng tải của bạn

528
00:45:36,330 --> 00:45:42,430
cập nhật khi cần thiết, sau đó truy cập, nếu bạn đặt nó vào một biến toàn cầu,

529
00:45:42,430 --> 00:45:44,930
sẽ có thể được truy cập bằng cách kích thước.

530
00:45:44,930 --> 00:45:51,450
Vì vậy, những gì kích thước chỉ có thể làm trong một dòng, chỉ cần trả về giá trị truy cập,

531
00:45:51,450 --> 00:45:55,500
kích thước của từ điển, mà bạn đã xử lý trong tải.

532
00:45:55,500 --> 00:46:05,190
Đó là những gì tôi có nghĩa là khi tôi nói rằng nếu bạn thực hiện tải một cách hữu ích,

533
00:46:05,190 --> 00:46:08,540
sau đó kích thước là có được khá dễ dàng.

534
00:46:08,540 --> 00:46:11,350
>> Vì vậy, bây giờ chúng tôi nhận được để kiểm tra.

535
00:46:11,350 --> 00:46:15,960
Bây giờ chúng ta đang đối phó với những lời từ các tập tin văn bản nhập vào,

536
00:46:15,960 --> 00:46:19,910
và do đó, chúng ta sẽ kiểm tra xem tất cả của những từ đầu vào

537
00:46:19,910 --> 00:46:22,520
thực sự có trong từ điển hay không.

538
00:46:22,520 --> 00:46:26,520
Tương tự như Scramble, chúng tôi muốn cho phép trường hợp vô cảm.

539
00:46:26,520 --> 00:46:32,110
Bạn muốn đảm bảo rằng tất cả các từ thông qua tại, mặc dù họ đang hỗn hợp trường hợp,

540
00:46:32,110 --> 00:46:37,840
khi được gọi với so sánh chuỗi, là tương đương.

541
00:46:37,840 --> 00:46:42,450
Những từ trong các tập tin văn bản từ điển thực sự là tất cả các chữ thường.

542
00:46:42,450 --> 00:46:49,280
Một điều nữa là bạn có thể giả định rằng tất cả các từ thông qua, mỗi chuỗi,

543
00:46:49,280 --> 00:46:53,200
sẽ được, hoặc chữ cái hoặc chứa các dấu nháy.

544
00:46:53,200 --> 00:46:58,010
Apostrophes đang có được từ hợp lệ trong từ điển của chúng tôi.

545
00:46:58,010 --> 00:47:06,470
Vì vậy, nếu bạn có một từ với dấu nháy đơn S, đó là một từ hợp pháp thực tế trong từ điển của bạn

546
00:47:06,470 --> 00:47:11,650
đó sẽ là một trong các nút trong bảng băm của bạn.

547
00:47:13,470 --> 00:47:18,350
Kiểm tra hoạt động nếu từ đó tồn tại, sau đó nó đã nhận được trong bảng băm của chúng tôi.

548
00:47:18,350 --> 00:47:22,210
Nếu từ đó trong từ điển, sau đó tất cả các từ có trong từ điển trong bảng băm,

549
00:47:22,210 --> 00:47:26,560
do đó, chúng ta hãy tìm từ này trong bảng băm.

550
00:47:26,560 --> 00:47:29,250
Chúng ta biết rằng kể từ khi chúng tôi thực hiện hàm băm của chúng tôi

551
00:47:29,250 --> 00:47:38,420
như vậy mà mỗi một từ duy nhất là luôn luôn băm với cùng một giá trị,

552
00:47:38,420 --> 00:47:43,340
sau đó chúng ta biết rằng thay vì tìm kiếm thông qua toàn bộ bảng băm của chúng tôi toàn bộ,

553
00:47:43,340 --> 00:47:48,310
chúng tôi thực sự có thể tìm thấy danh sách liên kết mà từ đó phải thuộc về.

554
00:47:48,310 --> 00:47:51,850
Nếu nó đã có trong từ điển, sau đó nó sẽ được trong thùng đó.

555
00:47:51,850 --> 00:47:57,140
Những gì chúng tôi có thể làm, nếu từ đó là tên của chuỗi của chúng tôi thông qua tại,

556
00:47:57,140 --> 00:48:01,560
chúng ta có thể chỉ cần băm từ đó và nhìn vào danh sách liên kết

557
00:48:01,560 --> 00:48:06,410
giá trị của hashtable [hash (word)].

558
00:48:06,410 --> 00:48:12,410
Từ đó, những gì chúng ta có thể làm là chúng tôi có một nhóm nhỏ hơn của các nút để tìm kiếm các từ này,

559
00:48:12,410 --> 00:48:16,770
và vì vậy chúng tôi có thể đi qua các danh sách liên kết, bằng cách sử dụng một ví dụ từ trước đó trong các hương,

560
00:48:16,770 --> 00:48:24,110
và sau đó gọi chuỗi so sánh khi từ bất cứ nơi nào con trỏ đang trỏ đến,

561
00:48:24,110 --> 00:48:28,430
từ đó, và xem liệu những so sánh.

562
00:48:30,280 --> 00:48:35,110
Tùy thuộc vào cách mà bạn tổ chức hàm băm của bạn,

563
00:48:35,110 --> 00:48:39,260
nếu nó được sắp xếp, bạn có thể có thể trở lại sai sớm hơn một chút,

564
00:48:39,260 --> 00:48:43,440
nhưng nếu nó không được phân loại, sau đó bạn muốn tiếp tục vượt qua thông qua danh sách liên kết của bạn

565
00:48:43,440 --> 00:48:46,480
cho đến khi bạn tìm thấy những yếu tố cuối cùng của danh sách.

566
00:48:46,480 --> 00:48:53,320
Và nếu bạn vẫn không tìm thấy từ thời gian bạn đã đạt đến kết thúc của danh sách liên kết,

567
00:48:53,320 --> 00:48:56,890
điều đó có nghĩa là từ đó không tồn tại trong từ điển,

568
00:48:56,890 --> 00:48:59,410
và do đó, từ đó là không hợp lệ,

569
00:48:59,410 --> 00:49:02,730
và kiểm tra trả về false.

570
00:49:02,730 --> 00:49:09,530
>> Bây giờ chúng ta đến để dỡ bỏ, nơi chúng tôi muốn giải phóng tất cả các nút mà chúng tôi đã malloc'd

571
00:49:09,530 --> 00:49:14,050
miễn phí tất cả các nút bên trong của bảng băm của chúng tôi.

572
00:49:14,050 --> 00:49:20,270
Chúng tôi sẽ muốn để lặp lại trên tất cả các danh sách liên kết và miễn phí tất cả các nút trong đó.

573
00:49:20,270 --> 00:49:29,350
Nếu bạn nhìn ở trên trong hương các ví dụ nơi mà chúng ta giải phóng một danh sách liên kết,

574
00:49:29,350 --> 00:49:35,140
sau đó bạn sẽ muốn lặp lại quá trình cho mọi phần tử trong bảng băm.

575
00:49:35,140 --> 00:49:37,780
Và tôi sẽ đi qua vào cuối của hương,

576
00:49:37,780 --> 00:49:46,600
nhưng Valgrind là một công cụ mà bạn có thể thấy nếu bạn đã giải phóng

577
00:49:46,600 --> 00:49:53,600
tất cả các nút mà bạn đã malloc'd hoặc bất cứ điều gì khác mà bạn đã malloc'd, bất kỳ con trỏ khác.

578
00:49:55,140 --> 00:50:00,530
Vì vậy đó là bảng băm, nơi chúng tôi có một số hữu hạn xô

579
00:50:00,530 --> 00:50:09,220
và một hàm băm mà sẽ mất một giá trị và sau đó gán giá trị đó để một xô nhất định.

580
00:50:09,220 --> 00:50:13,340
>> Bây giờ chúng ta cố gắng.

581
00:50:13,340 --> 00:50:18,750
Cố gắng loại giống như thế này, và tôi cũng sẽ vẽ ra một ví dụ.

582
00:50:18,750 --> 00:50:25,630
Về cơ bản, bạn có một mảng toàn bộ thư tiềm năng,

583
00:50:25,630 --> 00:50:29,210
và sau đó bất cứ khi nào bạn đang xây dựng một từ,

584
00:50:29,210 --> 00:50:36,490
thư có thể liên kết một từ điển để một loạt các khả năng.

585
00:50:36,490 --> 00:50:40,840
Một số từ bắt đầu với C, nhưng sau đó tiếp tục với A,

586
00:50:40,840 --> 00:50:42,960
nhưng những người khác tiếp tục với O, ví dụ.

587
00:50:42,960 --> 00:50:51,090
Trie là một cách hình dung tất cả các kết hợp có thể có của những từ đó.

588
00:50:51,090 --> 00:50:59,070
Một Trie để theo dõi các trình tự của các chữ cái mà bao gồm từ,

589
00:50:59,070 --> 00:51:08,280
nhánh ra khi cần thiết, khi thư có thể được theo sau bởi một nhiều của các chữ cái,

590
00:51:08,280 --> 00:51:16,630
và cuối cùng cho thấy tại mỗi điểm cho dù từ đó là hợp lệ hay không

591
00:51:16,630 --> 00:51:30,120
bởi vì nếu bạn đang đánh vần MAT từ, MA Tôi không nghĩ là một từ hợp lệ, nhưng MAT là.

592
00:51:30,120 --> 00:51:37,820
Và như vậy trong Trie của bạn, nó sẽ chỉ ra rằng sau khi MAT đó thực sự là một từ hợp lệ.

593
00:51:41,790 --> 00:51:48,590
Mỗi nút trong Trie của chúng tôi thực sự là sẽ chứa một mảng của các con trỏ nút,

594
00:51:48,590 --> 00:51:52,970
và chúng ta sẽ có, cụ thể, 27 của những người con trỏ nút,

595
00:51:52,970 --> 00:52:00,550
một cho mỗi chữ trong bảng chữ cái cũng như các ký tự dấu nháy đơn.

596
00:52:00,550 --> 00:52:10,450
Mỗi phần tử trong mảng đó để trỏ đến một nút khác.

597
00:52:10,450 --> 00:52:14,020
Vì vậy, nếu nút đó là NULL, nếu không có gì sau đó,

598
00:52:14,020 --> 00:52:20,550
sau đó chúng tôi biết rằng có thêm không có chữ cái trong chuỗi từ.

599
00:52:20,550 --> 00:52:26,950
Nhưng nếu nút đó không phải là NULL, đó có nghĩa là có chữ hơn trong chuỗi thư.

600
00:52:26,950 --> 00:52:32,160
Và sau đó hơn nữa, mỗi nút chỉ ra cho dù đó là ký tự cuối cùng của một từ hay không.

601
00:52:38,110 --> 00:52:43,170
>> Chúng ta hãy đi vào một ví dụ về Trie.

602
00:52:50,500 --> 00:52:58,340
Đầu tiên tôi có chỗ cho 27 nút trong mảng này.

603
00:52:58,340 --> 00:53:03,200
Nếu tôi có BAR từ -

604
00:53:13,310 --> 00:53:15,370
Nếu tôi có BAR từ và tôi muốn để chèn trong,

605
00:53:15,370 --> 00:53:22,700
chữ cái đầu tiên là B, vì vậy nếu Trie của tôi là trống rỗng,

606
00:53:22,700 --> 00:53:29,910
B là lá thư thứ hai của bảng chữ cái, vì vậy tôi sẽ chọn đặt này ở đây chỉ số này.

607
00:53:29,910 --> 00:53:33,450
Tôi sẽ có B ở đây.

608
00:53:33,450 --> 00:53:42,400
B là có được một nút trỏ tới một mảng của tất cả các ký tự có thể khác

609
00:53:42,400 --> 00:53:45,870
có thể theo sau khi lá thư B.

610
00:53:45,870 --> 00:53:57,610
Trong trường hợp này, tôi đang đối phó với BAR từ, do đó, A sẽ đi đây.

611
00:54:02,000 --> 00:54:08,990
A, tôi có chữ R, do đó, sau đó tại điểm kết hợp của riêng của nó,

612
00:54:08,990 --> 00:54:15,120
và sau đó R sẽ có mặt ở đây.

613
00:54:15,120 --> 00:54:22,470
BAR là một từ hoàn chỉnh, vì vậy sau đó tôi sẽ có R điểm nút khác

614
00:54:22,470 --> 00:54:33,990
nói rằng từ đó là hợp lệ.

615
00:54:36,010 --> 00:54:40,970
Nút đó cũng sẽ có một mảng của các nút,

616
00:54:40,970 --> 00:54:45,260
nhưng những người có thể là NULL.

617
00:54:45,260 --> 00:54:49,080
Nhưng về cơ bản, nó có thể tiếp tục như thế.

618
00:54:49,080 --> 00:54:54,250
Điều đó sẽ trở thành một chút rõ ràng hơn khi chúng tôi đi vào một ví dụ khác,

619
00:54:54,250 --> 00:54:56,780
do đó, chỉ cần chịu với tôi.

620
00:54:56,780 --> 00:55:02,050
Bây giờ chúng tôi có BAR bên trong từ điển của chúng tôi.

621
00:55:02,050 --> 00:55:05,980
Bây giờ nói rằng chúng ta có Baz từ.

622
00:55:05,980 --> 00:55:12,630
Chúng tôi bắt đầu với B, và chúng tôi đã có B là một trong các chữ cái trong từ điển của chúng tôi.

623
00:55:12,630 --> 00:55:15,170
Đó là theo sau với A. Chúng tôi đã có A.

624
00:55:15,170 --> 00:55:19,250
Nhưng sau đó thay vào đó, chúng ta có Z sau đây.

625
00:55:19,250 --> 00:55:25,490
Vì vậy, sau đó một phần tử trong mảng của chúng tôi là có được Z,

626
00:55:25,490 --> 00:55:30,810
và như vậy thì đó là một trong những sẽ để trỏ đến một kết thúc hợp lệ khác của từ này.

627
00:55:30,810 --> 00:55:36,930
Vì vậy, chúng ta thấy rằng khi chúng tôi tiếp tục qua B và sau đó,

628
00:55:36,930 --> 00:55:43,480
có hai tùy chọn khác nhau hiện đang có trong từ điển của chúng tôi cho những từ bắt đầu với B và A.

629
00:55:49,650 --> 00:55:57,460
Nói rằng chúng tôi muốn để chèn FOOBAR từ.

630
00:55:57,460 --> 00:56:05,620
Sau đó, chúng tôi sẽ thực hiện một mục tại F.

631
00:56:05,620 --> 00:56:11,320
F là một nút chỉ vào một mảng toàn.

632
00:56:11,320 --> 00:56:22,790
Chúng tôi sẽ tìm thấy O, O, O sau đó liên kết đến một danh sách toàn.

633
00:56:22,790 --> 00:56:35,340
Chúng ta sẽ có B và sau đó tiếp tục, chúng tôi phải A và sau đó R.

634
00:56:35,340 --> 00:56:43,570
Vì vậy, sau đó đi qua FOOBAR tất cả các con đường xuống cho đến khi FOOBAR là một từ chính xác.

635
00:56:43,570 --> 00:56:52,590
Và như vậy thì đây sẽ là một từ hợp lệ.

636
00:56:52,590 --> 00:57:00,170
Bây giờ nói từ kế tiếp của chúng tôi trong từ điển thực sự là FOO từ.

637
00:57:00,170 --> 00:57:03,530
Chúng tôi sẽ nói F. gì sau F?

638
00:57:03,530 --> 00:57:06,190
Tôi thực sự đã có một không gian cho O, vì vậy tôi sẽ tiếp tục.

639
00:57:06,190 --> 00:57:09,150
Tôi không cần phải thực hiện một hình mới. Tiếp tục.

640
00:57:09,150 --> 00:57:15,500
FOO là một từ hợp lệ trong từ điển này, do đó, sau đó tôi sẽ để cho biết

641
00:57:15,500 --> 00:57:21,660
rằng đó là hợp lệ.

642
00:57:21,660 --> 00:57:28,370
Nếu tôi dừng lại trình tự của tôi ở đó, đó sẽ là chính xác.

643
00:57:28,370 --> 00:57:33,050
Nhưng nếu chúng ta tiếp tục trình tự của chúng tôi từ FOO xuống đến B

644
00:57:33,050 --> 00:57:39,750
và chỉ có FOOB, FOOB không phải là một từ, và đó là không được chỉ định như là một một hợp lệ.

645
00:57:47,370 --> 00:57:57,600
Trong Trie, bạn có tất cả các nút cho thấy cho dù đó là một từ hợp lệ hay không,

646
00:57:57,600 --> 00:58:05,840
và sau đó mỗi node cũng có một mảng 27 con trỏ nút

647
00:58:05,840 --> 00:58:09,520
mà sau đó trỏ đến các nút tự.

648
00:58:09,520 --> 00:58:12,940
>> Đây là một cách làm thế nào bạn có thể muốn xác định điều này.

649
00:58:12,940 --> 00:58:17,260
Tuy nhiên, giống như trong ví dụ bảng băm, nơi chúng tôi có một cái đầu * nút

650
00:58:17,260 --> 00:58:21,320
để cho biết sự khởi đầu của danh sách liên kết của chúng tôi, chúng tôi cũng sẽ muốn

651
00:58:21,320 --> 00:58:29,150
một số cách để biết nơi bắt đầu của Trie của chúng tôi là.

652
00:58:29,150 --> 00:58:34,110
Một số người gọi những người cố gắng cây, và đó là nơi gốc đến từ.

653
00:58:34,110 --> 00:58:36,910
Vì vậy, chúng tôi muốn gốc rễ của cây của chúng tôi để đảm bảo rằng chúng tôi ở lại căn cứ

654
00:58:36,910 --> 00:58:39,570
bất cứ nơi nào Trie của chúng tôi là.

655
00:58:42,910 --> 00:58:46,300
Chúng tôi đã loại đã đi qua

656
00:58:46,300 --> 00:58:50,240
cách bạn có thể nghĩ về tải mỗi từ vào từ điển.

657
00:58:50,240 --> 00:58:54,540
Về cơ bản, cho mỗi từ, bạn sẽ muốn để lặp qua Trie của bạn

658
00:58:54,540 --> 00:58:59,590
và biết rằng mọi phần tử trong những đứa trẻ - chúng tôi gọi nó là trẻ em trong trường hợp này -

659
00:58:59,590 --> 00:59:04,290
tương ứng với một lá thư khác nhau, bạn sẽ muốn kiểm tra những giá trị

660
00:59:04,290 --> 00:59:08,320
rằng chỉ số cụ thể tương ứng với chữ cái.

661
00:59:08,320 --> 00:59:11,260
Vì vậy, suy nghĩ tất cả các cách trở lại Caesar và Vigenere,

662
00:59:11,260 --> 00:59:16,070
biết rằng mỗi lá thư, bạn có thể loại bản đồ trở lại một chỉ số theo thứ tự abc,

663
00:59:16,070 --> 00:59:20,690
chắc chắn từ A đến Z là có được khá dễ dàng để bản đồ đến một chữ cái,

664
00:59:20,690 --> 00:59:25,200
nhưng không may, dấu nháy cũng là một nhân vật được chấp nhận trong các từ.

665
00:59:25,200 --> 00:59:31,650
Tôi thậm chí không chắc chắn những gì giá trị ASCII,

666
00:59:31,650 --> 00:59:39,250
cho rằng nếu bạn muốn tìm một chỉ số để quyết định xem bạn muốn nó được hoặc là một trong những đầu tiên

667
00:59:39,250 --> 00:59:44,550
hoặc một trong những cuối cùng, bạn sẽ phải thực hiện một kiểm tra cứng mã hóa cho điều đó

668
00:59:44,550 --> 00:59:48,930
và sau đó đưa rằng trong 26 chỉ số, ví dụ.

669
00:59:48,930 --> 00:59:55,300
Vì vậy, sau đó bạn đang kiểm tra giá trị ở trẻ em [i]

670
00:59:55,300 --> 00:59:58,400
[i] tương ứng với bất kỳ bức thư bạn đang ở.

671
00:59:58,400 --> 01:00:04,110
Nếu đó là NULL, điều đó có nghĩa rằng không có bất cứ lá thư nào có thể

672
01:00:04,110 --> 01:00:08,150
bắt nguồn từ đó trình tự trước đó, vì vậy bạn sẽ muốn để malloc

673
01:00:08,150 --> 01:00:13,150
và thực hiện một nút mới và rằng trẻ em [i] trỏ đến nó

674
01:00:13,150 --> 01:00:17,890
để bạn tạo ra - khi chúng ta chèn một ký tự vào hình chữ nhật -

675
01:00:17,890 --> 01:00:23,680
làm cho trẻ không NULL và điểm vào nút đó mới.

676
01:00:23,680 --> 01:00:28,340
Nhưng nếu đó không phải là NULL, như trong trường hợp của chúng tôi FOO

677
01:00:28,340 --> 01:00:34,570
khi chúng tôi đã có FOOBAR, chúng tôi tiếp tục,

678
01:00:34,570 --> 01:00:44,010
và chúng tôi không bao giờ làm cho một nút mới mà chỉ thiết lập is_word đúng sự thật

679
01:00:44,010 --> 01:00:47,790
ở cuối của từ đó.

680
01:00:50,060 --> 01:00:55,340
>> Vì vậy, sau đó như trước đây, vì ở đây bạn đang làm việc với mỗi thư tại một thời điểm,

681
01:00:55,340 --> 01:01:01,470
nó sẽ được dễ dàng hơn cho bạn cho kích thước, thay vì phải tính toán

682
01:01:01,470 --> 01:01:06,910
và đi qua toàn bộ cây và tính toán để tôi có bao nhiêu trẻ em

683
01:01:06,910 --> 01:01:10,850
và sau đó phân nhánh ra, nhớ bao nhiêu là ở phía bên trái và bên phải

684
01:01:10,850 --> 01:01:12,850
và những thứ như thế, nó sẽ được dễ dàng hơn nhiều cho bạn

685
01:01:12,850 --> 01:01:16,220
nếu bạn chỉ theo dõi bao nhiêu từ bạn đang thêm trong

686
01:01:16,220 --> 01:01:18,080
khi bạn đang làm việc với tải.

687
01:01:18,080 --> 01:01:22,630
Và như vậy thì cách thức rằng kích thước chỉ có thể trả về một biến toàn cầu của kích thước.

688
01:01:25,320 --> 01:01:28,530
>> Bây giờ chúng tôi đến để kiểm tra.

689
01:01:28,530 --> 01:01:33,920
Cùng một tiêu chuẩn như trước đây, mà chúng tôi muốn cho phép trường hợp vô cảm.

690
01:01:33,920 --> 01:01:40,400
Là tốt, chúng tôi giả định rằng các dây chỉ là các ký tự chữ cái hoặc dấu nháy

691
01:01:40,400 --> 01:01:44,000
vì trẻ em là một mảng của 27 dài,

692
01:01:44,000 --> 01:01:48,480
do đó, tất cả các chữ cái của bảng chữ cái cộng với dấu lược.

693
01:01:48,480 --> 01:01:53,800
Đối với kiểm tra những gì bạn sẽ muốn làm là bạn sẽ muốn bắt đầu ở gốc

694
01:01:53,800 --> 01:01:58,440
bởi vì gốc rễ sẽ trỏ đến một mảng có chứa

695
01:01:58,440 --> 01:02:01,630
tất cả đều bắt đầu từ chữ cái có thể của một từ.

696
01:02:01,630 --> 01:02:03,680
Bạn sẽ bắt đầu ở đó,

697
01:02:03,680 --> 01:02:11,590
và sau đó bạn sẽ phải kiểm tra giá trị NULL hay không,

698
01:02:11,590 --> 01:02:16,490
bởi vì nếu giá trị là NULL, có nghĩa là từ điển không có bất kỳ giá trị

699
01:02:16,490 --> 01:02:21,480
có chứa lá thư đó theo thứ tự cụ thể.

700
01:02:21,480 --> 01:02:24,970
Nếu nó NULL, thì đó có nghĩa rằng từ này bị sai chính tả ngay lập tức.

701
01:02:24,970 --> 01:02:27,110
Nhưng nếu nó không phải là NULL, sau đó bạn có thể tiếp tục,

702
01:02:27,110 --> 01:02:34,090
nói rằng chữ cái đầu tiên là chữ cái đầu tiên có thể có trong một từ,

703
01:02:34,090 --> 01:02:40,630
vì vậy bây giờ tôi muốn kiểm tra nếu thư thứ hai, trình tự đó, trong từ điển của tôi.

704
01:02:40,630 --> 01:02:46,540
Vì vậy, bạn sẽ phải đi đến các chỉ số của các con của nút đầu tiên

705
01:02:46,540 --> 01:02:50,720
và kiểm tra xem lá thư thứ hai tồn tại.

706
01:02:50,720 --> 01:02:57,440
Sau đó, bạn lặp lại quá trình để kiểm tra xem chuỗi đó là hợp lệ hay không

707
01:02:57,440 --> 01:02:59,060
trong Trie của bạn.

708
01:02:59,060 --> 01:03:06,430
Bất cứ khi nào con cái nút đó điểm NULL,

709
01:03:06,430 --> 01:03:10,710
bạn biết rằng chuỗi không tồn tại,

710
01:03:10,710 --> 01:03:16,230
nhưng sau đó nếu bạn đến cuối của từ mà bạn đã đầu vào,

711
01:03:16,230 --> 01:03:20,070
sau đó bạn muốn kiểm tra ngay bây giờ mà tôi đã hoàn thành trình tự này

712
01:03:20,070 --> 01:03:27,610
và thấy nó trong Trie tôi, là từ hợp lệ hay không?

713
01:03:27,610 --> 01:03:32,480
Và như vậy sau đó bạn muốn kiểm tra, và đó là khi nếu bạn đã tìm thấy trình tự đó,

714
01:03:32,480 --> 01:03:35,120
sau đó bạn muốn kiểm tra xem từ đó là hợp lệ hay không

715
01:03:35,120 --> 01:03:40,290
bởi vì nhớ lại trong trường hợp trước mà tôi đã vẽ mà chúng tôi đã FOOB,

716
01:03:40,290 --> 01:03:48,410
đó là một chuỗi hợp lệ mà chúng tôi tìm thấy nhưng không phải là một thực tế hợp lệ từ chính nó.

717
01:03:50,570 --> 01:03:59,000
>> Tương tự như vậy, để dỡ bỏ trong cố gắng bạn muốn dỡ bỏ tất cả các nút trong Trie của bạn.

718
01:03:59,000 --> 01:04:04,790
Xin lôi. Tương tự như các bảng băm trong dỡ bỏ, chúng tôi đã giải phóng tất cả các nút,

719
01:04:04,790 --> 01:04:09,740
trong cố gắng chúng tôi cũng muốn giải phóng tất cả các nút.

720
01:04:09,740 --> 01:04:15,000
Dỡ bỏ thực sự sẽ làm việc dễ dàng nhất từ ​​dưới lên trên

721
01:04:15,000 --> 01:04:19,290
bởi vì đây là danh sách cơ bản liên kết.

722
01:04:19,290 --> 01:04:22,540
Vì vậy, chúng tôi muốn chắc chắn rằng chúng tôi tổ chức cho tất cả các giá trị

723
01:04:22,540 --> 01:04:25,700
và miễn phí tất cả trong số họ một cách rõ ràng.

724
01:04:25,700 --> 01:04:28,840
Những gì bạn sẽ muốn làm gì nếu bạn đang làm việc với một Trie

725
01:04:28,840 --> 01:04:35,640
là để đi du lịch để dưới cùng và nút thấp nhất có thể miễn phí đầu tiên

726
01:04:35,640 --> 01:04:39,190
và sau đó đi lên cho tất cả những đứa trẻ và sau đó tất cả những người,

727
01:04:39,190 --> 01:04:43,050
đi lên và sau đó miễn phí, vv

728
01:04:43,050 --> 01:04:48,790
Loại giống như đối phó với lớp dưới cùng những người đầu tiên Trie

729
01:04:48,790 --> 01:04:51,940
và sau đó đi lên trên một khi bạn đã giải thoát tất cả mọi thứ.

730
01:04:51,940 --> 01:04:56,720
Đây là một ví dụ tốt về chức năng đệ quy có thể có ích.

731
01:04:56,720 --> 01:05:03,830
Một khi bạn đã trả tự do cho lớp dưới cùng của Trie của bạn,

732
01:05:03,830 --> 01:05:08,000
sau đó bạn gọi dỡ bỏ phần còn lại của nó,

733
01:05:08,000 --> 01:05:13,620
làm cho chắc chắn rằng bạn tự do mỗi nhỏ -

734
01:05:13,620 --> 01:05:16,410
Loại có thể hình dung nó như là cố gắng nhỏ.

735
01:05:23,300 --> 01:05:28,990
Vì vậy, bạn có gốc của bạn ở đây.

736
01:05:30,840 --> 01:05:35,230
Tôi chỉ đơn giản hóa nó vì vậy tôi không phải rút ra 26 trong số họ.

737
01:05:37,250 --> 01:05:43,770
Vì vậy, bạn có này, và sau đó các đại diện cho các trình tự của các từ

738
01:05:43,770 --> 01:05:54,620
nơi mà tất cả các vòng tròn nhỏ là những chữ cái chuỗi giá trị của các chữ cái.

739
01:06:03,040 --> 01:06:07,160
Hãy tiếp tục nhiều hơn một chút.

740
01:06:15,110 --> 01:06:25,750
Những gì bạn sẽ muốn làm là miễn phí dưới đây và sau đó miễn phí này

741
01:06:25,750 --> 01:06:31,640
và sau đó miễn phí này ở phía dưới trước khi bạn giải phóng một trong những đầu lên ở đây

742
01:06:31,640 --> 01:06:38,180
bởi vì nếu bạn một cái gì đó ở cấp độ thứ hai ở đây,

743
01:06:38,180 --> 01:06:47,230
sau đó bạn thực sự sẽ mất giá trị này ở đây.

744
01:06:47,230 --> 01:06:54,780
Đó là lý do tại sao điều quan trọng là dỡ bỏ cho một Trie để làm cho chắc chắn rằng bạn tự do dưới cùng đầu tiên.

745
01:06:54,780 --> 01:06:59,480
Những gì bạn có thể muốn làm là nói cho tất cả các nút

746
01:06:59,480 --> 01:07:06,430
Tôi muốn để dỡ bỏ tất cả các em.

747
01:07:16,060 --> 01:07:22,140
>> Bây giờ chúng ta đã đi qua dỡ bỏ bảng băm cho phương pháp cũng như phương pháp Trie,

748
01:07:22,140 --> 01:07:27,020
chúng ta sẽ muốn nhìn vào Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind bạn chạy với các lệnh sau đây.

750
01:07:29,640 --> 01:07:32,700
Bạn có valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Bạn đang kiểm tra cho tất cả các rò rỉ khi bạn chạy speller cho văn bản này nhất định

752
01:07:40,960 --> 01:07:46,980
vì speller cần phải có trong một tập tin văn bản.

753
01:07:46,980 --> 01:07:52,330
Vì vậy, Valgrind sẽ chạy chương trình của bạn, cho bạn biết có bao nhiêu byte bạn được giao,

754
01:07:52,330 --> 01:07:57,150
bao nhiêu byte bạn giải phóng, và nó sẽ cho bạn cho dù bạn giải phóng vừa đủ

755
01:07:57,150 --> 01:07:58,930
hoặc cho dù bạn không đủ tự do,

756
01:07:58,930 --> 01:08:02,850
hoặc đôi khi bạn có thể thậm chí còn hơn, như miễn phí một nút đã được trả tự do

757
01:08:02,850 --> 01:08:05,140
và do đó, nó sẽ trở lại lỗi.

758
01:08:05,140 --> 01:08:11,600
Nếu bạn sử dụng Valgrind, nó sẽ cho bạn một số thông điệp

759
01:08:11,600 --> 01:08:15,970
chỉ ra cho dù bạn đã giải phóng hoặc làm việc ít hơn, đủ, vừa đủ,

760
01:08:15,970 --> 01:08:19,609
hoặc nhiều hơn đủ thời gian.

761
01:08:24,370 --> 01:08:30,410
>> Một phần của pset này, đó là tùy chọn để thách thức Ban Big.

762
01:08:30,410 --> 01:08:35,790
Nhưng khi chúng ta đang đối phó với các cấu trúc dữ liệu

763
01:08:35,790 --> 01:08:40,689
nó là loại thú vị để xem cấu trúc dữ liệu của bạn có thể là một cách nhanh chóng và hiệu quả.

764
01:08:40,689 --> 01:08:44,490
Băm kết quả trong rất nhiều va chạm chức năng của bạn?

765
01:08:44,490 --> 01:08:46,300
Hoặc là kích thước dữ liệu của bạn thực sự lớn?

766
01:08:46,300 --> 01:08:49,420
Liệu nó mất rất nhiều thời gian để đi qua?

767
01:08:49,420 --> 01:08:54,800
Trong nhật ký của speller, kết quả đầu ra bao nhiêu thời gian bạn sử dụng để tải,

768
01:08:54,800 --> 01:08:57,700
để kiểm tra, tiến hành kích thước, và dỡ bỏ,

769
01:08:57,700 --> 01:09:00,720
và do đó, những được đăng trong Ban Big,

770
01:09:00,720 --> 01:09:03,600
nơi bạn có thể cạnh tranh với các bạn cùng lớp của bạn

771
01:09:03,600 --> 01:09:11,350
và một số nhân viên để xem ai có nhanh nhất kiểm tra chính tả.

772
01:09:11,350 --> 01:09:14,760
Một điều mà tôi muốn lưu ý về các bảng băm

773
01:09:14,760 --> 01:09:20,470
là có một số chức năng khá đơn giản băm mà chúng ta có thể nghĩ ra.

774
01:09:20,470 --> 01:09:27,240
Ví dụ, bạn có 26 thùng, mỗi thùng

775
01:09:27,240 --> 01:09:30,200
tương ứng với chữ cái đầu tiên trong một từ,

776
01:09:30,200 --> 01:09:35,229
nhưng đó là đi đến kết quả trong một bảng băm khá cân bằng

777
01:09:35,229 --> 01:09:40,979
bởi vì có những từ ít hơn rất nhiều bắt đầu với X vì bắt đầu với M, ví dụ.

778
01:09:40,979 --> 01:09:47,890
Một cách để đi về speller là nếu bạn muốn để có được tất cả các chức năng khác xuống,

779
01:09:47,890 --> 01:09:53,240
sau đó chỉ cần sử dụng một hàm băm đơn giản để có thể để có được mã của bạn đang chạy

780
01:09:53,240 --> 01:09:58,650
và sau đó quay trở lại và thay đổi kích thước của bảng băm của bạn và định nghĩa.

781
01:09:58,650 --> 01:10:03,430
Có rất nhiều tài nguyên trên Internet cho các chức năng băm,

782
01:10:03,430 --> 01:10:08,250
và vì vậy cho pset này bạn được phép nghiên cứu các chức năng băm trên Internet

783
01:10:08,250 --> 01:10:15,560
cho một số gợi ý và cảm hứng miễn là bạn chắc chắn rằng để trích dẫn nơi bạn đã nhận nó từ.

784
01:10:15,560 --> 01:10:22,060
Bạn đang chào đón để xem xét và giải thích một số chức năng băm mà bạn tìm thấy trên Internet.

785
01:10:22,060 --> 01:10:27,460
Lại cho rằng, bạn có thể có thể để xem nếu có ai đó sử dụng một Trie

786
01:10:27,460 --> 01:10:31,700
việc thực hiện của họ là nhanh hơn so với bảng băm của bạn hay không.

787
01:10:31,700 --> 01:10:35,290
Bạn có thể trình Ban Big nhiều lần.

788
01:10:35,290 --> 01:10:37,660
Nó sẽ ghi lại mục nhập của bạn gần đây nhất.

789
01:10:37,660 --> 01:10:44,300
Vì vậy, có thể bạn thay đổi hàm băm của bạn và sau đó nhận ra rằng nó thực sự nhanh hơn rất nhiều

790
01:10:44,300 --> 01:10:46,780
hoặc chậm hơn rất nhiều so với trước đây.

791
01:10:46,780 --> 01:10:50,960
Đó là một chút của một cách thú vị.

792
01:10:50,960 --> 01:10:57,190
Luôn luôn có 1 hoặc 2 nhân viên người cố gắng để làm cho từ điển chậm nhất có thể,

793
01:10:57,190 --> 01:11:00,210
vì vậy đó là luôn luôn vui vẻ để xem xét.

794
01:11:00,210 --> 01:11:07,630
>> Sử dụng cho các pset là bạn chạy speller với một từ điển tùy chọn

795
01:11:07,630 --> 01:11:12,840
và sau đó là một tập tin văn bản bắt buộc.

796
01:11:12,840 --> 01:11:18,380
Theo mặc định khi bạn chạy speller chỉ với một tập tin văn bản và không chỉ định một từ điển,

797
01:11:18,380 --> 01:11:24,410
nó sẽ sử dụng các tập tin văn bản từ điển, lớn

798
01:11:24,410 --> 01:11:27,920
trong thư mục cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Một trong đó có hơn 100.000 từ.

800
01:11:32,760 --> 01:11:37,950
Họ cũng có một cuốn từ điển nhỏ, trong đó có những từ ngữ ít hơn đáng kể

801
01:11:37,950 --> 01:11:40,730
CS50 đã thực hiện cho bạn.

802
01:11:40,730 --> 01:11:44,050
Tuy nhiên, bạn có thể rất dễ dàng chỉ cần làm cho từ điển của riêng bạn

803
01:11:44,050 --> 01:11:47,150
nếu bạn chỉ muốn được làm việc trong các ví dụ nhỏ

804
01:11:47,150 --> 01:11:51,140
ví dụ, nếu bạn muốn sử dụng gdb và bạn biết các giá trị cụ thể

805
01:11:51,140 --> 01:11:53,560
mà bạn muốn bảng băm của bạn để vạch ra.

806
01:11:53,560 --> 01:12:00,430
Vì vậy, bạn chỉ có thể làm cho tập tin văn bản của riêng bạn chỉ với BAR, baz, FOO, và FOOBAR,

807
01:12:00,430 --> 01:12:04,860
làm cho rằng trong một tập tin văn bản, tách riêng với mỗi 1 dòng,

808
01:12:04,860 --> 01:12:12,670
và sau đó làm cho tập tin văn bản của riêng bạn mà theo nghĩa đen chỉ có thể chứa 1 hoặc 2 từ

809
01:12:12,670 --> 01:12:15,950
để bạn biết sản lượng nên được chính xác những gì.

810
01:12:15,950 --> 01:12:21,870
Một số của các tập tin văn bản mẫu mà Ban Big khi bạn chạy thách thức sẽ kiểm tra

811
01:12:21,870 --> 01:12:25,580
Chiến tranh và Hòa bình và một cuốn tiểu thuyết của Jane Austen hoặc một cái gì đó như thế.

812
01:12:25,580 --> 01:12:30,450
Vì vậy, khi bạn đang bắt đầu ra, đó là dễ dàng hơn nhiều để làm cho các tập tin văn bản của riêng bạn

813
01:12:30,450 --> 01:12:34,160
có chứa chỉ có một vài từ hoặc có thể 10

814
01:12:34,160 --> 01:12:38,280
để bạn có thể dự đoán kết quả

815
01:12:38,280 --> 01:12:42,880
và sau đó kiểm tra xem nó chống lại điều đó, vì vậy nhiều của một ví dụ có kiểm soát.

816
01:12:42,880 --> 01:12:45,820
Và như vậy kể từ khi chúng tôi đang làm việc với dự đoán và vẽ những thứ xung quanh,

817
01:12:45,820 --> 01:12:48,690
một lần nữa tôi muốn khuyến khích bạn sử dụng bút và giấy

818
01:12:48,690 --> 01:12:50,700
bởi vì nó thực sự sẽ giúp bạn với một trong những điều này -

819
01:12:50,700 --> 01:12:55,620
vẽ các mũi tên, bảng băm hoặc Trie của bạn trông như thế nào,

820
01:12:55,620 --> 01:12:57,980
khi bạn giải phóng một cái gì đó mà các mũi tên,

821
01:12:57,980 --> 01:13:01,730
đang nắm giữ đủ, bạn có thấy bất kỳ liên kết biến mất

822
01:13:01,730 --> 01:13:05,750
và rơi vào vực thẳm của bộ nhớ bị rò rỉ.

823
01:13:05,750 --> 01:13:11,070
Vì vậy, xin vui lòng, hãy cố gắng rút ra những điều trên ngay cả trước khi bạn có thể viết mã xuống.

824
01:13:11,070 --> 01:13:14,520
Vẽ những điều trên để bạn hiểu những điều sẽ làm việc

825
01:13:14,520 --> 01:13:22,750
bởi vì sau đó tôi đảm bảo bạn sẽ chạy vào ít muddles con trỏ ở đó.

826
01:13:24,270 --> 01:13:25,910
>> Được rồi.

827
01:13:25,910 --> 01:13:28,780
Tôi muốn chúc bạn tốt nhất của may mắn với pset này.

828
01:13:28,780 --> 01:13:31,980
Đây có thể là một trong những khó khăn nhất.

829
01:13:31,980 --> 01:13:40,360
Vì vậy, hãy thử bắt đầu sớm, rút ​​ra những điều trên, rút ​​ra những điều trên, và may mắn.

830
01:13:40,360 --> 01:13:42,980
Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]