>> SPEAKER 1: Hãy cho giải pháp này một thử.
Vì vậy, chúng ta hãy nhìn vào những gì chúng tôi Nút cấu trúc sẽ như thế nào.
Ở đây, chúng ta thấy chúng ta sẽ có một Bool Word và một nút sao Struct
Trẻ em trong ngoặc bảng chữ cái.
Vì vậy, điều đầu tiên bạn có thể tự hỏi, tại sao băm bảng chữ cái được xác định là 27?
Vâng, hãy nhớ rằng chúng ta sẽ cần được xử lý dấu nháy đơn, vì vậy
đó là có được một chút của một đặc biệt trường hợp trong suốt chương trình này.
>> OK, bây giờ, nhớ làm thế nào một Trie thực sự hoạt động.
Hãy nói rằng chúng tôi đang lập chỉ mục những con mèo từ, sau đó từ thư mục gốc của Trie của chúng tôi,
chúng ta sẽ nhìn vào trẻ em mảng, và chúng ta sẽ xem xét các
chỉ số tương ứng với chữ cái C. Vì vậy, đó sẽ là chỉ số hai.
Vì vậy, cho rằng, sẽ cung cấp cho chúng tôi một nút mới, và sau đó chúng tôi sẽ
làm việc từ nút đó.
>> Vì vậy, cho nút đó, chúng tôi lại một lần nữa sẽ xem xét các mảng trẻ em,
và chúng ta sẽ nhìn vào chỉ số không tương ứng với một trong mèo.
Vì vậy, sau đó chúng ta sẽ đi đến nút đó, và cho nút đó, chúng ta sẽ
nhìn vào các chỉ số tương ứng T. Và chuyển sang nút đó,
cuối cùng, chúng tôi đã hoàn toàn nhìn thông qua của chúng tôi từ Cát, và bây giờ Bool
Từ được cho là để cho biết từ cho điều này thực sự là một từ.
>> Vì vậy, tại sao chúng ta cần phải có trường hợp đặc biệt?
Vâng, những gì nếu thảm họa từ là trong từ điển của chúng tôi, nhưng
con mèo từ không?
Vì vậy, trong việc tìm kiếm để xem nếu con mèo từ là trong từ điển của chúng tôi, chúng ta sẽ
xem xét thành công thông qua các chỉ số C-A-T và đạt được một nút, nhưng đó là
chỉ vì thảm họa đã xảy ra với tạo ra các nút trên đường từ C-A-T tất cả
đường đến cuối từ.
Vì vậy, Bool Word được sử dụng chỉ ra liệu địa điểm cụ thể này thực sự
chỉ một từ.
>> Được rồi, vậy bây giờ chúng ta biết những gì một Trie sẽ như thế nào, chúng ta hãy xem
các chức năng Load.
Vì vậy, tải sẽ trả về một Bool cho dù chúng ta có thành công hay
từ điển nhưng không thành công và nạp này là có được từ điển
mà chúng tôi muốn để tải.
Điều đầu tiên để chúng ta sẽ làm là mở up từ điển để đọc.
Chúng ta phải chắc chắn rằng chúng tôi đã không thất bại, vì vậy nếu từ điển không
mở thành công, nó sẽ trở lại Không, trong trường hợp này chúng ta sẽ
trở về False.
Nhưng giả định rằng nó thành công mở ra, sau đó chúng tôi thực sự có thể đọc
thông qua các từ điển.
>> Điều đầu tiên để chúng ta sẽ muốn làm là chúng tôi có điều này
gốc biến toàn cầu.
Bây giờ, gốc là có được một ngôi sao nút.
Đó là đầu Trie của chúng tôi rằng chúng tôi sẽ được lặp lại thông qua.
Điều đầu tiên để chúng ta sẽ muốn làm là cấp phát bộ nhớ cho người chủ của chúng tôi.
>> Chú ý rằng chúng ta đang sử dụng calloc chức năng, mà về cơ bản là giống nhau
như chức năng malloc, ngoại trừ nó đảm bảo để trở về cái gì đó là
hoàn toàn zeroed ra.
Vì vậy, nếu chúng tôi sử dụng malloc, chúng tôi sẽ cần phải đi qua tất cả các con trỏ trong của chúng tôi
nút và chắc chắn rằng tất cả chúng null.
Vì vậy, calloc sẽ làm điều đó cho chúng ta.
>> Bây giờ, giống như malloc, chúng tôi cần phải thực hiện đảm bảo rằng việc phân bổ thực sự
thành công.
Nếu điều này trở về null, sau đó chúng tôi cần phải đóng từ điển của chúng tôi
nộp và trả lại sai.
Vì vậy, giả định việc phân bổ được thành công, chúng ta sẽ sử dụng một nút
sao con trỏ để lặp thông qua Trie của chúng tôi.
Vì vậy, chúng tôi gốc sẽ không bao giờ thay đổi, nhưng chúng ta sẽ sử dụng con trỏ để
thực sự đi từ nút đến nút.
>> Được rồi, vậy trong này Đối với loop, chúng tôi đọc qua các tập tin từ điển,
và chúng tôi đang sử dụng tại fgetc.
Vì vậy, fgetc sẽ lấy một đơn nhân vật từ tập tin.
Chúng tôi sẽ tiếp tục lấy ký tự trong khi chúng tôi không đạt được
kết thúc của tập tin, do đó, hai trường hợp chúng ta cần phải xử lý.
Đầu tiên, nếu nhân vật không phải là một dòng mới, vì vậy chúng tôi biết nếu đó là một mới
dòng, sau đó chúng tôi sắp sửa chuyển sang một từ mới.
Nhưng giả sử nó không phải là một dòng mới, sau đó ở đây, chúng tôi muốn tìm ra
chỉ số chúng ta sẽ chỉ vào trong mảng trẻ em mà
chúng tôi xem xét trước.
>> Vì vậy, như tôi đã nói, chúng ta cần phải trường hợp đặc biệt các dấu nháy đơn.
Lưu ý chúng đang sử dụng nhà điều hành ternary ở đây, vì vậy chúng ta sẽ đọc
này là nếu nhân vật chúng ta đọc trong là một dấu nháy đơn, sau đó chúng ta sẽ
thiết lập chỉ mục bằng bảng chữ cái trừ 1, đó sẽ là chỉ số 26.
Khác, nếu nó không phải là một dấu nháy đơn, sau đó chúng ta sẽ thiết lập các chỉ số
bằng c trừ đi một.
Vì vậy, nhớ lại từ bộ p trước, c trừ đi một sẽ cung cấp cho chúng tôi
vị trí chữ cái của c, vì vậy nếu c là chữ A, điều này sẽ
cung cấp cho chúng tôi số không.
Đối với chữ B, nó sẽ cung cấp cho chúng tôi chỉ số 1, và như vậy.
>> Vì vậy, điều này cho phép chúng ta chỉ mục vào Trẻ em mảng mà chúng ta muốn.
Bây giờ, nếu chỉ số này hiện đang vô giá trị trong mảng trẻ em, có nghĩa là
một nút hiện không tồn tại từ con đường đó, vì vậy chúng tôi cần phải phân bổ một
nút cho con đường đó.
Đó là những gì chúng tôi làm ở đây.
Vì vậy, chúng ta sẽ, một lần nữa, sử dụng calloc chức năng để chúng ta không có
để không ra tất cả các con trỏ, và chúng tôi, một lần nữa, cần phải kiểm tra calloc mà
đã không thất bại.
Nếu calloc đã thất bại, sau đó chúng ta cần dỡ bỏ tất cả mọi thứ, đóng cửa của chúng tôi
từ điển, và trở về False.
>> Vì vậy, giả định rằng nó đã không thất bại, sau đó điều này sẽ tạo ra một đứa trẻ mới cho chúng tôi,
và sau đó chúng ta sẽ đi đến đứa trẻ.
Con trỏ của chúng tôi sẽ lặp lại xuống con đó.
Bây giờ, nếu đây không phải là vô giá trị để bắt đầu với, sau đó con trỏ chỉ có thể lặp lại
xuống con đó mà không thực sự phải phân bổ bất cứ điều gì.
Đây là trường hợp đầu tiên mà chúng tôi đã xảy ra phân bổ mèo từ, và
đó có nghĩa là khi chúng tôi đi để phân bổ thảm họa, chúng tôi không cần phải tạo ra
các nút cho C-A-T một lần nữa.
Họ đã tồn tại.
>> OK, vì vậy đây là những gì khác?
Đây là điều kiện mà c là dấu gạch chéo ngược n, trong đó c là một dòng mới.
Điều này có nghĩa rằng chúng ta có thành công hoàn thành một từ.
Bây giờ, những gì chúng tôi muốn làm khi chúng ta Hoàn thành một từ?
Chúng ta sẽ sử dụng trường từ này bên trong của nút Struct của chúng tôi.
>> Chúng tôi muốn thiết lập đó là True, để chỉ ra rằng nút này cho thấy một
từ thành công một từ thực tế.
Bây giờ, thiết lập đó là True.
Chúng tôi muốn thiết lập lại con trỏ của chúng tôi đến thời điểm để đầu Trie một lần nữa.
Và cuối cùng, tăng từ điển của chúng tôi kích thước từ khi chúng tôi tìm thấy một từ khác.
>> Được rồi, vậy chúng ta sẽ tiếp tục làm rằng, đọc sách trong nhân vật của
nhân vật, xây dựng các nút mới trong Trie của chúng tôi và cho mỗi từ trong
từ điển, cho đến khi cuối cùng chúng ta đạt c bằng kết thúc tập tin, trong trường hợp này, chúng ta phá vỡ
ra của tập tin.
Bây giờ, có hai trường hợp dưới mà chúng tôi có thể nhấn kết thúc tập tin.
Đầu tiên là nếu có một lỗi đọc từ tập tin, vì vậy nếu có
một lỗi, chúng tôi cần phải làm những điển hình dỡ bỏ tất cả mọi thứ, đóng tập tin,
trở về False.
Giả sử không có lỗi, mà chỉ có nghĩa là chúng tôi thực sự đánh cuối
các tập tin, trong trường hợp đó, chúng tôi đóng cửa nộp và trở lại thật vì chúng ta
nạp thành công từ điển vào Trie của chúng tôi.
>> Được rồi, vậy bây giờ chúng ta hãy kiểm tra Kiểm tra.
Nhìn vào Kiểm tra chức năng, chúng ta thấy Kiểm tra có nghĩa là sẽ trả về một Bool.
Nó trả về True nếu từ này là nó được thông qua là trong Trie của chúng tôi.
Nó trả về False khác.
>> Vậy làm thế nào chúng ta sẽ xác định xem từ này là trong Trie của chúng tôi?
Chúng ta thấy ở đây, giống như trước đây, chúng ta sẽ sử dụng con trỏ để lặp
thông qua Trie của chúng tôi.
Bây giờ, ở đây, chúng ta sẽ lặp trên toàn bộ từ chúng tôi.
Vì vậy, duyệt qua từ chúng tôi trôi qua, chúng ta sẽ xác định
chỉ số vào mảng trẻ em mà tương ứng với khung từ tôi.
Vì vậy, điều này sẽ trông giống hệt như Tải, mà nếu khung từ tôi là một
dấu nháy đơn, sau đó chúng tôi muốn sử dụng chỉ số bảng chữ cái trừ 1 vì chúng tôi xác định
đó là nơi mà chúng ta sẽ để lưu trữ dấu nháy.
>> Khác chúng ta sẽ sử dụng ToLower khung từ tôi.
Vì vậy, nhớ từ đó có thể có tùy ý hoa, và vì vậy chúng tôi
muốn chắc chắn rằng chúng ta đang sử dụng một phiên bản chữ thường của sự vật.
Và sau đó trừ đi từ chữ thường mà một để, một lần nữa, cho chúng tôi
vị trí chữ cái của nhân vật đó.
Vì vậy, đó sẽ là chỉ số của chúng tôi vào mảng trẻ em.
>> Và bây giờ, nếu chỉ số vào trẻ em mảng là null, có nghĩa là chúng tôi
không còn có thể tiếp tục iterating xuống Trie của chúng tôi.
Nếu đó là trường hợp, từ này có thể không có thể là trong Trie của chúng tôi, vì nếu nó
được, mà có nghĩa là sẽ có một con đường xuống từ đó, và bạn sẽ
không bao giờ gặp phải null.
Vì vậy, gặp phải vô giá trị, chúng tôi trở lại Sai.
Từ không có trong từ điển.
Nếu nó không được null, sau đó chúng ta sẽ tiếp tục iterating, vì vậy chúng ta sẽ
để cập nhật con trỏ của chúng tôi để trỏ đến đó nút cụ thể tại chỉ số đó.
>> Vì vậy, chúng tôi tiếp tục làm điều đó trong suốt toàn bộ từ.
Giả sử chúng ta không bao giờ đánh null, mà phương tiện chúng tôi có thể để có được thông qua toàn bộ
thế giới và tìm thấy một nút trong Trie của chúng tôi, nhưng chúng tôi không hoàn toàn thực hiện được nêu ra.
Chúng tôi không muốn chỉ trả lại True.
Chúng tôi muốn trở lại con trỏ từ lỗi Kể từ đó, nhớ một lần nữa, nếu không phải là con mèo
trong từ điển và thảm họa của chúng tôi là, sau đó chúng tôi sẽ thành công có được thông qua
con mèo từ, nhưng từ con trỏ sẽ là sai và không thật.
Vì vậy, chúng tôi trở lại từ con trỏ để chỉ cho dù nút này thực sự là một từ,
và đó là nó để kiểm tra.
>> Vì vậy, hãy kiểm tra kích thước.
Vì vậy, Kích là có được khá dễ dàng Kể từ đó, nhớ trong Load, chúng tôi
cách tăng kích thước từ điển cho mỗi từ mà chúng ta gặp phải.
Vì vậy, Kích thước chỉ là sẽ quay trở lại kích thước từ điển, và đó là nó.
>> Được rồi, cuối cùng, chúng tôi có Unload.
Vì vậy, Unload, chúng ta sẽ sử dụng một hàm đệ quy để thực sự làm tất cả
các công việc cho chúng tôi, vì vậy chức năng của chúng tôi sẽ được gọi là dỡ.
Dỡ là những gì sẽ làm gì?
Chúng ta thấy ở đây dỡ có nghĩa là sẽ lặp qua tất cả các trẻ em
nút đặc biệt này, và nếu đứa trẻ nút không phải là null, sau đó chúng ta sẽ
dỡ bỏ các nút con.
>> Vì vậy, điều này sẽ đệ quy dỡ bỏ tất cả các trẻ em của chúng tôi.
Một khi chúng tôi chắc chắn rằng tất cả các trẻ em của chúng tôi đã được dỡ xuống, sau đó chúng tôi
có thể giải phóng mình, vì vậy dỡ bỏ ourself.
Vì vậy, điều này đệ quy sẽ dỡ bỏ các toàn bộ Trie, và sau đó một khi đó là
thực hiện, chúng tôi chỉ có thể trở lại True.
Dỡ bỏ không thể thất bại, chúng tôi chỉ giải phóng mọi thứ.
Vì vậy, khi chúng tôi đang thực hiện giải phóng tất cả mọi thứ, trở về thật.
Và đó là nó.
Tên tôi là Rob, và điều này là [không nghe được].