>> ROB Bowden: Hi.
Tôi Rob, và chúng ta hãy băm giải pháp này ra.
Vì vậy, ở đây chúng ta sẽ thực hiện một bảng băm chung.
Chúng ta thấy rằng các nút cấu trúc của băm của chúng tôi bảng sẽ trông như thế này.
Vì vậy, nó sẽ có một từ char mảng chiều dài cộng với kích thước 1.
Đừng quên 1 kể từ khi tối đa từ trong từ điển là 45
ký tự, và sau đó chúng ta sẽ cần một nhân vật phụ cho
dấu gạch chéo ngược 0.
>> Và sau đó bảng băm của chúng tôi trong mỗi xô là sẽ lưu một
danh sách liên kết của các nút.
Chúng tôi không làm tuyến tính thăm dò ở đây.
Và như vậy để liên kết đến tiếp theo yếu tố trong xô, chúng ta cần một
struct node * next.
Vì vậy, đó là những gì một nút như thế nào.
Bây giờ, đây là khai báo của bảng băm của chúng tôi.
Nó sẽ có 16.384 thùng, nhưng con số đó không quan trọng.
Và cuối cùng, chúng ta sẽ có hashtable_size biến toàn cầu,
sẽ bắt đầu là 0, và nó sẽ theo dõi có bao nhiêu từ
là trong từ điển của chúng tôi.
Được rồi.
>> Vì vậy, chúng ta hãy nhìn vào tải.
Vì vậy, nhận thấy rằng tải, nó trả về một bool.
Bạn trở về đúng nếu nó là thành công nạp và sai khác.
Và phải mất một char * const sao từ điển, mà là từ điển
mà chúng tôi muốn mở.
Vì vậy, đó là điều đầu tiên chúng ta sẽ làm.
Chúng ta sẽ fopen từ điển cho đọc, và chúng ta sẽ có
để đảm bảo rằng nó đã thành công vì vậy nếu nó trở về NULL, sau đó chúng tôi đã không
mở thành công điển và chúng ta cần phải trả về false.
>> Nhưng giả định rằng nó đã thành công mở, sau đó chúng tôi muốn đọc
từ điển.
Vì vậy, giữ vòng lặp cho đến khi chúng tôi tìm thấy một số lý do để thoát ra khỏi này
vòng lặp mà chúng ta sẽ thấy.
Vì vậy, giữ vòng lặp, và bây giờ chúng ta sẽ để malloc một nút duy nhất.
Và tất nhiên, chúng ta cần phải kiểm tra lỗi một lần nữa vì vậy nếu mallocing đã không thành công
và chúng tôi muốn dỡ bỏ bất kỳ nút mà chúng ta đã xảy ra với malloc trước, đóng cửa
từ điển và trả về false.
>> Nhưng bỏ qua mà, giả sử chúng ta đã thành công, sau đó chúng tôi muốn sử dụng fscanf
để đọc một từ duy nhất từ ​​chúng tôi từ điển vào nút của chúng tôi.
Vì vậy, hãy nhớ rằng từ nhập cảnh> là char đệm từ có độ dài cộng với kích thước
mà chúng ta đang đi lưu trữ từ nhập
Vì vậy, fscanf sẽ trả lại 1 miễn vì nó đã có thể đọc thành công
từ từ tập tin.
>> Nếu một trong hai lỗi xảy ra hoặc chúng tôi đạt được cuối của tập tin, nó sẽ không
trả lại 1 trong trường hợp này nếu nó không trở về 1, chúng tôi cuối cùng sẽ phá vỡ
ra khỏi vòng lặp trong khi điều này.
Vì vậy, chúng ta thấy rằng một khi chúng ta đã thành công đọc một từ vào
entry-> từ, sau đó chúng ta sẽ băm từ đó sử dụng hàm băm của chúng tôi.
Chúng ta hãy nhìn vào hàm băm.
>> Vì vậy, bạn không thực sự cần để hiểu được điều này.
Và trên thực tế, chúng ta chỉ cần kéo này băm chức năng từ internet.
Điều duy nhất bạn cần phải nhận ra là rằng điều này có một const char * từ,
do đó, nó tham gia một chuỗi như là đầu vào và trả lại một int unsigned như đầu ra.
Vì vậy, đó là tất cả một hàm băm được, là nó mất trong một đầu vào, nó sẽ cho bạn một
chỉ số vào bảng băm.
Chú ý rằng bạn chỉnh sửa bởi NUM_BUCKETS vì vậy giá trị băm trở lại
thực sự là một chỉ số vào bảng băm và không chỉ vượt ra ngoài
giới hạn của mảng.
>> Vì vậy, cho rằng hàm băm, chúng ta sẽ để băm từ mà chúng ta đọc
từ điển và sau đó chúng ta sẽ sử dụng có để chèn
nhập cảnh vào bảng băm.
Bây giờ, băm Hashtable là hiện tại danh sách liên kết trong bảng băm, và
nó rất có thể đó chỉ là NULL.
Chúng tôi muốn chèn mục của chúng tôi tại bắt đầu của danh sách liên kết này, và như vậy
chúng ta sẽ có mục hiện tại của chúng tôi trỏ đến những gì các bảng băm hiện
điểm và sau đó chúng ta sẽ lưu trữ trong bảng băm vào băm
mục hiện hành.
>> Vì vậy, hai dòng chèn thành công nhập cảnh tại các đầu
danh sách liên kết tại chỉ số đó trong bảng băm.
Một khi chúng ta đang thực hiện với đó, chúng tôi biết mà chúng ta tìm thấy một từ khác trong
Từ điển và chúng tôi tăng một lần nữa.
Vì vậy, chúng tôi tiếp tục làm điều đó cho đến khi fscanf cuối cùng trả về một cái gì đó không 1 tại
thời điểm đó hãy nhớ rằng chúng ta cần phải vào cửa miễn phí, vì vậy ở đây, chúng tôi malloced một
nhập cảnh, chúng tôi cố gắng để đọc một cái gì đó từ điển.
Và chúng tôi đã không đọc thành công một cái gì đó từ điển, trong đó
trường hợp chúng ta cần phải giải phóng các mục mà chúng ta không bao giờ thực sự đưa vào bảng băm
và cuối cùng phá vỡ.
>> Một khi chúng ta thoát ra khỏi, chúng ta cần phải nhìn thấy, tốt, chúng tôi đã phá vỡ ra bởi vì có
được một lỗi đọc từ tập tin, hoặc chúng tôi đã phá vỡ ra bởi vì chúng tôi đến
kết thúc của tập tin?
Nếu có một lỗi, sau đó chúng tôi muốn return false vì tải không
thành công, và trong quá trình này, chúng tôi muốn dỡ bỏ tất cả các từ mà chúng ta đọc
trong và đóng tập tin từ điển.
Giả sử chúng ta đã thành công, sau đó chúng tôi chỉ vẫn cần phải đóng cửa từ điển
tập tin, và cuối cùng trở về đúng kể từ khi chúng tôi đã nạp thành công
từ điển.
Và đó là nó cho tải.
>> Vì vậy, bây giờ kiểm tra, đưa ra một bảng băm tải, sẽ trông như thế này.
Vì vậy, kiểm tra, nó trả về một bool, mà sẽ chỉ ra cho dù
thông qua trong char * từ, cho dù chuỗi thông qua-in trong từ điển của chúng tôi.
Vì vậy, nếu nó có trong từ điển, nếu nó là trong bảng băm của chúng tôi, chúng tôi sẽ trở lại
đúng, và nếu nó không phải, chúng tôi sẽ trả về false.
Cho từ thông qua trong này, chúng tôi sẽ băm từ.
>> Bây giờ, một điều quan trọng để nhận ra là mà trong tải, chúng tôi biết rằng tất cả các
các từ được sẽ thấp hơn trường hợp, nhưng ở đây, chúng tôi không như vậy chắc chắn.
Nếu chúng ta hãy nhìn vào hàm băm của chúng tôi, hàm băm của chúng tôi thực sự
được lowercasing mỗi nhân vật của từ.
Vì vậy, bất kể giá trị vốn hóa của từ, hàm băm của chúng tôi sẽ
trả lại chỉ số tương tự cho bất cứ điều gì vốn là như nó sẽ có
trả lại cho một hoàn toàn chữ thường phiên bản của từ.
Được rồi.
>> Vì vậy, đó là chỉ số của chúng tôi.
Đó là bảng băm cho từ này.
Bây giờ, điều này cho vòng lặp sẽ đến hơn danh sách liên kết
đó là tại chỉ số đó.
Vì vậy, nhận thấy chúng ta đang khởi nhập để trỏ đến chỉ số.
Chúng tôi sẽ tiếp tục trong khi nhập không không NULL bằng nhau, và hãy nhớ rằng
cập nhật con trỏ trong danh sách liên kết của chúng tôi nhập bằng entry-> tiếp theo, vì vậy có
điểm vào hiện tại của chúng tôi với mục tiếp theo trong danh sách liên kết.
Được rồi.
>> Vì vậy, cho mỗi mục trong danh sách liên kết, chúng ta sẽ sử dụng strcasecmp.
Nó không strcmp vì một lần nữa, chúng tôi muốn làm những điều trường hợp insensitively.
Vì vậy, chúng tôi sử dụng để so sánh strcasecmp từ đã được thông qua chức năng này
chống lại các từ đó là trong mục này.
Nếu nó trả về 0, có nghĩa là đã có một trận đấu, trong trường hợp này chúng tôi muốn
return true.
Chúng tôi tìm thấy thành công từ trong bảng băm của chúng tôi.
>> Nếu không có một trận đấu, thì chúng ta đi lặp lại và nhìn vào
mục tiếp theo.
Và chúng tôi sẽ tiếp tục vòng lặp trong khi có là các mục trong danh sách liên kết này.
Điều gì xảy ra nếu chúng ta phá vỡ trong số này cho vòng lặp?
Điều đó có nghĩa chúng tôi không tìm thấy một mục mà kết hợp từ này, trong trường hợp
chúng tôi trả về false để chỉ ra rằng chúng tôi bảng băm không có từ này.
Và đó là nó để kiểm tra.
Được rồi.
>> Vì vậy, chúng ta hãy nhìn vào kích thước.
Bây giờ, kích thước sẽ là khá đơn giản kể từ khi nhớ trong tải, cho mỗi từ
chúng tôi thấy chúng tôi tăng lên một toàn cầu hashtable_size biến.
Vì vậy, các chức năng kích thước chỉ là sẽ trả lại rằng toàn cầu
biến, và đó là nó.
>> Bây giờ cuối cùng, chúng ta cần phải dỡ bỏ các từ điển một lần tất cả mọi thứ được thực hiện.
Vì vậy, làm thế nào chúng tôi sẽ làm điều đó?
Ngay tại đây, chúng tôi đang Looping trên tất cả xô bảng băm của chúng tôi.
Vì vậy, có NUM_BUCKETS xô.
Và cho mỗi danh sách liên kết trong băm của chúng tôi bảng, chúng ta sẽ vòng qua
toàn bộ danh sách liên kết giải phóng mỗi yếu tố.
Bây giờ, chúng ta cần phải cẩn thận, vì vậy ở đây chúng tôi có một biến tạm thời đó là
lưu trữ các con trỏ đến tiếp theo phần tử trong danh sách liên kết.
Và sau đó chúng tôi sẽ miễn phí các yếu tố hiện tại.
>> Chúng tôi cần phải chắc chắn chúng tôi làm điều này vì chúng ta không thể chỉ giải phóng các yếu tố hiện tại
và sau đó cố gắng truy cập vào các con trỏ tới kể từ khi chúng tôi giải thoát nó
bộ nhớ trở nên không hợp lệ.
Vì vậy, chúng ta cần phải giữ cho xung quanh một con trỏ tới các yếu tố tiếp theo, sau đó chúng tôi có thể giải phóng
yếu tố hiện tại, và sau đó chúng tôi có thể cập nhật phần tử hiện tại của chúng tôi để trỏ đến
các yếu tố tiếp theo.
>> Chúng tôi sẽ vòng lặp trong khi có những yếu tố trong danh sách liên kết này.
Chúng tôi sẽ làm điều đó cho tất cả các danh sách liên kết trong bảng băm, và một khi chúng ta đang thực hiện
với đó, chúng tôi đã hoàn toàn dỡ bảng băm, và chúng tôi đang thực hiện.
Vì vậy, nó không thể trút bao giờ return false, và khi chúng tôi đang thực hiện, chúng tôi
chỉ trả lại sự thật.