ZAMYLA CHAN: Hãy làm cho kiểm tra chính tả. Nếu bạn mở speller.c, sau đó bạn sẽ thấy rằng hầu hết các chức năng cho kiểm tra một tập tin văn bản với một từ điển đã được thực hiện cho bạn. . / Speller, đi qua trong một văn bản từ điển nộp và sau đó một tập tin văn bản, sẽ kiểm tra xem file văn bản so với từ điển. 

Bây giờ, tập tin văn bản từ điển sẽ chứa từ hợp lệ, mỗi dòng. Sau đó sẽ gọi speller.c tải trên các tập tin văn bản từ điển. Nó sẽ gọi một chức năng được gọi là Kiểm tra mỗi từ trong các tập tin văn bản đầu vào, in ấn tất cả các từ sai chính tả. 

Speller.c cũng sẽ gọi Kích để xác định số từ trong Từ điển và gọi Unload để giải phóng bộ nhớ. speller.c cũng sẽ theo dõi như thế nào nhiều thời gian được sử dụng để tiến hành các quy trình, nhưng chúng tôi sẽ nhận được để mà sau. 

Vì vậy, những gì chúng ta cần phải làm gì? Chúng ta cần phải điền vào dictionary.c. Trong dictionary.c, chúng tôi có người giúp đỡ chức năng Load, mà tải từ điển. Kiểm tra chức năng, trong đó kiểm tra nếu một từ được đưa ra là trong từ điển. Chức năng Kích trả về số các từ trong từ điển. Và cuối cùng, chúng tôi đã Dỡ bỏ, mà giải phóng từ điển từ bộ nhớ. 

Vì vậy, đầu tiên, hãy giải quyết Load. Đối với mỗi từ trong văn bản từ điển tập tin, tải sẽ lưu trữ những từ đó trong cấu trúc dữ liệu từ điển lựa chọn của bạn, hoặc là một băm bảng hoặc một Trie. Tôi sẽ đi qua cả này đi qua. 

Đầu tiên hãy nói về bảng băm. Giả sử bạn có 10 quả bóng bi-a và bạn muốn để lưu trữ chúng. Bạn có thể đặt tất cả chúng trong một cái xô, và khi bạn cần một người cụ thể số quả bóng, bạn sẽ mất một ngoài những xô tại một thời điểm tìm kiếm quả bóng đó. Và chỉ có 10 quả bóng, bạn sẽ có có thể tìm thấy bóng của bạn một cách hợp lý số lượng thời gian. 

Nhưng nếu bạn đã có 20 quả bóng? Nó có thể mất một ít lâu hơn bây giờ. Những gì về 100? 1000? Bây giờ, nó sẽ dễ dàng hơn nhiều nếu bạn có nhiều thùng. Có lẽ một xô cho bi số không thông qua chín, một xô cho bi số 10 thông qua 19, và như vậy. 

Bây giờ khi bạn cần thiết để tìm kiếm cụ thể bóng, bạn có thể tự động đi đến một xô cụ thể và tìm kiếm thông qua thùng đó. Và nếu mỗi thùng có khoảng 10 quả bóng, sau đó bạn có thể dễ dàng tìm kiếm thông qua nó. 

Bây giờ, kể từ khi chúng tôi đang làm việc với từ điển, một xô duy nhất cho tất cả các từ có trong từ điển sẽ có lẽ là quá ít thùng. Vì vậy, chúng ta hãy nhìn vào bảng băm. 

Nghĩ về nó như một mảng xô. Và trong trường hợp này, xô là danh sách liên kết của chúng tôi. Và chúng tôi sẽ phân phối tất cả các từ của chúng tôi trong số các danh sách liên kết nhiều trong một cách có tổ chức sử dụng một hàm băm, mà sẽ cho chúng tôi biết xô một khóa nhất định, một định từ, thuộc về. 

Chúng ta hãy đại diện này đồ. Các ô màu xanh ở đây chứa các giá trị và hộp màu đỏ trỏ đến giá trị khác cặp con trỏ. Chúng tôi sẽ gọi các nút cặp. Bây giờ, mỗi nhóm, như tôi đã nói trước đó, là một danh sách liên kết. Trong danh sách liên kết, mỗi nút có giá trị, cũng như một con trỏ đến giá trị tiếp theo. 

Bây giờ, đối phó với danh sách liên kết, nó rất quan trọng là bạn không bị mất bất kỳ liên kết. Và một thực tế cần ghi nhớ là các nút cuối cùng, nếu nó không trỏ đến một nút khác, chỉ để null. 

Vì vậy, làm thế nào để chúng tôi đại diện này trong C? Chúng tôi xác định cấu trúc của chúng tôi ở đây. Và giá trị trong trường hợp này là một mảng char chiều dài. Chiều dài cộng với 1, nơi mà chiều dài là Chiều dài tối đa của bất kỳ văn bản, cộng thêm 1 cho terminator null. Và sau đó chúng tôi có một con trỏ đến một nút gọi là Next. 

Vì vậy, chúng ta hãy làm một danh sách liên kết nhỏ. Trước tiên, bạn sẽ muốn malloc nút của bạn, mà tạo ra không gian trong bộ nhớ kích thước của loại nút của bạn. Và làm cho một nút khác, một lần nữa mallocing. 

Bây giờ nếu bạn muốn chỉ định một giá trị cho một từ, sau đó chúng tôi có thể nói mũi tên node1 từ bằng "Xin chào." Điều hành mũi tên này dereferences con trỏ và truy cập các biến của cấu trúc. Bằng cách này, chúng ta không cần phải sử dụng cả hai các dấu chấm và các nhà điều hành sao. 

Vì vậy, sau đó tôi có node2 mũi tên từ bằng "Thế giới." Và ở đó, các giá trị dân cư trong các nút của tôi. Để làm cho các liên kết, tôi sẽ vượt qua trong node1 mũi tên bên cạnh, tiếp cận ngôi sao nút, rằng con trỏ nút, bằng node2, chỉ node1 node2 để hai. Và chúng tôi đã có một danh sách liên kết. 

Vì vậy, đó chỉ là một danh sách liên kết, nhưng một bảng băm là một mảng toàn bộ danh sách liên kết. Vâng, chúng ta sẽ có cùng một nút cấu trúc như trước. Nhưng nếu chúng ta muốn có một bảng băm thực tế, sau đó chúng tôi chỉ có thể làm cho một con trỏ nút mảng ở đây. Ví dụ, kích thước 500. 

Bây giờ thông báo, có sẽ là một thương mại bằng giữa kích thước của bạn bảng băm và kích thước của danh sách liên kết của bạn. Nếu bạn có một số thực sự cao xô, tưởng tượng phải chạy trở lại và ra trong một dòng tìm xô của bạn. Nhưng bạn cũng không muốn có một số lượng nhỏ xô, bởi vì sau đó chúng tôi trở lại vấn đề ban đầu như thế nào có quá nhiều quả bóng trong xô của chúng tôi. 

OK, nhưng nơi nào bóng của chúng tôi đi đâu? Vâng, đầu tiên chúng ta cần phải có một quả bóng, phải không? Vì vậy, hãy malloc một nút cho mỗi từ mới mà chúng ta có. nút * new_node bình đẳng malloc (sizeof (node)). 

Bây giờ chúng ta có cấu trúc này, chúng tôi có thể quét trong, bằng cách sử dụng chức năng fscanf, một chuỗi từ tập tin của chúng tôi, nếu đó là một tập tin từ điển, vào new_node mũi tên từ nơi new_node từ mũi tên là của chúng tôi điểm đến của từ đó. 

Tiếp theo, chúng ta sẽ muốn băm mà từ sử dụng một hàm băm. Một hàm băm phải mất một chuỗi và trả về một chỉ số. Trong trường hợp này, chỉ số này có đến ít hơn số lượng xô mà bạn có. 

Bây giờ, hàm băm, khi bạn đang cố gắng để tìm kiếm và tạo ra một trong của riêng bạn, hãy nhớ rằng họ phải xác định. Điều đó có nghĩa rằng cùng một giá trị cần bản đồ để xô giống nhau mỗi lần mà bạn băm nó. 

Nó giống như một thư viện. Khi bạn có một cuốn sách, dựa trên tác giả, bạn biết được thời hạn sử dụng là cần đi vào, cho dù đó là số kệ một, hai, hoặc ba. Và cuốn sách đó sẽ luôn luôn thuộc về hoặc kệ một, hai, hoặc ba. 

Vì vậy, nếu new_node mũi tên từ có từ từ từ điển của bạn, sau đó băm new_node mũi tên từ sẽ cho chúng ta những chỉ số của xô bảng băm. Và sau đó chúng tôi sẽ chèn vào đó mà danh sách liên kết cụ thể chỉ định bởi các giá trị của hàm băm của chúng tôi trở lại. 

Hãy xem xét một ví dụ về chèn một nút vào bắt đầu của một danh sách liên kết. Nếu người đứng đầu là một con trỏ nút cho biết khởi đầu của một liên kết danh sách, và new_node cho biết mới nút mà bạn muốn nhập vào, chỉ cần giao đầu đến new_node sẽ mất các liên kết đến các phần còn lại của danh sách. Vì vậy, chúng tôi không muốn làm điều này. 

Thay vào đó, chúng tôi muốn chắc chắn rằng chúng ta giữ cho mỗi nút duy nhất trong chương trình của chúng tôi. Vì vậy, chạy new_node mũi tên ngang hàng tiếp theo đầu và sau đó đầu bằng new_node sẽ bảo vệ tất cả các liên kết và không mất bất kỳ. 

Nhưng nếu bạn muốn danh sách của bạn được sắp xếp, bởi vì có một sắp xếp liên kết danh sách có thể được dễ dàng hơn cho tìm kiếm nó sau này? Vâng, cho rằng, bạn sẽ cần phải biết làm thế nào để đi qua danh sách liên kết. 

Đi qua một danh sách liên kết, chúng ta hãy có một con trỏ nút, một nút *, làm con trỏ của bạn, cho thấy đó nút bạn đang ở, bắt đầu ở phần tử đầu tiên. Vòng lặp cho đến khi con trỏ là null, chúng ta có thể tiến hành quy trình nhất định và sau đó thúc đẩy con trỏ khi chúng ta cần sử dụng con trỏ giá trị mũi tên. 

Hãy nhớ rằng, đây là điều tương tự như nói con trỏ sao, dereferencing con trỏ, sau đó sử dụng giá trị dấu chấm. Để cập nhật con trỏ bằng cách gán con trỏ đến con trỏ mũi tên bên cạnh. 

Giả sử bạn xác định rằng D sẽ trở thành trong giữa C và E. Để chèn các nút, có điểm D new_node đến nút E, đó là con trỏ tới. Và sau đó C, con trỏ, có thể sau đó điểm D. Bằng cách đó, bạn duy trì một danh sách. Hãy cẩn thận không để mất liên kết của bạn bằng cách di chuyển mũi tên trỏ bên cạnh D ngay lập tức. 

Được rồi. Vì vậy, đó là cách bạn có thể chèn các nút, tải chúng trong, từ tải vào những các nút, và chèn chúng vào bảng băm của bạn. Vì vậy, bây giờ chúng ta hãy nhìn vào cố gắng. 

Trong một Trie, mỗi nút sẽ chứa một mảng của con trỏ nút, một cho mỗi thư trong bảng chữ cái cộng với một dấu nháy đơn. Và mỗi phần tử trong mảng sẽ trỏ đến một nút khác. Nếu nút đó là vô giá trị, sau đó lá thư sẽ không được thư tiếp theo của bất kỳ từ nào trong một chuỗi, bởi vì mỗi từ chỉ ra cho dù đó là người cuối cùng nhân vật của một từ hay không. 

Hãy nhìn vào một sơ đồ. Hy vọng rằng những điều sẽ là một chút rõ ràng hơn. Trong sơ đồ này, chúng ta thấy rằng chỉ một số chữ cái và chuỗi con nhất định đang được liệt kê ra. Vì vậy, bạn có thể làm theo những con đường nhất định, và tất cả những con đường sẽ dẫn bạn đến Nói cách khác nhau. 

Vì vậy, làm thế nào để chúng tôi đại diện này trong C? Vâng, tất cả các nút bây giờ là sẽ có một giá trị logic Boolean cho biết nút đó là kết thúc của một từ được hay không. Và sau đó nó cũng sẽ có một loạt các con trỏ nút được gọi là trẻ em, và có đang có được 27 trong số họ. Và hãy nhớ, bạn cũng sẽ muốn theo dõi các nút đầu tiên của bạn. Chúng ta sẽ gọi gốc mà. 

Vì vậy, đó là cấu trúc của một Trie. Làm thế nào để chúng tôi đại diện này như một từ điển? Vâng, để tải từ trong, cho mỗi từ trong từ điển, bạn sẽ muốn để lặp qua các Trie. Và mỗi phần tử trong trẻ em tương ứng với một thư khác nhau. 

Vì vậy, kiểm tra giá trị ở trẻ em chỉ số i, nơi mà tôi đại diện cho chỉ số cụ thể của bức thư bạn đang cố gắng để chèn. Vâng, nếu đó là vô giá trị, sau đó bạn sẽ muốn malloc một nút mới và có con i trỏ đến nút đó. 

Nếu nó không phải là vô giá trị, thì đó có nghĩa là mà ngành đưa ra, mà được chuỗi con, đã tồn tại. Vì vậy, sau đó bạn sẽ chỉ di chuyển đến nút mới và tiếp tục. Nếu bạn đang ở cuối của từ đó bạn đang cố gắng để tải trong từ điển, sau đó bạn có thể thiết lập mà nút hiện tại mà bạn đang ở trên là đúng sự thật. 

Vì vậy, chúng ta hãy xem một ví dụ về chèn từ "con cáo" thành của chúng tôi từ điển. Giả vờ chúng tôi bắt đầu với một từ điển rỗng. Chữ cái đầu tiên, F, sẽ được đặt ở trẻ em chỉ số năm của các gốc trẻ em mảng. Vì vậy, chúng ta chèn rằng in 

Chữ O sau đó sẽ là ở trẻ em chỉ số 15, sau đó F. Và sau đó X sẽ còn thấp hơn, phân nhánh tắt của trẻ em của O. Và sau đó bởi vì X là ký tự cuối cùng của từ "con cáo", sau đó tôi sẽ màu xanh để chỉ ra rằng đó là cuối từ. Trong C, mà có thể được thiết lập Is Từ Boolean với giá trị thực. 

Bây giờ những gì nếu từ tiếp theo mà bạn tải trong là từ "foo"? Vâng, bạn không cần phải malloc nữa không gian cho F hoặc O, bởi vì những người đã tồn tại. Nhưng cuối cùng O trong foo? Một trong đó, bạn sẽ phải malloc. Làm cho một nút mới cho rằng, thiết lập các Is Lời Boolean true. 

Vì vậy, bây giờ chúng ta hãy chèn "con chó". Con chó sẽ bắt đầu với chỉ số ba của các gốc trẻ em, bởi vì D có không được tạo ra chưa. Và chúng tôi sẽ theo một quy trình tương tự như trước đây, tạo ra con chó chuỗi, nơi của G là màu xanh vì đó là kết thúc của một từ. 

Bây giờ, nếu chúng ta muốn chèn "làm"? Vâng, đây là một chuỗi con của con chó, vì vậy chúng tôi không cần phải malloc nữa. Nhưng chúng tôi cần phải chỉ ra nơi chúng tôi đã đến cuối của từ đó. Vì vậy, các O sẽ được tô màu xanh lá cây. Tiếp tục quá trình cho mỗi đơn từ trong từ điển của bạn, bạn đã nạp chúng vào một trong hai của bạn băm bảng hoặc Trie của bạn. 

speller.c sẽ vượt qua trong chuỗi cho dictionary.c để kiểm tra xem chúng. Bây giờ, Kiểm tra chức năng có hoạt động dưới trường hợp vô cảm. Điều đó có nghĩa rằng chữ in hoa và chữ thường và một kết hợp của cả hai tất cả phải tương đương với sự thật nếu có sự kết hợp của đó là trong từ điển. Bạn cũng có thể giả định rằng dây là sẽ chỉ chứa chữ cái ký tự hoặc dấu nháy. 

Vì vậy, chúng ta hãy xem làm thế nào bạn có thể kiểm tra với một cấu trúc bảng băm. Vâng, nếu từ tồn tại, sau đó nó có thể được tìm thấy trong bảng băm. Vì vậy, sau đó bạn có thể thử để thấy rằng từ trong xô có liên quan. 

Vì vậy, mà xô sẽ từ đó được? Vâng, bạn sẽ nhận được số lượng, chỉ số các xô, bằng cách băm từ đó và sau đó tìm kiếm trong danh sách liên kết mà, đi ngang qua toàn bộ danh sách liên kết, sử dụng String So sánh chức năng. 

Nếu kết thúc của danh sách liên kết là đạt, có nghĩa là con trỏ của bạn đạt null, sau đó từ không phải là được tìm thấy trong từ điển. Nó sẽ không được ở bất kỳ thùng khác. Vì vậy, ở đây, bạn có thể xem như thế nào có thể có là một thương mại-off giữa có hoặc danh sách liên kết được sắp xếp hoặc những người được phân loại. Hoặc sẽ mất thời gian nhiều hơn trong tải hoặc thêm thời gian trong quá trình kiểm tra. 

Làm thế nào bạn có thể kiểm tra trong một cấu trúc Trie? Chúng ta sẽ đi xuống trong Trie. Cho mỗi chữ cái trong từ đầu vào mà chúng tôi đang kiểm tra, chúng tôi sẽ đi đến đó tương ứng với phần tử trong trẻ em. 

Nếu yếu tố đó là vô giá trị, sau đó phương tiện rằng không có chuỗi con có chứa từ đầu vào của chúng tôi, vì vậy từ viết sai chính tả. Nếu nó không phải là vô giá trị, chúng ta có thể di chuyển đến thư từ tiếp theo mà chúng tôi kiểm tra và tiếp tục quá trình này cho đến khi chúng tôi đạt được kết thúc của từ đầu vào. Và sau đó chúng tôi có thể kiểm tra nếu Is Word là sự thật. Nếu có, sau đó tuyệt vời. Từ chính xác. Nhưng nếu không, mặc dù chuỗi đó tồn tại trong Trie, từ đó sai chính tả. 

Khi chức năng Kích thước được gọi là, kích thước nên trả lại số lượng từ mà là trong từ điển cho bạn cấu trúc dữ liệu. Vì vậy, nếu bạn đang sử dụng một bảng băm, bạn có thể đi qua tất cả các đơn danh sách liên kết trong mỗi đơn xô đếm số các từ ở đó. Nếu bạn đang sử dụng một Trie, bạn có thể đi qua tất cả không vô đường dẫn trong Trie của bạn. Hoặc trong khi bạn đang tải từ điển trong, có thể bạn có thể theo dõi như thế nào nhiều từ bạn đang tải nhập 

Sau khi kết thúc kiểm tra speller.c tập tin văn bản với từ điển, sau đó nó được thực hiện và do đó, nó gọi Unload, nơi công việc của bạn là để giải phóng bất cứ điều gì mà bạn đã malloced. Vì vậy, nếu bạn sử dụng một bảng băm, sau đó bạn cần phải đặc biệt cẩn thận để tránh rò rỉ bộ nhớ bằng cách không giải phóng bất cứ điều gì sớm và nắm giữ tất cả liên kết duy nhất trước khi bạn miễn phí. 

Vì vậy, cho mọi phần tử trong bảng băm và cho tất cả các nút trong danh sách liên kết, bạn sẽ muốn giải phóng nút đó. Làm thế nào để bạn đi về giải phóng một danh sách liên kết? Thiết lập nút của bạn con trỏ trỏ đến người đứng đầu, với sự khởi đầu của danh sách liên kết, sau đó trong khi con trỏ của bạn không phải là vô giá trị, bạn có thể đặt tạm thời nút con trỏ đến con trỏ của bạn. Sau đó tiến con trỏ. Và sau đó bạn có thể tự do mà tạm thời giá trị trong khi vẫn giữ trên để tất cả mọi thứ sau đó. 

Nếu bạn đang sử dụng một Trie? Sau đó, cách tốt nhất để làm điều này là dỡ bỏ từ rất dưới lên trên. Bằng cách đi xuống mức thấp nhất có thể nút, bạn có thể tự do tất cả các con trỏ trong rằng trẻ em và sau đó quay lại trở lên, giải phóng tất cả các yếu tố trong tất cả của trẻ em mảng, cho đến khi bạn nhấn nút gốc hàng đầu của bạn. Đây là nơi Đệ quy sẽ có ích. 

Để đảm bảo rằng bạn đã có thể giải thoát tất cả mọi thứ mà bạn đã malloced, bạn có thể sử dụng Valgrind. Chạy Valgrind sẽ chạy chương trình của bạn đếm bao nhiêu byte bộ nhớ bạn đang sử dụng và đảm bảo rằng bạn đã giải thoát tất cả, nói cho bạn nơi bạn có thể có quên miễn phí. Vì vậy, chạy đó và một lần Valgrind cho bạn và cung cấp cho bạn đi trước, sau đó bạn đã hoàn tất dỡ bỏ. 

Bây giờ, một vài lời khuyên trước khi bạn đi ra và bắt đầu thực hiện của bạn từ điển. Tôi muốn khuyên bạn nên để vượt qua trong một nhỏ hơn từ điển khi bạn đang cố gắng để kiểm tra những điều trên và gỡ lỗi với GDP. Việc sử dụng Speller là. / Speller, một từ điển tùy chọn, và sau đó là một văn bản. 

Theo mặc định, nó tải trong từ điển lớn. Vì vậy, bạn có thể muốn vượt qua trong nhỏ từ điển, hoặc thậm chí có thể làm cho bạn riêng, tùy biến từ điển của bạn và tập tin văn bản của bạn. 

Và cuối cùng, tôi cũng khuyên bạn nên để có một cây bút và giấy và vẽ những điều trên trước, trong, và sau khi bạn đã viết tất cả các mã của bạn. Chỉ cần chắc chắn rằng bạn đã có những con trỏ vừa phải. 

Tôi muốn bạn tốt nhất của may mắn. Và một khi bạn đã hoàn tất, nếu bạn muốn để thách thức các tàu lớn và xem cách nhanh chóng chương trình của bạn được so sánh với bạn cùng lớp của bạn, sau đó tôi khuyến khích bạn kiểm tra mà ra. 

Cùng với đó, bạn đã hoàn tất các PSet Speller. Tên tôi là Zamyla, và đây là CS50.