[Powered by Google Translate] [Walkthrough - Vấn đề Set 5]
[Zamyla Chan - Đại học Harvard]
[Đây là CS50. - CS50.TV]
>> Được rồi. Xin chào, tất cả mọi người, và được chào đón để Walkthrough 5.
>> 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ả.
Chính tả cờ là cực kỳ quan trọng.
Này đã từng xảy ra với bạn?
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 độ
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
và tất cả bởi vì bạn là spoiler liverwurst từ cá voi rộng.
Có, hiệu đính ớt của bạn là một vấn đề, bất lực tối đa.
Đây là một vấn đề có ảnh hưởng đến các sinh viên nam tính, nam tính.
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.
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,
chỉ để có được vào một đồng nghiệp tốt.
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à.
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,
Jale, hoặc nhà tù - bạn biết đấy, trong nhà tù, New Jersey.
Vì vậy, tôi nhận bản thân mình một kiểm tra chính tả.
Đó 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.
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.
>> 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ả,
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ả.
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
chỉ để hiểu các chức năng khác nhau mà từ điển của bạn là sẽ có.
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.
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
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,
mà chúng ta sẽ viết, sẽ là khá quan trọng.
Các spec pset cũng chứa rất nhiều thông tin hữu ích
về những điều mà bạn có thể giả định, quy tắc và những điều như thế,
vì vậy hãy chắc chắn để đọc các spec pset cẩn thận cho lời khuyên.
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
hoặc thảo luận.
Này pset sẽ phải dựa rất nhiều trên con trỏ,
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
ở phía trước tên và ampersands của con trỏ, làm thế nào để giải thoát họ, vv ...
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.
Chúng ta sẽ nhìn vào danh sách liên kết nhiều hơn một chút,
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ỏ
đế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.
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.
Chúng ta sẽ xem xét hai phương pháp chính, đó là bảng băm và sau đó cố gắng.
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
, nơi bạn có yếu tố liên kết với nhau.
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,
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ó
hoặc miễn phí tất cả các nút như đây.
Trong điều kiện của các nút giải phóng, đó là thực sự quan trọng
rằng bất cứ khi nào chúng ta malloc bộ nhớ, sau đó chúng tôi giải phóng nó.
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ớ.
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
và kiểm tra tất cả các bộ nhớ mà bạn được giao sau đó được giải phóng.
Pset của bạn chỉ được hoàn thành khi nó hoạt động và nó có đầy đủ chức năng,
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ớ.
Cuối cùng, cho pset này, tôi thực sự muốn nhấn mạnh -
Ý 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,
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
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.
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
vì nó có thể có được một chút lộn xộn.
>> Trước tiên, chúng ta hãy đi vào danh sách liên kết một chút.
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ó,
cũng như một con trỏ đến nút tiếp theo sau khi nó.
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ớ
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,
như vậy chúng ta có thể truy cập các nút nút đầu tiên
và sau đó một sau đó và sau đó.
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 đó
luôn luôn để trỏ đến NULL.
Khi một điểm nút NULL, sau đó bạn biết rằng bạn đã đạt đến cuối danh sách,
nút đó là một trong những cuối cùng, rằng không có gì sau đó.
Trong sơ đồ này, bạn thấy rằng các mũi tên con trỏ,
và phần màu xanh là nơi mà giá trị được lưu giữ,
và sau đó hộp màu đỏ với con trỏ đến nó là con trỏ của nút
trỏ đến nút tiếp theo sau khi nó.
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.
>> 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.
Và kể từ khi chúng tôi muốn có nhiều nút,
điều này sẽ trở thành một cấu trúc typedef
trong đó chúng ta sẽ có một số trường hợp khác nhau của các nút.
Và vì vậy chúng ta định nghĩa nó như là một kiểu dữ liệu mới.
Ở đây, chúng tôi có một nút typedef struct.
Trong ví dụ này, chúng ta đang đối phó với các nút số nguyên,
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ỏ,
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.
Và sau đó chúng tôi đang gọi nút này toàn bộ điều.
Hãy chắc chắn rằng bạn làm theo cú pháp này.
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.
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,
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.
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.
Vì vậy, người đứng đầu thực sự không chứa bất kỳ giá trị,
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à.
>> Để 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
để theo dõi đảm bảo rằng bạn duy trì chuỗi,
Tôi thích nghĩ về nó như những người trong một dòng nắm tay,
nơi mà mỗi người đang tay trong tay với một trong những kế tiếp.
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
đó là trong dây chuyền của họ.
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
tưởng tượng tất cả những người có giá trị liên kết với chúng
và cũng chỉ ra những người tiếp theo trong dòng -
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ị
hoặc tìm kiếm một giá trị hay một cái gì đó như thế,
sau đó bạn sẽ muốn có một con trỏ đến người cụ thể.
Vì vậy, chúng ta sẽ có một con trỏ dữ liệu Loại nút.
Đối với trường hợp này, chúng ta hãy gọi nó là con trỏ.
Một cách thông thường để tên này sẽ là iterator hoặc một cái gì đó như thế
bởi vì nó iterating trên và thực sự di chuyển nút nó trỏ đến.
Đây sẽ là con trỏ của chúng tôi.
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.
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ỏ,
di chuyển từ bên này sang bên kia.
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.
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.
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,
và đó sẽ là giá trị tiếp theo.
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
là chúng tôi muốn để có được giá trị mà con trỏ đang trỏ đến.
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.
Để có được đến nút thực tế mà con trỏ đang trỏ đến,
thông thường chúng ta chỉ ra nó (con trỏ).
Điều đó sẽ cung cấp cho bạn các nút thực tế mà con trỏ đang trỏ đến.
Và rồi sau đó, những gì chúng tôi muốn làm là chúng ta muốn truy cập
bất cứ điều gì là giá trị tiếp theo của nút.
Để 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.
Vì vậy, sau đó nó sẽ là (* con trỏ). Tiếp theo.
Nhưng đây là một chút lộn xộn về có dấu ngoặc xung quanh con trỏ *
và do đó, chúng tôi thay thế toàn bộ tuyên bố này với con trỏ->.
Đâ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.
con trỏ-> tiếp theo.
Đ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.
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.
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.
>> 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ị,
trước, chúng tôi đã có con trỏ-> tiếp theo,
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
node-> giá trị.
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.
Nếu nó là một nút int, sau đó con trỏ-> giá trị chỉ là sẽ là một số nguyên.
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
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,
bạn thực sự thay đổi giá trị của con trỏ.
Kể từ khi con trỏ là một con trỏ nút, bạn thay đổi địa chỉ con trỏ thực tế
đến địa chỉ của nút tiếp theo trong danh sách của bạn.
Đây chỉ là một số mã nơi bạn có thể lặp đi lặp lại.
Tôi có những nhận xét làm điều gì đó,
đó là nơi bạn có thể sẽ để truy cập vào các giá trị
hoặc làm điều gì đó để làm với nút cụ thể đó.
Để bắt đầu, tôi nói rằng con trỏ chuột của tôi ban đầu
để trỏ đến phần tử đầu tiên trong danh sách liên kết.
Và phía trước, tôi xác định là người đứng đầu của các nút.
>> Như tôi đã đề cập trước đây, giải phóng thực sự là quan trọng.
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ó.
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,
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ỏ.
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ớ.
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
sẽ bị mất.
Trở lại ví dụ người để làm cho nó cổ phần cao hơn một chút,
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.
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
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ọ.
Ví dụ, nếu bạn chỉ đơn giản là gọi miễn phí trên anh chàng này ở đây,
sau đó ông sẽ được giải thoát, nhưng sau đó tất cả những kẻ sau đó sẽ bị mất
và họ sẽ trôi đi và rơi xuống.
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.
Con trỏ đầu của chúng tôi, chỉ vào phần tử đầu tiên trong danh sách.
Nó là loại giống như một sợi dây thừng neo người đầu tiên.
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ó -
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
điểm mà bất cứ các yếu tố đầu tiên.
Vì vậy, bạn có con trỏ tạm thời của bạn chỉ ở đây.
Bằng cách đó, chúng tôi có một tổ chức của nút đầu tiên.
Và sau đó, kể từ khi chúng ta biết rằng nút đầu tiên sẽ được giải thoát,
sau đó chúng ta có thể di chuyển dây thừng, neo, người đứng đầu của chúng tôi,
để thực sự trỏ đến bất cứ điều gì một trong những đầu tiên được trỏ đến.
Vì vậy, đầu này thực sự chỉ vào phần tử thứ hai.
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 độ,
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.
Một cách khác mà bạn có thể làm điều này có thể được
mỗi khi bạn chỉ cần miễn phí các phần tử cuối cùng trong danh sách
bởi vì họ sẽ được bảo đảm không được chỉ tới bất cứ điều gì.
Vì vậy, bạn chỉ có thể miễn phí này, sau đó tự do này, sau đó miễn phí này.
Đ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,
chúng ta không thể ngay lập tức nhảy đến người cuối cùng.
Chúng tôi phải đi qua từng phần tử trong danh sách liên kết
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,
và sau đó một khi chúng ta đạt được kết thúc, sau đó miễn phí mà.
Nếu bạn đã làm quá trình này, bạn thực sự sẽ được kiểm tra ở đây,
kiểm tra ở đây, sau đó kiểm tra ở đây, giải phóng nó,
sau đó sẽ trở lại, kiểm tra ở đây, kiểm tra ở đây, giải phóng nó,
kiểm tra ở đây, và sau đó giải phóng nó.
Điều đó cần có thời gian nhiều hơn một chút. Yeah.
>> [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?
Điều đó chắc chắn sẽ là có thể.
Để 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
như vậy mà bạn có một con trỏ trỏ đến cuối của danh sách liên kết?
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
bạn sẽ phải cập nhật con trỏ và vật như thế.
Bạn sẽ có một cái đuôi * nút, ví dụ.
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,
như bao nhiêu lần tôi sẽ được lặp lại trên này,
khó khăn như thế nào là nó sẽ được theo dõi của đuôi cũng như đầu
cũng như iterator của tôi, và những thứ như thế.
Điều đó? >> [Sinh viên] Yeah.
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.
>> 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.
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ỏ
iterator.
Chúng tôi đang lặp lại cho đến khi con trỏ là NULL.
Bạn không muốn để lặp lại khi con trỏ của bạn là NULL
bởi vì điều đó có nghĩa rằng không có bất cứ điều gì trong danh sách.
Vì vậy, sau đó ở đây tôi làm cho một nút tạm thời *
chỉ với những gì tôi đang xem xét đầu tiên trong danh sách của tôi,
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.
>> Bây giờ chúng ta chèn vào danh sách liên kết.
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
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.
Để làm được điều đó, tất cả chúng ta sẽ làm là chúng ta sẽ đi qua
để 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 -
đó là một trong những điều này -
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;
chúng tôi đang thực sự sẽ có một số khác.
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.
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.
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.
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. Ở đó.
>> 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?
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
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.
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.
Ví dụ, chúng ta hãy gọi đây là thứ hai.
Nếu bạn nói một trong những thứ hai tại điểm này mới
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
bởi vì không có bất cứ liên kết nào với anh ta.
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.
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.
Chúng tôi phải đảm bảo rằng chúng tôi giữ đến người cuối cùng.
Những gì chúng tôi có thể muốn làm là có một con trỏ tạm thời
các yếu tố đó sẽ được nối trên.
Vì vậy, sau đó chúng tôi có một con trỏ tạm thời.
Kể từ khi chúng ta biết rằng 1/3 này đang được lưu giữ theo dõi,
2 bây giờ có thể liên kết sang cái mới của chúng tôi.
Và nếu anh chàng này màu đỏ mới là có được giữa 2 và 3,
sau đó của anh chàng đó con trỏ để trỏ đến những gì? >> [Sinh viên] Temp.
Temp. Yeah.
Vì vậy, sau đó giá trị tiếp theo của anh chàng này màu đỏ sẽ là tạm thời.
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ể
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,
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,
sau đó nó sẽ mất một chút xáo trộn xung quanh.
Nếu bạn muốn, ví dụ, có một danh sách được sắp xếp liên kết,
sau đó bạn phải loại cân nhắc chi phí và lợi ích của thế
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ó,
nó sẽ mất thời gian nhiều hơn một chút.
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,
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ự.
Vì vậy, bạn có thể muốn cân nhắc chi phí và lợi ích của thế.
>> 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.
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 -
và sau đó có những người này liên kết với nó,
và sau đó chúng tôi có một nút mới được chèn vào đầu,
sau đó những gì chúng ta có thể muốn làm gì?
Đ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,
bởi vì đó là một trong những đầu tiên?
Điều gì sẽ xảy ra ở đây?
Tất cả ba sẽ bị lạc.
Vì vậy, chúng tôi không muốn làm điều đó.
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.
Hãy lựa chọn để có một điểm tạm thời với anh chàng này.
Sau đó, chúng ta có thể có một điểm màu xanh để tạm thời
và sau đó các điểm màu đỏ sang màu xanh.
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
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ọ
trước khi chúng ta để cho đi của một tay hoặc một cái gì đó như thế.
>> 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
và tạo ra các cấu trúc đó bao gồm các định nghĩa kiểu cho nút
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 đó -
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,
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ọ,
sau đó chúng ta có thể nhận được vào các lỗi chính tả.
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
và cấu trúc khác nhau như hàng đợi và ngăn xếp.
Sau đó, chúng ta có thể di chuyển vào các lỗi chính tả.
>> Lỗi chính tả có trong mã phân phối một vài các tập tin quan trọng.
Trước tiên, chúng tôi nhận thấy rằng chúng ta có Makefile này đây,
mà chúng tôi đã không thực sự gặp phải trước đây.
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,
sau đó bạn có hai c tập tin.
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
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.
Makefile không cho phép chúng tôi biên dịch tập tin cùng một lúc
và vượt qua trong những lá cờ mà chúng tôi muốn.
Ở đây chúng ta chỉ thấy có một tập tin tiêu đề ở đây.
Sau đó, chúng tôi thực sự có hai tập tin nguồn.
Chúng tôi có speller.c và dictionary.c.
Bạn được chào đón để chỉnh sửa các Makefile nếu bạn muốn.
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ì
đó là cốt lõi.
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.
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à.
Bạn sẽ muốn loại bỏ để làm cho nó sạch.
Nó loại bỏ bất kỳ tập tin exe và các tập tin o.
>> Hãy có một cái nhìn vào dictionary.h.
Điều này nói rằng tuyên bố chức năng của từ điển.
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.
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.
Vì vậy, chúng tôi sẽ không có bất kỳ từ nào vượt quá độ dài.
Ở đây chúng ta chỉ có các nguyên mẫu chức năng.
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.
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
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.
để 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.
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.
Sau đó, họ sẽ nói chức năng tải của tôi,
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.
Ở đây chúng tôi đã kiểm tra, mà trả về true nếu một từ có trong từ điển.
Sau đó, chúng tôi có tải, mà về cơ bản có trong một tập tin từ điển
và sau đó tải nó vào một số cấu trúc dữ liệu.
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,
bao nhiêu từ được lưu trong đó,
và sau đó dỡ bỏ, mà giải phóng tất cả các bộ nhớ mà bạn có thể đã đưa lên
trong khi làm cho từ điển của bạn.
>> Chúng ta hãy nhìn vào dictionary.c.
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ó.
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.
Dictionary.c, khi chạy, không thực sự sẽ làm bất cứ điều gì,
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ả.
Mặc dù bạn sẽ không thể chỉnh sửa bất kỳ của mã này,
đ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,
chỉ để hiểu, bản đồ nó ra, chức năng hoạt động như thế nào.
Chúng tôi thấy rằng nó kiểm tra cho việc sử dụng chính xác.
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
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.
Và sau đó họ phải vượt qua trong văn bản để kiểm tra chính tả.
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
không chỉ nhận được một chức năng kiểm tra chính tả làm việc
nhưng thực sự nhận được nó để được nhanh chóng.
Và như vậy thì đó là nơi rusage sẽ đến.
Ở đâ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.
Tải trả về đúng hay sai - đúng khi thành công, false khi thất bại.
Vì vậy, nếu từ điển không load được, sau đó speller.c sẽ trở về 1 và bỏ thuốc lá.
Nhưng nếu nó không tải đúng cách, sau đó nó sẽ để tiếp tục.
Chúng tôi tiếp tục, và chúng ta thấy một số tập tin I / O ở đây,
mà nó sẽ được giao dịch với mở các tập tin văn bản.
Ở đâ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.
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
và sau đó kiểm tra trong từ điển.
Ở đâ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.
Nếu từ đó thực sự có trong từ điển, sau đó kiểm tra sẽ trở lại đúng sự thật.
Điều đó có nghĩa rằng từ ngữ này không sai chính tả.
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.
Chúng tôi tiếp tục đi, và sau đó nó theo dõi có bao nhiêu từ sai chính tả
có trong tập tin.
Nó tiếp tục và đóng file.
Sau đó, ở đây, nó báo cáo bạn đã có bao nhiêu từ sai chính tả.
Nó tính toán mất bao nhiêu thời gian để tải các từ điển,
mất bao nhiêu thời gian để kiểm tra xem nó,
bao nhiêu thời gian đã mất để tính toán kích thước,
, như chúng ta sẽ đi về, nên rất nhỏ,
và sau đó mất bao nhiêu thời gian để dỡ bỏ các từ điển.
Ở đây lên trên chúng ta thấy các cuộc gọi dỡ bỏ ở đây.
Nếu chúng ta kiểm tra các kích thước ở đây,
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.
Awesome.
>> 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
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ử -
từ tập tin từ điển.
Sau đó, bạn có kích thước, mà sẽ trả về số từ trong từ điển.
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.
Sau đó, bạn đã kiểm tra, đó sẽ kiểm tra nếu một từ có trong từ điển.
Vì vậy, speller.c qua trong một chuỗi, và sau đó bạn phải kiểm tra xem chuỗi đó
được chứa trong từ điển của bạn.
Chú ý rằng chúng ta thường có từ điển tiêu chuẩn,
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ữ.
Vì vậy, chúng ta không thể giả định rằng từ bên trong.
FOOBAR từ có thể được định nghĩa trong từ điển nào đó mà chúng tôi vượt qua.
Và sau đó chúng tôi đã dỡ bỏ, mà giải phóng từ điển từ bộ nhớ.
>> Trước tiên, tôi muốn đi qua các phương pháp bảng băm
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,
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,
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
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ớ.
>> Chúng ta hãy vào phương pháp bảng băm.
Một bảng băm bao gồm một danh sách các nhóm.
Mỗi giá trị, từng chữ, để đi vào một trong những xô.
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
và sau đó phổ biến nhất trong xô như vậy mà mỗi thùng
có khoảng một số lượng tương đương giá trị trong nó.
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.
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ề,
xô nó thuộc về, và sau đó đặt nó vào danh sách liên kết liên quan đến thùng đó.
Ở đây, những gì tôi có là một hàm băm.
Đây là một bảng băm int.
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.
Bất kỳ số nguyên trên 10 nhưng dưới đi 20 vào thứ hai,
và sau đó vv và vv.
Đối với tôi, với mỗi nhóm đại diện cho những con số này.
Tuy nhiên, nói rằng tôi đã phải vượt qua trong 50, ví dụ.
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.
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,
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.
Và như vậy thì sẽ dẫn đến một loại bảng băm không cân bằng.
Nói cách khác, một bảng băm chỉ là một mảng của các nhóm
xô hàng là một danh sách liên kết.
Và do đó, để xác định giá trị mỗi đi, mà xô nó đi vào,
bạn sẽ muốn những gì được gọi là một hàm băm
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.
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ị.
Kiểm tra xem nó đã được ít hơn 10.
Nếu nó được, nó sẽ đặt nó vào xô đầu tiên.
Nó kiểm tra cho dù đó là ít hơn 20, đặt nó vào thứ hai nếu đúng,
kiểm tra nếu nó ít hơn 30, và sau đó đặt nó vào xô thứ ba,
và sau đó tất cả các khác chỉ rơi vào xô thứ tư.
Vì vậy, bất cứ khi nào bạn có một giá trị, hàm băm của bạn
sẽ đặt giá trị đó vào xô thích hợp.
Hàm băm cơ bản cần biết bạn có bao nhiêu xô.
Kích thước bảng băm của bạn, số lượng thùng mà bạn có,
đó sẽ là một số cố định đó là cho bạn, để bạn quyết định,
nhưng nó sẽ là một con số cố định.
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
như vậy mà nó phân bố đều.
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
thực sự là sẽ có một char.
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,
có ý nghĩa bởi vì nó sẽ là một danh sách liên kết.
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 *
đã được trỏ đến nút đầu tiên trong danh sách liên kết.
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,
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ì?"
Xô chỉ là một danh sách các nút con trỏ,
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.
Để trở lại sơ đồ này, bạn thấy rằng bản thân xô là các mũi tên,
không thực tế các nút.
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.
Điều đó có nghĩa rằng bất cứ khi nào bạn băm số 2,
nó luôn luôn phải trả lại cùng một thùng.
Mỗi giá trị duy nhất mà đi vào hàm băm, nếu lặp đi lặp lại,
để có được các chỉ số tương tự.
Vì vậy, hàm băm của bạn trả về chỉ số của mảng
nơi mà giá trị đó thuộc về.
Như tôi đã đề cập trước đây, số lượng nhóm là cố định,
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
nhưng lớn hơn 0.
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
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
nếu chúng ta biết đặc tính của một giá trị -
thay vì phải tìm kiếm thông qua toàn bộ toàn bộ từ điển,
có thể nhảy đến một phần nhất định của nó.
Hàm băm của bạn nên đưa vào tài khoản mà lý tưởng,
mỗi nhóm có khoảng cùng một số phím.
Kể từ khi bảng băm là một loạt các danh sách liên kết,
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.
Trong ví dụ trước, hai số khác nhau, mặc dù họ đã không bằng nhau,
khi băm, sẽ trở lại cùng một chỉ số.
Vì vậy, khi bạn đang đối phó với các từ, một từ khi băm
sẽ là giá trị hash giống nhau như một từ khác.
Đó 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,
danh sách liên kết thùng đó không phải là sản phẩm nào.
Kỹ thuật mà chúng ta gọi là tuyến tính thăm dò,
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
bởi vì bạn có một vụ va chạm.
Bạn có thể thấy rằng có thể có một thương mại-off ở đây, phải không?
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,
sau đó bạn sẽ có rất nhiều va chạm.
Nhưng sau đó nếu bạn thực hiện một bảng rất lớn băm,
bạn có thể sẽ giảm thiểu các va chạm,
nhưng nó sẽ là một dữ liệu rất lớn.
Có sẽ là thương mại-off với điều đó.
Vì vậy, khi bạn đang làm cho pset của bạn, hãy thử để chơi xung quanh
giữa có thể làm cho một bảng băm nhỏ
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
của những danh sách liên kết.
>> Tải sẽ làm là lặp qua tất cả các từ trong từ điển.
Nó vượt qua trong một con trỏ đến các tập tin từ điển.
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
và duyệt qua tất cả các từ trong từ điển.
Bạn muốn mỗi từ trong từ điển để trở thành một nút mới,
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.
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.
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ó.
Ở đâ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.
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ữ
một từ và sau đó một dòng mới, những gì chúng ta có thể tận dụng
là fscanf chức năng,
theo đó các tập tin là tập tin từ điển mà chúng tôi đang thông qua,
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.
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
và loại bóc các lớp trở lại trên thư viện CS50,
chúng ta đã thấy một thực hiện fscanf.
Để trở lại fscanf, chúng tôi có các tập tin mà chúng tôi đang đọc từ,
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
ở đây tôi có new_node-> từ vì new_node là một con trỏ nút,
không phải là một nút thực tế.
Vì vậy, sau đó tôi nói new_node, tôi muốn đi tới nút mà nó trỏ đến
và sau đó gán giá trị từ.
Chúng tôi muốn để rồi mất từ ​​đó và chèn nó vào bảng băm.
Nhận ra rằng chúng tôi đã thực hiện new_node một con trỏ nút
bởi vì chúng ta sẽ muốn biết địa chỉ của nút đó là những gì
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,
là họ có một con trỏ đến một nút mới.
Vì vậy, sau đó địa chỉ của nút đó để trỏ đến là gì?
Địa chỉ đó sẽ được new_node.
Đó 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?
Okay.
Chúng tôi có một lời. Đó là giá trị new_node-> từ.
Có chứa một từ trong từ điển mà chúng tôi muốn đầu vào.
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 đó
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,
số nguyên đó là chỉ số hashtable tại chỉ số đó đại diện cho rằng xô.
Chúng tôi muốn đi mà chỉ số và sau đó đi rằng chỉ số của bảng băm
và sau đó sử dụng danh sách liên kết để chèn các nút new_node.
Hãy nhớ rằng tuy nhiên bạn quyết định để chèn nút của bạn,
cho dù đó là ở giữa nếu bạn muốn sắp xếp nó
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
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.
>> 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,
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à
chúng tôi đi qua mọi phần tử trong bảng băm của chúng tôi
và sau đó lặp qua tất cả các danh sách liên kết trong bảng băm
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.
Nhưng mỗi khi kích thước được gọi là, sẽ mất một thời gian dài
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.
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.
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
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,
sẽ có thể được truy cập bằng cách kích thước.
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,
kích thước của từ điển, mà bạn đã xử lý trong tải.
Đó 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,
sau đó kích thước là có được khá dễ dàng.
>> Vì vậy, bây giờ chúng tôi nhận được để kiểm tra.
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,
và do đó, chúng ta sẽ kiểm tra xem tất cả của những từ đầu vào
thực sự có trong từ điển hay không.
Tương tự như Scramble, chúng tôi muốn cho phép trường hợp vô cảm.
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,
khi được gọi với so sánh chuỗi, là tương đương.
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.
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,
sẽ được, hoặc chữ cái hoặc chứa các dấu nháy.
Apostrophes đang có được từ hợp lệ trong từ điển của chúng tôi.
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
đó sẽ là một trong các nút trong bảng băm của bạn.
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.
Nếu từ đó trong từ điển, sau đó tất cả các từ có trong từ điển trong bảng băm,
do đó, chúng ta hãy tìm từ này trong bảng băm.
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
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ị,
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ộ,
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ề.
Nếu nó đã có trong từ điển, sau đó nó sẽ được trong thùng đó.
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,
chúng ta có thể chỉ cần băm từ đó và nhìn vào danh sách liên kết
giá trị của hashtable [hash (word)].
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,
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,
và sau đó gọi chuỗi so sánh khi từ bất cứ nơi nào con trỏ đang trỏ đến,
từ đó, và xem liệu những so sánh.
Tùy thuộc vào cách mà bạn tổ chức hàm băm của bạn,
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,
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
cho đến khi bạn tìm thấy những yếu tố cuối cùng của danh sách.
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,
điều đó có nghĩa là từ đó không tồn tại trong từ điển,
và do đó, từ đó là không hợp lệ,
và kiểm tra trả về false.
>> 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
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.
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 đó.
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,
sau đó bạn sẽ muốn lặp lại quá trình cho mọi phần tử trong bảng băm.
Và tôi sẽ đi qua vào cuối của hương,
nhưng Valgrind là một công cụ mà bạn có thể thấy nếu bạn đã giải phóng
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.
Vì vậy đó là bảng băm, nơi chúng tôi có một số hữu hạn xô
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.
>> Bây giờ chúng ta cố gắng.
Cố gắng loại giống như thế này, và tôi cũng sẽ vẽ ra một ví dụ.
Về cơ bản, bạn có một mảng toàn bộ thư tiềm năng,
và sau đó bất cứ khi nào bạn đang xây dựng một từ,
thư có thể liên kết một từ điển để một loạt các khả năng.
Một số từ bắt đầu với C, nhưng sau đó tiếp tục với A,
nhưng những người khác tiếp tục với O, ví dụ.
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ừ đó.
Một Trie để theo dõi các trình tự của các chữ cái mà bao gồm từ,
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,
và cuối cùng cho thấy tại mỗi điểm cho dù từ đó là hợp lệ hay không
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à.
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ệ.
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,
và chúng ta sẽ có, cụ thể, 27 của những người con trỏ nút,
một cho mỗi chữ trong bảng chữ cái cũng như các ký tự dấu nháy đơn.
Mỗi phần tử trong mảng đó để trỏ đến một nút khác.
Vì vậy, nếu nút đó là NULL, nếu không có gì sau đó,
sau đó chúng tôi biết rằng có thêm không có chữ cái trong chuỗi từ.
Nhưng nếu nút đó không phải là NULL, đó có nghĩa là có chữ hơn trong chuỗi thư.
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.
>> Chúng ta hãy đi vào một ví dụ về Trie.
Đầu tiên tôi có chỗ cho 27 nút trong mảng này.
Nếu tôi có BAR từ -
Nếu tôi có BAR từ và tôi muốn để chèn trong,
chữ cái đầu tiên là B, vì vậy nếu Trie của tôi là trống rỗng,
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.
Tôi sẽ có B ở đây.
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
có thể theo sau khi lá thư B.
Trong trường hợp này, tôi đang đối phó với BAR từ, do đó, A sẽ đi đây.
A, tôi có chữ R, do đó, sau đó tại điểm kết hợp của riêng của nó,
và sau đó R sẽ có mặt ở đây.
BAR là một từ hoàn chỉnh, vì vậy sau đó tôi sẽ có R điểm nút khác
nói rằng từ đó là hợp lệ.
Nút đó cũng sẽ có một mảng của các nút,
nhưng những người có thể là NULL.
Nhưng về cơ bản, nó có thể tiếp tục như thế.
Đ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,
do đó, chỉ cần chịu với tôi.
Bây giờ chúng tôi có BAR bên trong từ điển của chúng tôi.
Bây giờ nói rằng chúng ta có Baz từ.
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.
Đó là theo sau với A. Chúng tôi đã có A.
Nhưng sau đó thay vào đó, chúng ta có Z sau đây.
Vì vậy, sau đó một phần tử trong mảng của chúng tôi là có được Z,
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.
Vì vậy, chúng ta thấy rằng khi chúng tôi tiếp tục qua B và sau đó,
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.
Nói rằng chúng tôi muốn để chèn FOOBAR từ.
Sau đó, chúng tôi sẽ thực hiện một mục tại F.
F là một nút chỉ vào một mảng toàn.
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.
Chúng ta sẽ có B và sau đó tiếp tục, chúng tôi phải A và sau đó R.
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.
Và như vậy thì đây sẽ là một từ hợp lệ.
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ừ.
Chúng tôi sẽ nói F. gì sau F?
Tôi thực sự đã có một không gian cho O, vì vậy tôi sẽ tiếp tục.
Tôi không cần phải thực hiện một hình mới. Tiếp tục.
FOO là một từ hợp lệ trong từ điển này, do đó, sau đó tôi sẽ để cho biết
rằng đó là hợp lệ.
Nếu tôi dừng lại trình tự của tôi ở đó, đó sẽ là chính xác.
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
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ệ.
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,
và sau đó mỗi node cũng có một mảng 27 con trỏ nút
mà sau đó trỏ đến các nút tự.
>> Đây là một cách làm thế nào bạn có thể muốn xác định điều này.
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
để 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
một số cách để biết nơi bắt đầu của Trie của chúng tôi là.
Một số người gọi những người cố gắng cây, và đó là nơi gốc đến từ.
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ứ
bất cứ nơi nào Trie của chúng tôi là.
Chúng tôi đã loại đã đi qua
cách bạn có thể nghĩ về tải mỗi từ vào từ điển.
Về cơ bản, cho mỗi từ, bạn sẽ muốn để lặp qua Trie của bạn
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 -
tương ứng với một lá thư khác nhau, bạn sẽ muốn kiểm tra những giá trị
rằng chỉ số cụ thể tương ứng với chữ cái.
Vì vậy, suy nghĩ tất cả các cách trở lại Caesar và Vigenere,
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,
chắc chắn từ A đến Z là có được khá dễ dàng để bản đồ đến một chữ cái,
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ừ.
Tôi thậm chí không chắc chắn những gì giá trị ASCII,
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
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 đó
và sau đó đưa rằng trong 26 chỉ số, ví dụ.
Vì vậy, sau đó bạn đang kiểm tra giá trị ở trẻ em [i]
[i] tương ứng với bất kỳ bức thư bạn đang ở.
Nếu đó là NULL, điều đó có nghĩa rằng không có bất cứ lá thư nào có thể
bắt nguồn từ đó trình tự trước đó, vì vậy bạn sẽ muốn để malloc
và thực hiện một nút mới và rằng trẻ em [i] trỏ đến nó
để bạn tạo ra - khi chúng ta chèn một ký tự vào hình chữ nhật -
làm cho trẻ không NULL và điểm vào nút đó mới.
Nhưng nếu đó không phải là NULL, như trong trường hợp của chúng tôi FOO
khi chúng tôi đã có FOOBAR, chúng tôi tiếp tục,
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
ở cuối của từ đó.
>> 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,
nó sẽ được dễ dàng hơn cho bạn cho kích thước, thay vì phải tính toán
và đi qua toàn bộ cây và tính toán để tôi có bao nhiêu trẻ em
và sau đó phân nhánh ra, nhớ bao nhiêu là ở phía bên trái và bên phải
và những thứ như thế, nó sẽ được dễ dàng hơn nhiều cho bạn
nếu bạn chỉ theo dõi bao nhiêu từ bạn đang thêm trong
khi bạn đang làm việc với tải.
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.
>> Bây giờ chúng tôi đến để kiểm tra.
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.
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
vì trẻ em là một mảng của 27 dài,
do đó, tất cả các chữ cái của bảng chữ cái cộng với dấu lược.
Đố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
bởi vì gốc rễ sẽ trỏ đến một mảng có chứa
tất cả đều bắt đầu từ chữ cái có thể của một từ.
Bạn sẽ bắt đầu ở đó,
và sau đó bạn sẽ phải kiểm tra giá trị NULL hay không,
bởi vì nếu giá trị là NULL, có nghĩa là từ điển không có bất kỳ giá trị
có chứa lá thư đó theo thứ tự cụ thể.
Nếu nó NULL, thì đó có nghĩa rằng từ này bị sai chính tả ngay lập tức.
Nhưng nếu nó không phải là NULL, sau đó bạn có thể tiếp tục,
nói rằng chữ cái đầu tiên là chữ cái đầu tiên có thể có trong một từ,
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.
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
và kiểm tra xem lá thư thứ hai tồn tại.
Sau đó, bạn lặp lại quá trình để kiểm tra xem chuỗi đó là hợp lệ hay không
trong Trie của bạn.
Bất cứ khi nào con cái nút đó điểm NULL,
bạn biết rằng chuỗi không tồn tại,
nhưng sau đó nếu bạn đến cuối của từ mà bạn đã đầu vào,
sau đó bạn muốn kiểm tra ngay bây giờ mà tôi đã hoàn thành trình tự này
và thấy nó trong Trie tôi, là từ hợp lệ hay không?
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ự đó,
sau đó bạn muốn kiểm tra xem từ đó là hợp lệ hay không
bởi vì nhớ lại trong trường hợp trước mà tôi đã vẽ mà chúng tôi đã FOOB,
đó 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ó.
>> 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.
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,
trong cố gắng chúng tôi cũng muốn giải phóng tất cả các nút.
Dỡ bỏ thực sự sẽ làm việc dễ dàng nhất từ ​​dưới lên trên
bởi vì đây là danh sách cơ bản liên kết.
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ị
và miễn phí tất cả trong số họ một cách rõ ràng.
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
là để đi du lịch để dưới cùng và nút thấp nhất có thể miễn phí đầu tiên
và sau đó đi lên cho tất cả những đứa trẻ và sau đó tất cả những người,
đi lên và sau đó miễn phí, vv
Loại giống như đối phó với lớp dưới cùng những người đầu tiên Trie
và sau đó đi lên trên một khi bạn đã giải thoát tất cả mọi thứ.
Đây là một ví dụ tốt về chức năng đệ quy có thể có ích.
Một khi bạn đã trả tự do cho lớp dưới cùng của Trie của bạn,
sau đó bạn gọi dỡ bỏ phần còn lại của nó,
làm cho chắc chắn rằng bạn tự do mỗi nhỏ -
Loại có thể hình dung nó như là cố gắng nhỏ.
Vì vậy, bạn có gốc của bạn ở đây.
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ọ.
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ừ
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.
Hãy tiếp tục nhiều hơn một chút.
Những gì bạn sẽ muốn làm là miễn phí dưới đây và sau đó miễn phí này
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
bởi vì nếu bạn một cái gì đó ở cấp độ thứ hai ở đây,
sau đó bạn thực sự sẽ mất giá trị này ở đây.
Đó 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.
Những gì bạn có thể muốn làm là nói cho tất cả các nút
Tôi muốn để dỡ bỏ tất cả các em.
>> 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,
chúng ta sẽ muốn nhìn vào Valgrind.
Valgrind bạn chạy với các lệnh sau đây.
Bạn có valgrind-v.
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
vì speller cần phải có trong một tập tin văn bản.
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,
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 đủ
hoặc cho dù bạn không đủ tự do,
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
và do đó, nó sẽ trở lại lỗi.
Nếu bạn sử dụng Valgrind, nó sẽ cho bạn một số thông điệp
chỉ ra cho dù bạn đã giải phóng hoặc làm việc ít hơn, đủ, vừa đủ,
hoặc nhiều hơn đủ thời gian.
>> Một phần của pset này, đó là tùy chọn để thách thức Ban Big.
Nhưng khi chúng ta đang đối phó với các cấu trúc dữ liệu
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ả.
Băm kết quả trong rất nhiều va chạm chức năng của bạn?
Hoặc là kích thước dữ liệu của bạn thực sự lớn?
Liệu nó mất rất nhiều thời gian để đi qua?
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,
để kiểm tra, tiến hành kích thước, và dỡ bỏ,
và do đó, những được đăng trong Ban Big,
nơi bạn có thể cạnh tranh với các bạn cùng lớp của bạn
và một số nhân viên để xem ai có nhanh nhất kiểm tra chính tả.
Một điều mà tôi muốn lưu ý về các bảng băm
là có một số chức năng khá đơn giản băm mà chúng ta có thể nghĩ ra.
Ví dụ, bạn có 26 thùng, mỗi thùng
tương ứng với chữ cái đầu tiên trong một từ,
nhưng đó là đi đến kết quả trong một bảng băm khá cân bằng
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ụ.
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,
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
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.
Có rất nhiều tài nguyên trên Internet cho các chức năng băm,
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
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ừ.
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.
Lại cho rằng, bạn có thể có thể để xem nếu có ai đó sử dụng một Trie
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.
Bạn có thể trình Ban Big nhiều lần.
Nó sẽ ghi lại mục nhập của bạn gần đây nhất.
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
hoặc chậm hơn rất nhiều so với trước đây.
Đó là một chút của một cách thú vị.
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ể,
vì vậy đó là luôn luôn vui vẻ để xem xét.
>> Sử dụng cho các pset là bạn chạy speller với một từ điển tùy chọn
và sau đó là một tập tin văn bản bắt buộc.
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,
nó sẽ sử dụng các tập tin văn bản từ điển, lớn
trong thư mục cs50/pset5/dictionaries.
Một trong đó có hơn 100.000 từ.
Họ cũng có một cuốn từ điển nhỏ, trong đó có những từ ngữ ít hơn đáng kể
CS50 đã thực hiện cho bạn.
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
nếu bạn chỉ muốn được làm việc trong các ví dụ nhỏ
ví dụ, nếu bạn muốn sử dụng gdb và bạn biết các giá trị cụ thể
mà bạn muốn bảng băm của bạn để vạch ra.
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,
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,
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ừ
để bạn biết sản lượng nên được chính xác những gì.
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
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ế.
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
có chứa chỉ có một vài từ hoặc có thể 10
để bạn có thể dự đoán kết quả
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.
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,
một lần nữa tôi muốn khuyến khích bạn sử dụng bút và giấy
bởi vì nó thực sự sẽ giúp bạn với một trong những điều này -
vẽ các mũi tên, bảng băm hoặc Trie của bạn trông như thế nào,
khi bạn giải phóng một cái gì đó mà các mũi tên,
đang nắm giữ đủ, bạn có thấy bất kỳ liên kết biến mất
và rơi vào vực thẳm của bộ nhớ bị rò rỉ.
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.
Vẽ những điều trên để bạn hiểu những điều sẽ làm việc
bởi vì sau đó tôi đảm bảo bạn sẽ chạy vào ít muddles con trỏ ở đó.
>> Được rồi.
Tôi muốn chúc bạn tốt nhất của may mắn với pset này.
Đây có thể là một trong những khó khăn nhất.
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.
Walkthrough 5.
>> [CS50.TV]