[MUSIC CHƠI] 

Andi PENG: Chào mừng bạn đến tuần 6 phần. Chúng tôi đã đi trệch khỏi tiêu chuẩn của chúng tôi Phần thứ ba của thời gian buổi chiều đến sáng chủ nhật đáng yêu này. Cảm ơn bạn cho tất cả mọi người mà tham gia cùng tôi ngày hôm nay, nhưng nghiêm túc, một tràng pháo tay. 

Đó là một nỗ lực khá lớn. Tôi gần như đã thậm chí không làm cho nó lên trong thời gian, nhưng nó là OK. Vì vậy, tôi biết rằng tất cả các bạn đã đã thực hiện nó vào bài kiểm tra. Trước hết, chào mừng mặt trái của điều đó. 

Thứ hai, chúng ta sẽ nói về nó. Chúng ta sẽ nói về các bài kiểm tra. Chúng tôi sẽ nói về cách bạn đang làm trong lớp. Bạn se ổn thôi. Tôi có câu đố của bạn bạn vào cuối ở đây, vì vậy nếu các bạn muốn đi một nhìn vào nó, hoàn toàn tốt. 

Vì vậy, một cách nhanh chóng trước khi chúng tôi bắt đầu, chương trình nghị sự cho ngày hôm nay là như sau. Như bạn có thể thấy, chúng tôi bắn nhanh cơ bản thông qua một bó toàn bộ các cấu trúc dữ liệu thực sự, thực sự, thực sự nhanh chóng. Vì vậy, như vậy, nó sẽ không được siêu tương tác ngày hôm nay. Nó sẽ chỉ là tôi loại la hét điều mà bạn, và nếu tôi làm bạn bối rối, nếu tôi đi quá nhanh, cho tôi biết. Chúng chỉ khác nhau dữ liệu cấu trúc, và như là một phần pset của bạn cho việc này tuần sắp tới, bạn sẽ được yêu cầu để thực hiện một trong số họ, có lẽ hai them-- hai người trong pset của bạn. OK, vì vậy tôi chỉ cần đi để bắt đầu với một số thông báo. Chúng tôi sẽ đi qua ngăn xếp và hàng đợi nhiều hơn ở sâu hơn so với những gì chúng ta đã làm trước các bài kiểm tra. Chúng tôi sẽ đi qua liên kết liệt kê một lần nữa, một lần nữa, sâu hơn so với những gì chúng tôi đã có trước khi các bài kiểm tra. Và sau đó chúng ta sẽ nói về băm bảng, cây và cố gắng, mà là tất cả khá cần thiết cho pset của bạn. Và sau đó chúng ta sẽ đi qua một số lời khuyên hữu ích cho pset5. 

OK, vậy đố 0. Trung bình là 58%. Nó là rất thấp, và do đó các bạn tất cả đã làm rất, rất tốt phù hợp với. 

Khá nhiều, nguyên tắc nhỏ là nếu bạn trong vòng một độ lệch chuẩn của giá trị trung bình đặc biệt là kể từ khi chúng tôi đang ở trong một ít phần thoải mái, bạn hoàn toàn tốt. Bạn đang đi đúng hướng. Cuộc sống là tốt. 

Tôi biết nó đáng sợ khi nghĩ rằng Tôi đã như một 40% trên bài kiểm tra này. Tôi sẽ không lớp này. Tôi hứa với bạn, bạn không sẽ thất bại lớp. Bạn hoàn toàn tốt. 

Đối với những người bạn của những người đã vượt qua giá trị trung bình, ấn tượng, ấn tượng, như, nghiêm túc thực hiện tốt. Tôi có họ với tôi. Hãy đến đón chúng ở cuối phần. Hãy cho tôi biết nếu bạn có bất kỳ vấn đề, câu hỏi với họ. Nếu chúng ta cộng số điểm của bạn sai, hãy cho chúng tôi biết. 

OK, vì vậy pset5, đây là một thực sự tuần lạ cho Yale trong ý nghĩa rằng pset chúng tôi là do Thứ Tư lúc trưa bao gồm Vào cuối ngày, vì vậy nó thực sự về mặt lý thuyết do thứ ba vào buổi trưa. Có lẽ không có một kết thúc tại thứ ba vào buổi trưa. Điều đó hoàn toàn tốt. Chúng tôi sẽ có những giờ văn phòng tối nay cũng như đêm thứ hai. Và tất cả các mục trong tuần này sẽ thực sự được biến thành các cuộc hội thảo, vì vậy cảm thấy tự do để bật trong bất kỳ phần bạn muốn, và họ sẽ có loại mini-pset hội thảo để được giúp đỡ về điều đó. Vì vậy, như vậy, đây là phần duy nhất nơi chúng tôi đang giảng dạy vật chất. Tất cả các phần khác sẽ được tập trung hoàn toàn vào sự giúp đỡ cho các pset. Yeah? 

Đung đâu là giờ làm việc? 

Andi PENG: Thời gian làm việc tonight-- oh, câu hỏi hay. Tôi nghĩ giờ hành chính tối nay là trong Teal hoặc tại Commons. Nếu bạn kiểm tra trực tuyến CS50 và bạn đi đến giờ làm việc, không nên có một lịch trình cho bạn nơi mà tất cả chúng đều. 

Tôi biết một trong hai đêm nay hoặc ngày mai là teal, và tôi nghĩ rằng chúng tôi có thể có commons cho đêm khác. Tôi không chắc. Câu hỏi hay. Kiểm tra trên CS50. 

Cool, bất kỳ câu hỏi liên quan đến việc Lịch trình tiếp theo như ba ngày? Tôi hứa với các bạn như David cho biết, đây là đỉnh đồi. Các bạn đang ở gần đó. Hơn chỉ trong ba ngày. Đạt được điều đó, và sau đó chúng tôi sẽ tất cả đi xuống. Chúng tôi sẽ có một kì nghỉ CS-free tốt đẹp. Chào mừng trở lại. Chúng tôi sẽ nhảy vào web lập trình và phát triển, điều đó rất thú vị so với một số các psets khác. Và nó sẽ được lạnh, và chúng ta sẽ có rất nhiều niềm vui. Chúng tôi sẽ có thêm kẹo. Xin lỗi cho kẹo. Tôi quên kẹo. Đó là một buổi sáng thô. Vì vậy, các bạn đang ở gần đó, và tôi thực sự tự hào về các bạn. 

OK, vì vậy ngăn xếp. Ai yêu các câu hỏi về Jack và quần áo của mình vào các bài kiểm tra? Không một ai? Được rồi, ổn mà. 

Vì vậy, về cơ bản như bạn có thể hình ảnh Jack, anh chàng này ở đây, yêu thương để lấy quần áo ra khỏi đỉnh của ngăn xếp, và ông đặt nó trở lại vào stack sau khi anh ta thực hiện. Vì vậy, bằng cách này, ông không bao giờ dường như nhận được để dưới cùng của ngăn xếp trong quần áo của mình. Vì vậy, đây loại mô tả cấu trúc dữ liệu cơ bản làm thế nào một chồng được thực hiện. 

Về cơ bản, suy nghĩ của một ngăn xếp như bất kỳ ngăn xếp của các đối tượng nơi bạn đặt mọi thứ lên đầu trang, và sau đó bạn bật chúng ra khỏi đầu. Vì vậy, LIFO là từ viết tắt của chúng tôi thích để use-- cuối In, First Out. Và như vậy kéo dài vào đầu ngăn xếp là một trong những đầu tiên mà đi ra. Và do đó, hai thuật ngữ chúng tôi muốn liên kết với điều đó được gọi là push và pop. Khi bạn đẩy một cái gì đó lên ngăn xếp, và bạn bật nó trở lại. 

Và vì vậy tôi đoán đây là loại một khái niệm trừu tượng cho những người bạn ai muốn xem như một thực hiện thực tế của điều này trong thế giới thực. Làm thế nào nhiều bạn đã viết một bài luận có lẽ như một giờ trước khi nó là do, và bạn vô tình xóa một lớn đoạn của nó, giống như vô tình? Và sau đó những gì kiểm soát làm chúng tôi sử dụng để đưa nó trở lại? Control-Z, yeah? Control-Z, vì vậy số lượng lần rằng Control-Z đã cứu cuộc đời tôi, đã lưu ass của tôi, mỗi lần đó là thực hiện thông qua một chồng. 

Về cơ bản tất cả các thông tin đó là trên tài liệu Word của bạn, nó được đẩy và bật theo ý muốn. Và do đó, về cơ bản bất cứ khi nào bạn xóa bất cứ điều gì, bạn bật nó trở lại. Và sau đó nếu bạn cần nó trở lại, bạn đẩy nó, đó là những gì Control-C không. Và chức năng trên thế giới rất thật cấu trúc dữ liệu như thế nào đơn giản có thể giúp cuộc sống hàng ngày của bạn. 

Vì vậy, một struct là cách mà chúng tôi thực sự tạo ra một chồng. Chúng tôi gõ xác định cấu trúc, và sau đó chúng ta gọi nó là ngăn xếp ở phía dưới. Và trong ngăn xếp, chúng tôi có hai thông số rằng chúng ta có thể thao tác cơ bản, vì vậy chúng tôi có char chuỗi sao năng lực. 

Tất cả những gì nó đang làm đang tạo ra một mảng rằng chúng ta có thể lưu trữ bất cứ điều gì bạn muốn mà chúng ta có thể xác định khả năng của mình. Công suất là chỉ số tiền tối đa của mặt hàng chúng tôi có thể đưa vào mảng này. int size kích thước là quầy mà giữ theo dõi bao nhiêu mặt hàng hiện đang là trong ngăn xếp. Vì vậy, sau đó chúng ta có thể theo dõi, A, cả lớn như thế nào stack thực tế là, và, B, bao nhiêu đó ngăn xếp chúng tôi đầy bởi vì chúng tôi không muốn tràn trên những năng lực của chúng tôi là. 

Vì vậy, ví dụ, điều này đáng yêu Câu hỏi là trên bài kiểm tra của bạn. Về cơ bản cách làm chúng ta đẩy vào đầu của một chồng. Khá đơn giản. Nếu bạn nhìn vào nó, chúng ta sẽ đi qua này. Nếu [Không nghe thấy] size-- nhớ, bất cứ khi nào bạn muốn truy cập vào bất kỳ Tham số trong một cấu trúc, bạn làm tên của struct.parameter. 

Trong trường hợp này, s là tên của ngăn xếp của chúng tôi. Chúng tôi muốn truy cập vào kích thước của nó, vì vậy chúng tôi làm s.size. Vì vậy, miễn là kích thước không phải là bằng công suất hoặc kéo dài vì nó là ít hơn so với năng lực, hoặc là sẽ làm việc ở đây. 

Bạn muốn truy cập vào bên trong của ngăn xếp của bạn, vì vậy s.strings, và bạn đang đi để đưa con số mới mà bạn muốn chèn vào đó. Hãy chỉ nói rằng chúng ta sẽ muốn chèn int n vào ngăn xếp, chúng ta có thể làm s.strings, ngoặc, s.size bằng n. Bởi vì kích thước là nơi chúng tôi Hiện tại trong ngăn xếp nếu chúng ta để đẩy nó trên, chúng ta chỉ cần truy cập bất cứ nơi nào kích thước là, viên mãn hiện tại của chồng, và chúng tôi đẩy int n vào nó. Và sau đó, chúng tôi muốn chắc chắn rằng chúng tôi cũng cách tăng kích thước của n, vì vậy chúng tôi có thể theo dõi của chúng tôi đã thêm một điều thêm vào stack. Bây giờ chúng ta có một kích thước lớn hơn. Liệu điều này ở đây có ý nghĩa để tất cả mọi người, làm thế nào nó hoạt động một cách hợp lý? Đó là một loại nhanh chóng. Đung bạn có thể đi qua các s.stringss.strings [s.size] một lần nữa? Andi PENG: Chắc chắn rồi, vì vậy những gì hiện s.size hiện đang cung cấp cho chúng ta? Đung Đó là kích thước hiện tại. Andi PENG: Chính xác, do đó, chỉ số hiện tại mà kích thước của chúng tôi là, và vì vậy chúng tôi muốn đưa các số nguyên mới rằng chúng ta muốn chèn vào s.size. Điều đó có ý nghĩa? Bởi vì s.strings, tất cả những gì là là tên của mảng. Tất cả đó là là truy cập mảng trong cấu trúc của chúng tôi, và do đó, nếu chúng ta muốn đặt n vào chỉ số đó, chúng ta chỉ có thể truy cập nó sử dụng dấu ngoặc s.size. Mát. 

Tất cả các quyền, pop, tôi giả nó ra cho bạn, nhưng khái niệm tương tự. Điều đó có ý nghĩa? Nếu kích thước lớn hơn số không, sau đó bạn biết rằng bạn muốn để có cái gì ra vì nếu kích thước không phải là lớn hơn số không, sau đó bạn không có gì trong ngăn xếp. 

Vì vậy, bạn chỉ muốn thực hiện mã này, nó chỉ có thể bật nếu có cái gì đó để bật. Vì vậy, nếu kích thước lớn hơn 0, chúng ta trừ đi kích thước. Chúng tôi giảm các kích thước và sau đó quay trở lại bất cứ điều gì là bên trong của nó, vì bằng cách popping, chúng tôi muốn truy cập bất cứ điều gì được lưu trữ trong chỉ mục của các đỉnh của ngăn xếp. Tất cả mọi thứ có ý nghĩa? Nếu tôi làm bạn kẻ viết này ra, các bạn sẽ có thể viết nó ra? OK, các bạn có thể chơi xung quanh với nó. Không phải lo lắng nếu bạn không nhận được nó. Chúng tôi không có thời gian để mã nó ra ngày hôm nay bởi vì chúng tôi đã có rất nhiều các cấu trúc đi qua, nhưng về cơ bản giả, rất, rất tương tự để đẩy. Chỉ cần làm theo dọc theo logic. Hãy chắc chắn rằng bạn đang truy cập tất cả các tính năng của cấu trúc của bạn một cách chính xác. Yeah? 

ĐỐI TƯỢNG: liệu những slide và toàn bộ điều này được ký hôm nay-ish? Andi PENG: Luôn luôn, vâng. Tôi sẽ cố gắng đưa này lên như một giờ sau. Tôi sẽ gửi email cho David, David sẽ cố gắng đặt nó lên như một giờ sau này. 

OK, vậy thì chúng ta bước sang khác này cấu trúc dữ liệu đáng yêu gọi là hàng đợi. Như các bạn có thể thấy ở đây, một hàng đợi, đối với người Anh trong số chúng tôi, tất cả đó là là một dòng. Vì vậy, trái với những gì bạn nghĩ rằng một chồng là, một hàng đợi là chính xác những gì logic bạn nghĩ rằng đó là. Nó được tổ chức bởi các quy tắc của FIFO, đó là First In, First Out. Nếu bạn là người đầu tiên một trong các dòng, bạn một trong những đầu tiên đi ra khỏi dòng. 

Vì vậy, những gì chúng tôi muốn kêu gọi này được dequeueing và enqueueing. Nếu chúng ta muốn thêm một cái gì đó vào hàng đợi của chúng tôi, chúng tôi enqueue. Nếu chúng ta muốn dequeue, hoặc mất đi cái gì đó, chúng ta dequeue. 

Vì vậy, cùng một ý nghĩa mà chúng ta đang loại tạo ra yếu tố kích thước cố định mà chúng ta có thể lưu trữ nhất định thứ, nhưng chúng ta cũng có thể thay đổi nơi chúng tôi đang đặt các thông số bên trong của họ dựa trên những gì loại chức năng chúng tôi muốn. Vì vậy, ngăn xếp, chúng tôi muốn cuối cùng một, N là người ra đầu tiên. Queue là chúng tôi muốn điều đầu tiên để được điều đầu tiên ra. 

Vì vậy, các cấu trúc kiểu xác định, như bạn có thể thấy, đó là một chút khác nhau từ những gì các ngăn xếp được không chỉ bởi vì chúng ta phải giữ theo dõi các nơi kích thước là hiện nay, chúng tôi cũng muốn theo dõi của người đứng đầu cũng như nơi chúng tôi đang có. Vì vậy, tôi nghĩ rằng đó là dễ dàng hơn nếu tôi vẽ này lên. Vì vậy, chúng ta hãy tưởng tượng chúng ta đã có một hàng đợi, vì vậy chúng ta hãy nói người đứng đầu là đúng ở đây. Người đứng đầu của dòng, chúng ta hãy chỉ nói rằng hiện đang có, và chúng tôi muốn chèn một cái gì đó vào trong hàng đợi. Tôi sẽ gọi cho kích thước cơ bản là những điều tương tự như đuôi, cuối hàng đợi của bạn bất cứ nơi nào có. Hãy chỉ nói rằng kích thước là quyền ở đây. 

Vì vậy, làm thế nào một khả thi chèn một cái gì đó vào một hàng đợi? Chỉ số gì làm chúng tôi muốn đặt nơi mà chúng ta muốn chèn vào. Nếu đây là sự khởi đầu của bạn xếp hàng và đây là kết thúc của nó hoặc kích thước của nó, nơi nào chúng ta muốn thêm đối tượng kế tiếp? 

Đung [Không nghe thấy] Andi PENG: Chính xác, bạn muốn thêm nó tùy thuộc vào bạn đã viết nó. Hoặc này là trống hay là trống. Vì vậy, bạn muốn thêm vào thì có lẽ nó ở đây vì nếu kích thước is-- nếu đây là tất cả đầy đủ, bạn muốn để thêm nó phải ở đây, phải không? 

Và đó là, trong khi rất, rất đơn giản, không hoàn toàn luôn luôn đúng bởi vì sự khác biệt chính giữa một hàng đợi và một chồng là hàng đợi có thể thực sự được thao tác do đó những thay đổi đầu tùy thuộc vào nơi bạn muốn đầu cue của bạn để bắt đầu. Và kết quả là, cái đuôi của bạn cũng sẽ thay đổi. Và do đó, có một cái nhìn tại mã này ngay bây giờ. Như các bạn cũng được yêu cầu viết ra trên các bài kiểm tra, enqueue. Có lẽ chúng ta sẽ nói chuyện thông qua tại sao câu trả lời là những gì nó được. 

Tôi có thể không khá phù hợp với dòng này trên một, nhưng về cơ bản đoạn mã này nên được trên một dòng. Chi tiêu như 30 giây. Hãy xem, và xem tại sao đây là cách mà nó được. 

Rất, cấu trúc rất giống nhau, rất, rất cấu trúc tương tự như trước đây chồng ngoại trừ có lẽ một dòng mã. Và đó là một dòng mã xác định các chức năng. Và nó thực sự khác biệt một hàng đợi từ một chồng. 

Bất cứ ai muốn để mất một đâm tại giải thích tại sao bạn đã có điều phức tạp này tại đây? Chúng ta thấy sự trở lại của chúng tôi tuyệt vời modulus bạn. Như các bạn sẽ sớm đi để nhận ra trong lập trình, hầu như bất cứ lúc nào bạn cần một cái gì đó để bọc xung quanh bất cứ điều gì, mô đun sẽ là cách để làm điều đó. Vì vậy, khi biết rằng, không ai muốn để cố gắng giải thích rằng dòng mã? Vâng, tất cả các câu trả lời chấp nhận và hoan nghênh. Đung bạn đang nói chuyện với tôi? Andi PENG: Yeah. Đung Oh, không xin lỗi. Andi PENG: OK, vì vậy chúng ta đi bộ qua đoạn mã này. Vì vậy, khi bạn đang cố gắng để thêm một cái gì đó vào một hàng đợi, trong trường hợp đáng yêu mà người đứng đầu xảy ra là ngay tại đây, nó rất dễ dàng cho chúng tôi chỉ cần đi đến cùng chèn một cái gì đó, phải không? Nhưng điểm chung của một hàng đợi rằng người đứng đầu thực sự có thể tự động thay đổi tùy thuộc vào nơi chúng tôi muốn bắt đầu q của chúng tôi có được, và như vậy, đuôi cũng sẽ thay đổi. 

Và như vậy tưởng tượng rằng đây không phải là xếp hàng, nhưng thay vì đây là hàng đợi. Hãy nói rằng người đứng đầu là đúng ở đây. Hãy nói rằng hàng đợi của chúng tôi trông như thế này. Nếu chúng ta muốn thay đổi nơi đầu dòng là, hãy nói chúng tôi chuyển đầu cách này và kích cỡ tại đây. 

Bây giờ chúng ta muốn thêm một cái gì đó để hàng đợi này, nhưng như các bạn có thể thấy, nó không phải đơn giản như vậy để chỉ thêm bất cứ điều gì là sau khi kích thước bởi vì sau đó chúng tôi chạy ra khỏi giới hạn của mảng thực tế của chúng tôi. Nơi mà chúng tôi muốn thực sự thêm là ở đây. Đó là vẻ đẹp của một hàng đợi là để chúng ta, nó trực quan trông giống như các dòng đi như thế này, nhưng khi được lưu trữ trong một cấu trúc dữ liệu, họ cung cấp cho nó như là giống như một chu kỳ. Nó loại kết thúc tốt đẹp xung quanh vào phía trước cùng một cách rằng một dòng cũng có thể bọc xung quanh phụ thuộc vào bất cứ nơi nào bạn muốn đầu dòng được. Và như vậy nếu chúng ta hãy nhìn xuống ở đây, chúng ta hãy nói chúng tôi muốn tạo ra một chức năng gọi là enqueue. Chúng tôi muốn thêm int n vào q đó. Nếu q.size q-- chúng ta sẽ gọi là dữ liệu của chúng tôi structure-- nếu queue.size chúng tôi không bằng công suất hoặc nếu nó ít hơn so với năng lực, q.strings là mảng trong q của chúng tôi. Chúng ta sẽ thiết mà bằng q.heads, mà là ngay đây, cộng với q.size modulus bởi năng lực, mà bọc chúng lại quanh đây. 

Vì vậy, trong ví dụ này, chỉ số đầu là 1, phải không? Các chỉ số của kích thước là 0, 1, 2, 3, 4. Vì vậy, chúng ta có thể làm 1 cộng với 4 mô đun bởi khả năng của chúng tôi mà là 5. Những gì mà không cho chúng ta? Chỉ số là gì mà đi ra khỏi đây? 

Đung 0. 

Andi PENG: 0, sẽ xảy ra là ngay tại đây, và vì vậy chúng tôi muốn có thể để chèn vào ngay đây. Và do đó, phương trình này ở đây loại chỉ hoạt động với bất kỳ số điện tùy thuộc vào nơi bạn đầu và kích thước của bạn. Nếu bạn biết những gì các điều là, bạn biết chính xác nơi bạn muốn chèn bất cứ điều gì là sau khi hàng đợi của bạn. Điều đó có ý nghĩa với tất cả mọi người? 

Tôi biết loại của một bộ não trêu ghẹo đặc biệt là kể từ nay đến hậu quả của bài kiểm tra của bạn. Nhưng hy vọng rằng tất cả mọi người bây giờ có thể hiểu được tại sao giải pháp này hay này chức năng là cách mà nó được. Bất cứ ai một chút không rõ ràng về điều đó? ĐƯỢC. 

Và vì vậy bây giờ, nếu bạn muốn dequeue, điều này là nơi đầu của chúng tôi sẽ được chuyển bởi vì nếu chúng ta dequeue, chúng tôi không đưa ra khỏi cuối của q. Chúng tôi muốn đi ra khỏi đầu, phải không? Vì vậy, kết quả là, người đứng đầu là sẽ thay đổi, và đó là lý do tại sao khi bạn enqueue, bạn đã có để theo dõi nơi đầu của bạn và kích thước của bạn là để có thể chèn vào đúng vị trí. 

Và như vậy khi bạn dequeue, Tôi cũng giả nó ra. Cảm thấy tự do để nếu bạn muốn để cố gắng mã hóa này ra. Bạn muốn di chuyển đầu, phải không? Nếu tôi muốn dequeue, tôi sẽ di chuyển đầu hơn. Điều này sẽ là người đứng đầu. 

Và kích thước hiện tại của chúng tôi sẽ trừ bởi vì chúng tôi không còn có bốn yếu tố trong mảng. Chúng tôi chỉ có ba, và sau đó chúng tôi muốn để trả lại bất cứ đã được lưu trữ bên trong của người đứng đầu bởi vì chúng tôi muốn đi này giá trị ra như vậy rất giống với stack. Chỉ cần bạn đang dùng từ một nơi khác, và bạn phải phân công lại con trỏ của bạn đến nơi khác như một kết quả. Một cách hợp lý, tất cả mọi người làm theo? Thật tuyệt. 

OK, vì vậy chúng ta sẽ nói một chút sâu hơn về danh sách liên kết vì họ sẽ được rất, rất có giá trị cho bạn trong quá trình tuần này của psets. Danh sách liên kết, như các bạn có thể nhớ, tất cả họ là là các nút đó là nút của một số giá trị của cả một giá trị và một con trỏ được liên kết với nhau bởi những con trỏ. Và do đó, các cấu trúc trên như thế nào chúng ta tạo ra một nút ở đây là chúng ta có int n, mà là bất cứ điều gì các giá trị trong một cửa hàng hoặc chuỗi n hoặc bất cứ điều gì bạn muốn gọi nó, char sao n. Struct sao nút, mà là con trỏ mà bạn muốn có trong mỗi nút, bạn đang đi để có mà điểm con trỏ về phía sau. Bạn sẽ có người đứng đầu của một danh sách liên kết đó sẽ trỏ đến các phần còn lại của các giá trị vv và vv cho đến khi bạn cuối cùng đã đạt được kết thúc. Và nút cuối cùng này chỉ là sẽ không có một con trỏ. Nó sẽ trỏ đến null, và đó là khi Bạn có biết bạn đã nhấn cuối danh sách liên kết của bạn là khi con trỏ cuối cùng của bạn không trỏ đến bất cứ điều gì. 

Vì vậy, chúng ta sẽ đi một chút trong chiều sâu về cách người ta sẽ có thể tìm kiếm một danh sách liên kết. Ghi một số là gì nhược điểm của danh sách liên kết các câu một mảng liên quan đến tìm kiếm. Một mảng, bạn có thể tìm kiếm nhị phân, nhưng tại sao bạn không thể làm điều đó trong một danh sách liên kết? 

Đung Bởi vì tất cả chúng đều được kết nối, nhưng bạn không biết chắc đâu [Không nghe thấy]. 

Andi PENG: Yeah, chính xác như vậy nhớ rằng sự sáng chói của một mảng đã được thực tế rằng chúng tôi đã có bộ nhớ truy cập ngẫu nhiên mà nếu tôi muốn các giá trị từ chỉ số sáu, tôi chỉ có thể nói chỉ số sáu, cho tôi giá trị đó. Và đó là bởi vì các mảng đều được sắp xếp trong một không gian tiếp giáp của bộ nhớ ở một nơi, trong khi loại danh sách liên kết là xen kẽ ngẫu nhiên tất cả xung quanh, và cách duy nhất bạn có thể tìm thấy một là thông qua một con trỏ mà nói với bạn địa chỉ nơi mà nút tiếp theo là. 

Và do đó, kết quả là, cách duy nhất để tìm kiếm thông qua một danh sách liên kết là tìm kiếm tuyến tính. Bởi vì tôi không biết chính xác nơi giá trị thứ 12 trong danh sách liên kết là, Tôi phải đi qua toàn bộ trong đó một danh sách liên kết bởi một từ đầu đến nút đầu tiên, đến nút thứ hai, đến nút thứ ba, tất cả các con đường xuống cho đến khi cuối cùng tôi nhận được đến nơi mà nút Tôi đang tìm được. Và như vậy trong ý nghĩa này, tìm kiếm vào một danh sách liên kết luôn luôn là n. Nó luôn luôn n. Nó luôn luôn trong thời gian tuyến tính. 

Và do đó, các mã trong đó chúng tôi thực hiện điều này, và điều này là một chút mới cho các bạn kể từ khi bạn kẻ đã không thực sự nói về hoặc bao giờ con trỏ thấy trong cách tìm kiếm thông qua con trỏ, vì vậy chúng tôi sẽ đi bộ qua này rất, rất chậm. Vì vậy, tìm kiếm bool, phải, hãy tưởng tượng chúng ta muốn để tạo ra một chức năng gọi là tìm kiếm trả về true nếu bạn tìm thấy một giá trị bên trong liên kết danh sách, và nó trả về false. Danh sách sao Node là hiện nay chỉ con trỏ đến mục đầu tiên trong danh sách liên kết của bạn. int n là giá trị mà bạn tìm kiếm trong danh sách đó. 

Vì vậy, con trỏ sao nút bằng danh sách. Điều đó có nghĩa là chúng tôi đang thiết và tạo ra một con trỏ gửi đến nút đầu tiên bên trong danh sách. Tất cả mọi người với tôi? Vì vậy, nếu chúng ta đi trở lại đây, tôi sẽ có khởi tạo một con trỏ trỏ tới người đứng đầu danh sách đó là bất cứ điều gì. 

Và sau đó một khi bạn nhận được xuống đây, trong khi con trỏ không làm rỗng bằng nhau, vì vậy đó là các vòng lặp trong đó chúng tôi sẽ là sau đó đi qua phần còn lại của danh sách của chúng tôi vì những gì xảy ra khi con trỏ bằng null? Chúng tôi biết rằng chúng tôi have-- 

Đung [Không nghe thấy] 

Andi PENG: Chính xác, vì vậy chúng tôi biết rằng chúng tôi đã đạt đến cuối danh sách, phải không? Nếu bạn quay trở lại đây, mỗi nút nên được trỏ đến một nút khác vv và vv cho đến khi bạn nhấn cuối cùng đuôi của danh sách liên kết của bạn, trong đó có một con trỏ chỉ không trỏ bất cứ nơi nào khác hơn là không có. Và do đó, về cơ bản bạn biết rằng danh sách của bạn vẫn còn đó lên cho đến khi con trỏ không bằng null bởi vì một khi nó bằng null, Bạn có biết rằng không có nhiều thứ hơn. 

Vì vậy, đó là các vòng lặp, trong đó chúng tôi sẽ phải tìm kiếm thực tế. Và nếu pointer-- làm bạn thấy là loại mũi tên chức năng đó? Vì vậy, nếu con trỏ trỏ đến n, nếu con trỏ chuột tại n bằng bằng n, do đó có nghĩa rằng nếu các con trỏ mà bạn tìm kiếm trên phần cuối của mỗi nút là thực sự bằng giá trị bạn đang tìm kiếm, sau đó bạn muốn trở thành sự thật. Vì vậy, về cơ bản, nếu bạn đang ở một nút đó có giá trị mà bạn đang tìm kiếm, bạn biết rằng bạn đã có thể tìm kiếm thành công. 

Nếu không, bạn muốn thiết lập con trỏ của bạn đến nút tiếp theo. Đó là những gì mà dòng ở đây là làm. Pointer bằng con trỏ tới. Mọi người thấy thế nào mà làm việc? 

Và về cơ bản bạn đang đi để chỉ đi qua toàn bộ danh sách, đặt con trỏ của bạn mỗi lần cho đến khi Cuối cùng bạn nhấn vào cuối danh sách. Và bạn biết rằng không có các nút hơn để tìm kiếm thông qua, và sau đó bạn có thể quay trở lại sai bởi vì bạn biết rằng, oh, tốt, nếu tôi đã có thể tìm kiếm thông qua toàn bộ danh sách. Nếu trong ví dụ này, nếu tôi muốn để tìm kiếm các giá trị là 10, và tôi bắt đầu từ đầu, và Tôi tìm kiếm tất cả các con đường xuống, và cuối cùng tôi đã đến đây, mà một con trỏ trỏ đến null, Tôi biết rằng, crap, tôi đoán 10 không có trong danh sách này bởi vì tôi không thể tìm thấy nó. Và tôi đang ở cuối danh sách. Và trong trường hợp bạn biết Tôi sẽ trả về false. 

Hãy để đó ngâm trong một chút. Đây sẽ là khá quan trọng cho pset của bạn. Logic của nó rất đơn giản, có lẽ cú pháp chỉ thực hiện nó. Các bạn muốn làm chắc chắn rằng bạn hiểu. Mát. 

OK, vậy làm thế nào chúng tôi sẽ là chèn các nút, phải, vào một danh sách vì nhớ những gì là những gì trong những lợi ích của việc có một danh sách liên kết so với một mảng về lưu trữ? 

Đung Đó là năng động, vì vậy nó dễ dàng hơn đối với: 

Andi PENG: Chính xác, do đó, nó là năng động, có nghĩa là nó có thể mở rộng và thu nhỏ tùy thuộc vào nhu cầu của người dùng. Và như vậy, trong ý nghĩa này, chúng ta không cần để lãng phí bộ nhớ không cần thiết bởi vì tôi nếu tôi không biết có bao nhiêu giá trị tôi muốn để lưu trữ, nó không có ý nghĩa đối với tôi để tạo ra một mảng vì nếu tôi muốn để lưu trữ 10 giá trị và tôi tạo ra một mảng của 1000, đó là rất nhiều bộ nhớ bị lãng phí, quy định. Đó là lý do tại sao chúng tôi muốn sử dụng một liên kết danh sách để có thể tự động thay đổi hoặc thu nhỏ kích thước của chúng tôi. 

Và vì vậy mà làm chèn một chút phức tạp hơn. Kể từ khi chúng tôi không thể truy cập ngẫu nhiên các yếu tố cách mà chúng tôi sẽ của một mảng. Nếu tôi muốn chèn một phần tử vào các chỉ số thứ bảy, Tôi chỉ có thể chèn nó vào các chỉ số thứ bảy. Trên một danh sách liên kết, nó không khá làm việc như là một cách dễ dàng, và do đó, nếu chúng ta muốn chèn cái ở đây, trong danh sách liên kết, trực quan, nó rất dễ dàng để xem. Chúng tôi chỉ muốn chèn nó ở ngay đó, ngay từ đầu của danh sách, ngay sau khi người đứng đầu. 

Nhưng cách thức mà chúng ta phải phân công lại các con trỏ là một chút phức tạp hay, hợp lý, nó có ý nghĩa, nhưng bạn muốn chắc chắn rằng bạn có nó hoàn toàn xuống vì điều cuối cùng bạn muốn là để gán một con trỏ cách mà chúng tôi đang làm ở đây. Nếu bạn tới đích của các con trỏ từ đầu đến 1, sau đó tất cả của một đột ngột phần còn lại của danh sách liên kết của bạn bị mất bởi vì bạn đã không thực sự tạo ra một điều gì tạm thời. Đó là chỉ vào 2. Nếu bạn gán lại con trỏ, sau đó các phần còn lại của danh sách của bạn là hoàn toàn bị mất. Vì vậy, bạn muốn được rất, rất cẩn thận ở đây đầu tiên gán con trỏ từ bất cứ điều gì bạn muốn chèn vào bất cứ nơi nào bạn muốn, và sau đó bạn có thể tới đích của phần còn lại của danh sách của bạn. 

Vì vậy, điều này áp dụng cho bất cứ nơi nào bạn đang cố gắng để chèn vào. Nếu bạn muốn chèn vào đầu, nếu bạn muốn trả lời ở đây, nếu bạn muốn chèn vào Cuối cùng, cũng, kết thúc tôi đoán bạn sẽ chỉ không có con trỏ, nhưng bạn muốn chắc chắn rằng bạn làm không mất phần còn lại của danh sách của bạn. Bạn luôn muốn chắc chắn nút mới của bạn được trỏ hướng tới bất cứ điều gì bạn muốn chèn vào, và sau đó bạn có thể thêm các chuỗi trên. Mọi người đều rõ ràng? 

Điều này là có được một trong những vấn đề thực tế. Một trong những vấn đề lớn nhất bạn sẽ có trên pset của bạn là bạn sẽ cố gắng để tạo ra một danh sách liên kết và những thứ chèn nhưng sau đó chỉ mất phần còn lại của danh sách liên kết của bạn. Và bạn sẽ được như thế, tôi không biết tại sao điều này xảy ra? Và đó là một nỗi đau để đi qua và tìm kiếm tất cả các con trỏ của bạn. 

Và tôi đảm bảo với bạn về pset này, viết và vẽ các nút này ra sẽ rất, rất hữu ích. Vì vậy, bạn hoàn toàn có thể theo dõi của nơi mà tất cả các con trỏ của bạn, những gì đang xảy ra sai, nơi mà tất cả các nút của bạn đang có, những gì bạn cần làm để truy cập hay chèn hoặc xóa hoặc bất kỳ của họ. Mọi người đều tốt với điều đó? Mát. 

Vì vậy, nếu chúng ta muốn nhìn vào mã? Oh, tôi không biết nếu chúng tôi có thể thấy the-- OK, vì vậy ở đầu tất cả đó là là một chức năng tên chèn nơi chúng tôi muốn để chèn int n vào danh sách liên kết. Chúng ta sẽ đi qua này. Đó là một rất nhiều mã, rất nhiều cú pháp mới. Chúng tôi sẽ OK. 

Vì vậy, ở đầu, bất cứ khi nào chúng tôi muốn tạo ra bất cứ điều gì những gì chúng ta cần phải làm, đặc biệt là nếu bạn muốn nó không được lưu trữ trên stack nhưng trong đống? Chúng tôi đi đến một malloc, phải không? Vì vậy, chúng ta sẽ tạo ra một con trỏ. Node, con trỏ, bình đẳng mới malloc kích thước của một nút bởi vì chúng tôi muốn nút đó được tạo ra. Chúng tôi muốn lượng nhớ rằng một nút chiếm được phân bổ cho các tạo ra các nút mới. 

Và sau đó chúng ta sẽ kiểm tra xem equals mới bằng null. Hãy nhớ những gì chúng tôi đã nói? Dù bạn malloc, những gì bạn luôn phải làm gì? Bạn luôn luôn phải kiểm tra xem có hay không mà là null. 

Ví dụ, nếu điều hành của bạn hệ thống là hoàn toàn đầy đủ, nếu bạn có trí nhớ không có nhiều ở tất cả và bạn cố gắng để malloc, nó sẽ trả về null cho bạn. Và do đó, nếu bạn cố gắng sử dụng nó khi nó đã được trỏ đến null, bạn sẽ không thể truy cập thông tin. Và như vậy, như vậy, chúng tôi muốn làm chắc chắn rằng bất cứ khi nào bạn đang mallocing, bạn luôn kiểm tra để xem nếu rằng bộ nhớ dành cho bạn là null. Và nếu nó không phải, sau đó chúng ta có thể di chuyển trên với phần còn lại của mã của chúng tôi. 

Vì vậy, chúng ta sẽ khởi tạo các nút mới. Chúng tôi đang đi làm n mới bằng n. Và sau đó, chúng tôi đang đi làm thiết lập mới các con trỏ trên mới để null vì ngay bây giờ chúng ta làm không muốn bất cứ điều gì cho nó để trỏ đến. Chúng tôi không có ý tưởng nó sẽ đưa bạn, và sau đó nếu chúng ta muốn chèn nó ở phần đầu, sau đó chúng ta có thể gán con trỏ vào đầu. Có phải mọi người làm theo logic nơi đang diễn ra? 

Tất cả chúng ta đang làm là tạo ra một mới nút, đặt con trỏ đến null, và sau đó giao lại nó cho người đứng đầu nếu chúng ta biết chúng ta muốn chèn nó ở phần đầu. Và sau đó người đứng đầu là có chỉ hướng tới rằng nút mới. Mọi người đều OK với điều đó? 

Vì vậy, nó là một quá trình hai bước. Bạn đã có để gán đầu tiên bất cứ điều gì bạn đang tạo. Đặt rằng con trỏ đến tham khảo, và sau đó bạn có thể loại dereference con trỏ đầu tiên và trỏ về phía nút mới. Bất cứ nơi nào bạn muốn chèn nó, logic rằng sẽ giữ đúng. 

Nó giống như là gán các biến tạm thời. Hãy nhớ rằng, bạn đã có để đảm bảo rằng bạn không mất theo dõi nếu bạn đang trao đổi. Bạn muốn chắc chắn rằng bạn có một biến tạm thời là loại giữ theo dõi các nơi điều mà được lưu trữ để bạn không bị mất bất kỳ giá trị trong khóa học giống như rối tung xung quanh với nó. 

OK, do đó, mã sẽ được ở đây. Các bạn hãy xem phần sau. Nó sẽ ở đó. 

Vì vậy, tôi đoán như thế nào này khác nếu chúng ta muốn để chèn vào giữa hoặc cuối cùng? Có ai có một ý tưởng về những gì là giả như là tài liệu tham khảo logic rằng chúng ta sẽ có được nếu chúng ta muốn để chèn nó vào giữa? Vì vậy, nếu chúng ta muốn chèn nó ở đầu, tất cả chúng tôi làm là tạo ra một nút mới. Chúng tôi đặt con trỏ đó nút mới vào bất cứ điều gì vào đầu, và sau đó chúng tôi đặt đầu đến nút mới, phải không? Nếu chúng ta muốn chèn nó ở giữa của danh sách, những gì chúng ta sẽ phải làm gì? 

Đung Nó vẫn sẽ là một quá trình tương tự giống như gán con trỏ và sau đó gán con trỏ đó, nhưng chúng ta sẽ phải xác định vị trí đó. 

Andi PENG: Chính xác, vì vậy chính xác quá trình tương tự, ngoại trừ bạn phải xác định vị trí chính xác nơi bạn muốn rằng con trỏ mới đi vào, vì vậy nếu tôi muốn chèn vào giữa liên kết list-- OK, hãy nói rằng đó là danh sách liên kết của chúng tôi. Nếu chúng ta muốn chèn nó phải ở đây, chúng ta sẽ tạo ra một nút mới. Chúng tôi đang đi để malloc. Chúng ta sẽ tạo ra một nút mới. Chúng tôi sẽ giao con trỏ của nút này ở đây. 

Nhưng vấn đề đó khác từ nơi mà người đứng đầu là là chúng ta biết chính xác nơi người đứng đầu là. Đó là ngay ở lần đầu tiên, phải không? Nhưng ở đây chúng ta phải theo dõi của nơi mà chúng ta đang chèn nó vào. Nếu chúng ta đang chèn chúng tôi nút ở đây, chúng tôi đã có để đảm bảo rằng các trước đó đến nút này là một trong đó reassigns con trỏ. Vì vậy, sau đó bạn phải loại theo dõi trong hai điều. Nếu bạn theo dõi các nơi này nút hiện được chèn vào. Bạn cũng cần phải theo dõi các nơi nút trước đó mà bạn đang tìm kiếm cũng đã có. Mọi người đều tốt với điều đó? ĐƯỢC. 

Làm thế nào về cách chèn vào cuối? Nếu tôi muốn thêm nó here-- nếu tôi muốn để thêm một nút mới vào cuối danh sách, làm thế nào tôi có thể đi về làm việc đó? Đung Vì vậy, hiện nay, người cuối cùng đã chỉ để null. Andi PENG: Yeah. Chính xác, vì vậy một trong này hiện là chỉ để biết, và vì vậy tôi đoán, trong ý nghĩa này, nó rất dễ dàng để thêm vào cuối danh sách. Tất cả bạn phải làm là cài đặt nó bằng null và sau đó bùng nổ. Ngay ở đó, rất dễ dàng. Rất đơn giản. 

Rất giống với đầu, nhưng logic bạn muốn chắc chắn rằng các bước bạn đưa về phía làm bất cứ điều này, bạn đang theo cùng. Nó rất dễ dàng để, ở giữa code của bạn, nhận được đánh bắt lên trên, oh, tôi đã có rất nhiều con trỏ. Tôi không biết nơi bất cứ điều gì được trỏ đến. Tôi thậm chí còn không biết mà nút tôi đang trên. Điều gì đang xảy ra? 

Hãy thư giãn, bình tĩnh lại, hít một hơi thật sâu. Vẽ ra danh sách liên kết của bạn. Nếu bạn nói, tôi biết chính xác nơi Tôi cần phải chèn này vào và tôi biết chính xác làm thế nào để phân công lại của tôi con trỏ, nhiều, dễ dàng hơn nhiều để ảnh out-- nhiều, dễ dàng hơn nhiều để không bị lạc trong các lỗi của mã của bạn. Mọi người đều OK với điều đó? ĐƯỢC. 

Vì vậy, tôi đoán là một khái niệm mà chúng ta có không thực sự đã nói trước bây giờ, và tôi đoán bạn có thể sẽ không gặp phải nhiều yet-- đó là loại một concept-- tiên tiến là chúng ta thực sự có một dữ liệu cấu trúc được gọi là một danh sách gấp đôi được liên kết. Vì vậy, các bạn có thể thấy, tất cả chúng ta đang làm là tạo một giá trị thực tế, một phụ con trỏ trên mỗi nút của chúng tôi mà cũng chỉ đến nút trước đó. Vì vậy, chúng ta không chỉ có chúng tôi nút điểm đến kế tiếp. Họ cũng chỉ ra trước đó. Tôi sẽ bỏ qua hai ngay bây giờ. 

Vì vậy, sau đó bạn có một chuỗi có thể di chuyển cả hai cách, và sau đó nó là một chút dễ dàng hơn để hợp lý theo cùng. Giống như ở đây, thay vì việc theo dõi, oh, tôi phải biết rằng nút này là một trong đó tôi phải phân công lại, Tôi chỉ có thể đến đây và chỉ cần kéo trước. Sau đó, tôi biết chính xác nơi đó là, và sau đó bạn không phải đi qua toàn bộ các danh sách liên kết. Đó là một chút dễ dàng hơn. 

Nhưng như vậy, bạn có gấp đôi số lượng con trỏ, đó là gấp đôi số lượng của bộ nhớ. Đó là rất nhiều của các con trỏ để theo dõi. Nó phức tạp hơn một chút, nhưng nó hơn một chút thân thiện với người sử dụng tùy vào những gì bạn đang cố gắng để thực hiện. 

Vì vậy, loại dữ liệu cấu trúc hoàn toàn tồn tại, và cấu trúc cho là rất, rất đơn giản, ngoại trừ tất cả các bạn đang gặp là, thay vì chỉ là một con trỏ đến tiếp theo, bạn cũng có một con trỏ đến trước. Đó là tất cả sự khác biệt. Mọi người đều tốt với điều đó? Mát. 

Được rồi, vậy bây giờ tôi để thực sự dành lẽ như 15-20 phút hoặc số lượng lớn của phần còn lại của thời gian trong phần nói về bảng băm. Bao nhiêu người trong các bạn đã đọc pset5 spec? Được rồi, tốt. Đó là cao hơn so với 50% của bình thường. Đó là OK. 

Vì vậy, các bạn sẽ thấy, bạn đang thách thức trong pset5 sẽ được thực hiện một từ điển nơi bạn nạp trên 140.000 lời mà chúng tôi cung cấp cho bạn và kiểm tra chính tả nó chống lại tất cả các văn bản. Chúng tôi sẽ cung cấp cho bạn ngẫu nhiên mảnh của văn học. Chúng tôi sẽ cung cấp cho bạn The Odyssey. Chúng tôi sẽ cung cấp cho bạn The Iliad. Chúng tôi sẽ cung cấp cho bạn Austin Powers. 

Và thách thức của bạn sẽ được kiểm tra chính tả mỗi từ duy nhất trong tất cả các của những từ điển về cơ bản với kiểm tra chính tả của chúng tôi. Và do đó, có một vài bộ phận tạo pset này, đầu tiên bạn muốn được có thể thực sự tải tất cả các từ vào của bạn từ điển, và sau đó bạn muốn để có thể kiểm tra chính tả tất cả chúng. Và như vậy, như vậy, bạn sẽ cần một cấu trúc dữ liệu có thể làm điều này nhanh và có hiệu quả và năng động. 

Vì vậy, tôi cho rằng đơn giản nhất cách để làm điều này, bạn có lẽ sẽ tạo ra một mảng, phải không? Cách đơn giản nhất là bạn lưu trữ có thể tạo ra một mảng của 140.000 lời và chỉ cần đặt tất cả chúng ở đó và sau đó đi qua chúng bằng cách tìm kiếm nhị phân hoặc bằng cách chọn hoặc not-- xin lỗi đó là phân loại. Bạn có thể sắp xếp chúng và sau đó đi qua chúng bằng cách tìm kiếm nhị phân hoặc tìm kiếm chỉ tuyến tính và chỉ thức lời nói, nhưng điều đó mất một số tiền rất lớn của bộ nhớ, và nó không phải là rất hiệu quả. 

Và vì vậy chúng tôi đang đi để bắt đầu nói về cách làm Hiện chúng tôi đang chạy hiệu quả hơn. Và mục tiêu của chúng tôi là để có được hằng số thời gian nơi nó gần như mảng, nơi bạn có thể truy cập tức thời. Nếu tôi muốn tìm kiếm bất cứ điều gì, Tôi muốn để có thể chỉ, bùng nổ, tìm thấy nó một cách chính xác, và kéo nó ra. Và do đó, một cấu trúc trong đó chúng tôi sẽ trở nên rất gần để có thể truy cập liên tục thời gian, Chén thánh này trong lập trình không đổi thời gian được gọi là một bảng băm. Và do đó, David đã đề cập trước đây [Không nghe thấy] một chút trong bài giảng, nhưng chúng ta sẽ thực sự lặn sâu trong tuần này trên một mảnh đó là liên quan đến làm thế nào một bảng băm làm việc. 

Vì vậy, cách mà một hash công trình bảng, ví dụ, nếu tôi muốn để lưu trữ một loạt các từ ngữ, một bó của các từ trong ngôn ngữ tiếng Anh, Tôi về mặt lý thuyết có thể đặt chuối, táo, kiwi, xoài, cặp, và dưa đỏ trên tất cả chỉ là một mảng. Tất cả họ có thể phù hợp và được tìm thấy. Nó muốn được loại đau đớn đến tìm kiếm thông qua và truy cập, nhưng cách dễ dàng hơn để làm điều này là rằng chúng ta có thể tạo ra một cấu trúc thực sự gọi là một bảng băm, nơi chúng tôi băm. Chúng tôi chạy tất cả các phím của chúng tôi thông qua một hàm băm, một phương trình, có thể biến tất cả chúng thành một số loại của một giá trị mà sau đó chúng ta có thể lưu trữ lên bản chất là một mảng các danh sách liên kết. 

Và như vậy ở đây, nếu chúng ta muốn để lưu trữ các từ tiếng Anh, chúng tôi có khả năng có chỉ là, tôi không biết, biến tất cả các chữ cái đầu tiên vào một số loại của một số. Và như vậy, ví dụ, nếu tôi muốn Một đồng nghĩa với apple-- hoặc với chỉ số 0, và B để được đồng nghĩa với 1, chúng ta có thể có 26 mục mà chỉ có thể lưu trữ tất cả các chữ cái của bảng chữ cái mà chúng ta sẽ bắt đầu với. Và sau đó chúng ta có thể có táo ở các chỉ số từ 0. Chúng tôi có thể có chuối tại chỉ số 1, dưa đỏ tại các chỉ số của 2, và vv và vv. Và như vậy, nếu tôi muốn tìm kiếm bảng và truy cập băm của tôi táo, Tôi biết táo bắt đầu với A, và tôi biết chính xác rằng nó phải được và băm bảng tại chỉ số 0 bởi vì các chức năng trước đây đã giao. 

Vì vậy, tôi không biết, chúng tôi là một chương trình sử dụng nơi bạn sẽ được tính phí với arbitrarily-- không tùy tiện, với cố gắng để chu đáo nghĩ về phương trình tốt để có thể lây lan ra tất cả các giá trị của bạn theo đó, họ có thể dễ dàng truy cập nó sau này có như một phương trình mà bạn, mình, biết. Vì vậy, trong ý nghĩa nếu tôi muốn đi đến xoài, tôi biết, oh, nó bắt đầu với m. Nó phải có các chỉ số của 12. Tôi không cần phải tìm kiếm thông qua bất cứ điều gì. Tôi biết exactly-- tôi chỉ có thể đi đến các chỉ số của 12 và kéo ra ngoài. 

Mọi người đều rõ ràng về cách thức một hàm bảng băm của công trình? Đó là loại chỉ là một mảng phức tạp hơn. Đó là tất cả nó là. ĐƯỢC. 

Vì vậy, tôi đoán chúng tôi chạy vào vấn đề này của những gì sẽ xảy ra nếu bạn có nhiều điều mà cung cấp cho bạn những chỉ số tương tự? Vì vậy, nói chức năng của chúng tôi, tất cả nó đã làm là lấy lá thư đầu tiên và biến chúng thành một tương ứng từ 0 đến 25 chỉ số. Điều đó hoàn toàn tốt nếu bạn chỉ có một của mỗi. Nhưng lần thứ hai bạn bắt đầu có hơn, bạn sẽ có những gì được gọi là một vụ va chạm. 

Vì vậy, nếu tôi cố gắng để chèn chôn vào một hash bảng mà đã có chuối trên đó, những gì sẽ xảy ra khi bạn cố gắng để chèn đó? Những điều xấu vì chuối đã tồn tại trong các chỉ số mà bạn muốn lưu trữ nó trong. Berry loại là như thế, ah, tôi phải làm gì? Tôi không biết đi đâu. Làm thế nào để giải quyết này? 

Và như vậy các bạn sẽ loại thấy chúng tôi làm điều này khó khăn nơi chúng ta có thể loại thực sự tạo danh sách liên kết trong mảng của chúng tôi. Và do đó, cách đơn giản nhất để suy nghĩ về điều này, tất cả các bảng băm là một mảng các danh sách liên kết. Và như vậy, trong ý nghĩa đó, bạn có mảng này đẹp của con trỏ, và sau đó mỗi con trỏ ở giá trị đó, trong số đó, thực sự có thể trỏ đến những thứ khác. Và do đó, bạn có tất cả những riêng chuỗi sắp tắt của một mảng lớn. 

Và như vậy ở đây, nếu tôi muốn chèn berry, Tôi biết, OK, tôi sẽ đầu vào nó thông qua hàm băm của tôi. Tôi sẽ kết thúc với chỉ số của 1, và sau đó tôi sẽ có thể có chỉ là một tập hợp con nhỏ hơn này khổng lồ từ điển 140.000 từ. Và sau đó tôi chỉ có thể nhìn qua 1/26 đó. 

Và như vậy thì tôi chỉ có thể chèn berry trước hoặc sau khi chuối trong trường hợp này? Sau khi, phải không? Và do đó, bạn sẽ muốn chèn nút này sau chuối, và như vậy bạn sẽ chèn ở đuôi của mà danh sách liên kết. Tôi sẽ quay trở lại đến slide trước đây, vậy các bạn có thể xem như thế nào hàm băm làm việc. 

Vì vậy, hàm băm là phương trình này rằng bạn đang chạy loại đầu vào của bạn thông qua để có được bất cứ điều gì chỉ số bạn muốn gán cho nó hướng tới. Và như vậy, trong ví dụ này, tất cả chúng ta muốn phải làm là lấy chữ cái đầu tiên, biến chúng thành một chỉ số, sau đó chúng tôi có thể lưu trữ trong đó hàm băm của chúng tôi. Tất cả chúng tôi đang làm ở đây là chúng tôi chuyển đổi các chữ cái đầu tiên. Vì vậy keykey [0] chỉ là chữ cái đầu tiên của bất cứ chuỗi chúng ta đang gặp phải, chúng ta đang đi trong. Chúng tôi đang chuyển đổi đó để phía trên, và chúng tôi đã trừ bằng chữ hoa A, vì vậy tất cả những gì đang làm là đem lại cho chúng ta một số trong đó chúng ta có thể băm giá trị của mình lên. 

Và sau đó chúng ta sẽ trở băm modulus SIZE. Hãy rất, rất cẩn thận bởi vì, về mặt lý thuyết, đây giá trị băm của bạn có thể là vô hạn. Nó chỉ có thể đi trên và trên và trên. Nó có thể là một số thực sự, thực sự có giá trị lớn, nhưng vì bảng băm của bạn bạn đã tạo ra chỉ có 26 chỉ số, bạn muốn chắc chắn của bạn modulusing để bạn không run-- đó là cùng điều như queue-- của bạn do đó bạn không chạy ra khỏi dưới cùng của hàm băm của bạn. 

Bạn muốn quấn nó lại xung quanh cách tương tự trong [không nghe được] khi bạn có giống như một rất, thư rất lớn, bạn không muốn điều đó chỉ cần chạy ra cuối cùng. Cùng một điều ở đây, bạn muốn chắc chắn nó không chạy ra khỏi cuối bởi gói xung quanh để đầu bảng. Vì vậy, đây chỉ là một rất hàm băm đơn giản. Tất cả những gì đã làm là lấy đầu tiên thư của bất cứ đầu vào của chúng tôi là và biến chúng thành một chỉ số chúng ta có thể đưa vào bảng băm của chúng tôi. 

Yeah, và như vậy như tôi đã nói trước đây, cách chúng ta giải quyết va chạm trong bảng băm của chúng tôi đang có, những gì chúng ta gọi, dí. Vì vậy, nếu bạn cố gắng để chèn nhiều từ bắt đầu với cùng một điều, bạn sẽ có một giá trị băm. Quả bơ táo, nếu bạn đã chạy nó thông qua hàm băm của chúng tôi, sẽ cung cấp cho bạn những cùng một số, số 0. Và do đó, cách giải quyết chúng tôi đó là rằng chúng ta có thể thực sự loại liên kết chúng với nhau thông qua danh sách liên kết. 

Và như vậy trong ý nghĩa này, các bạn có thể nhìn thấy loại về cách cấu trúc dữ liệu chúng tôi đã được thiết lập trước đó như một nho danh sách liên kết loại các thể đến với nhau thành một. Và sau đó bạn có thể tạo đến nay cấu trúc dữ liệu hiệu quả hơn mà có thể xử lý một lượng lớn dữ liệu, thay đổi kích thước tùy rằng động vào nhu cầu của bạn. Mọi người đều rõ ràng? Tất cả mọi người loại rõ ràng về những gì xảy ra ở đây? 

Nếu tôi muốn insert-- gì một trái cây bắt đầu với, tôi không biết, B, khác hơn so với quả mọng, chuối. 

Đung Blackberry. 

Andi PENG: Blackberry, blackberry. Trường hợp nào blackberry đi đây? Vâng, chúng tôi thực sự đã không được sắp xếp này chưa, nhưng về mặt lý thuyết nếu chúng ta muốn có này theo thứ tự bảng chữ cái, nơi nên Blackberry đi? 

Đung [Không nghe thấy] 

Andi PENG: Chính xác, sau khi ở đây, phải không? Nhưng kể từ đó là rất khó reorder-- Tôi đoán nó thuộc vào các bạn. Các bạn có thể hoàn toàn thực hiện bất cứ điều gì bạn muốn. Cách hiệu quả hơn để làm điều này có lẽ sẽ được sắp xếp liên kết của bạn liệt kê vào thứ tự chữ cái, và vì vậy khi bạn đang chèn vật, bạn muốn phải chắc chắn để chèn chúng vào thứ tự chữ cái vì vậy mà sau đó khi bạn đang cố gắng để tìm kiếm chúng, bạn không phải đi qua tất cả mọi thứ. Bạn biết chính xác nơi nó là, và nó dễ dàng hơn. 

Nhưng nếu bạn có loại điều xen kẽ một cách ngẫu nhiên, bạn vẫn sẽ có để đi qua nó anyways. Và vì vậy nếu tôi muốn chỉ chèn blackberry đây và tôi muốn tìm kiếm nó, tôi biết, oh, blackberry phải bắt đầu với chỉ số 1, vì vậy tôi biết ngay lập tức tìm kiếm chỉ ở mức 1. Và sau đó tôi có thể loại đi qua các danh sách liên kết cho đến khi tôi nhận được để blackberry, và then-- yeah? 

Đung Nếu bạn đang cố gắng để create-- Tôi đoán như thế này là một hash rất đơn giản chức năng. Và nếu chúng ta muốn làm nhiều lớp như thế, OK, chúng tôi muốn tách riêng thành giống như tất cả các chữ cái ABC và sau đó một lần nữa để thích bộ khác các chữ cái chữ cái trong đó, được chúng tôi đặt như một hash bảng trong một bảng băm, hoặc như một chức năng trong một chức năng? Hoặc là that-- 

Andi PENG: Vì vậy, băm của bạn function-- bảng băm của bạn có thể lớn như bạn muốn nó. Vì vậy, trong ý nghĩa này, tôi nghĩ nó là rất dễ dàng, rất đơn giản cho tôi để dựa chỉ là loại trên các chữ cái của từ đầu tiên. Và do đó, chỉ có 26 tùy chọn. Tôi chỉ có thể nhận được 26 lựa chọn từ 0-25 vì họ chỉ có thể bắt đầu từ A đến Z. Nhưng nếu bạn muốn thêm, có lẽ, phức tạp hơn hoặc nhanh hơn chạy thời gian để bạn bảng băm, bạn hoàn toàn có thể làm tất cả các loại vật. Bạn có thể làm cho riêng bạn phương trình cung cấp cho bạn phân phối ở của bạn từ, sau đó khi bạn tìm kiếm, nó sẽ được nhanh hơn. 

Đó là hoàn toàn vào bạn kẻ làm thế nào bạn muốn thực hiện điều đó. Hãy nghĩ về nó như là chỉ xô. Nếu tôi muốn có 26 xô, tôi sẽ để sắp xếp mọi thứ vào những xô. Nhưng tôi sẽ có một bó công cụ trong mỗi nhóm, vì vậy nếu bạn muốn làm cho nó nhanh hơn và hiệu quả hơn, cho tôi có một trăm thùng. 

Nhưng sau đó bạn phải tìm ra một cách để sắp xếp mọi thứ để họ có trong xô thích họ phải ở trong. Nhưng sau đó khi bạn thực sự muốn nhìn vào thùng đó, nó nhanh hơn rất nhiều bởi vì có ít công cụ trong mỗi nhóm. Và như vậy, yeah, đó là thực sự các trick cho các bạn trong pset5 là bạn sẽ được thách thức để chỉ cần tạo bất cứ điều gì là hiệu quả nhất chức năng mà bạn có thể nghĩ đến được có thể lưu trữ và kiểm tra các giá trị này. 

Hoàn toàn vào bạn kẻ tuy nhiên bạn muốn làm điều đó, nhưng đó là một điểm thực sự tốt. Đó là loại logic bạn muốn bắt đầu suy nghĩ về là, tốt, tại sao tôi không làm cho nhiều xô. Và sau đó tôi phải tìm kiếm điều ít hơn, và sau đó có lẽ tôi có một hàm băm khác nhau. 

Vâng, có rất nhiều cách để làm điều này pset, một số là nhanh hơn so với những người khác. Tôi hoàn toàn sẽ chỉ nhìn thấy như thế nào nhanh là các bạn sẽ nhanh nhất có thể có được chức năng của bạn để làm việc. OK, tất cả mọi người trên tốt chaining và băm bảng? Nó thực sự giống như một rất đơn giản khái niệm, nếu bạn nghĩ về nó. Tất cả đó là là tách bất cứ điều gì đầu vào của bạn là vào xô, phân loại chúng, và sau đó tìm kiếm các liệt kê rằng có liên kết với. 

Mát. Được rồi, bây giờ chúng ta có một loại khác nhau cấu trúc dữ liệu đó được gọi là một cây. Chúng ta hãy đi vào và nói về cố gắng đó là khác biệt rõ rệt, nhưng trong cùng thể loại. Về cơ bản, tất cả các cây là thay vì tổ chức dữ liệu theo cách tuyến tính rằng một bảng băm does-- bạn biết, nó có một đỉnh và đáy và sau đó bạn loại liên kết tắt của một it-- cây có đầu mà bạn gọi là gốc, và sau đó nó có những chiếc lá tất cả xung quanh nó. 

Và vì vậy tất cả các bạn có ở đây chỉ là nút trên cùng trỏ đến các nút khác, mà điểm để các nút hơn, và vv và vv. Và vì vậy bạn chỉ có các chi nhánh tách. Nó chỉ là một cách khác nhau của tổ chức dữ liệu, và vì chúng ta gọi nó là một cây, các bạn just-- nó chỉ mô hình ra để trông giống như một cái cây. Đó là lý do tại sao chúng tôi gọi nó là cây. 

Bảng băm trông giống như một bảng. Một cây chỉ trông giống như một cái cây. Tất cả đó là là một riêng biệt cách thức tổ chức các nút tùy thuộc vào nhu cầu của bạn. 

Vì vậy, bạn có một bộ rễ và sau đó bạn có lá. Cách mà chúng ta có thể đặc biệt nghĩ về nó là một cây nhị phân, một cây nhị phân chỉ là một loại hình cụ thể của một cây trong đó mỗi nút chỉ điểm để, lúc tối đa, hai nút khác. Và do đó, ở đây bạn có khác biệt đối xứng trong cây của bạn mà làm cho nó dễ dàng hơn để loại tìm tại những giá trị bạn là bởi vì sau đó bạn luôn luôn có một trái hoặc bên phải. Có bao giờ giống như một phần ba trái từ bên trái hoặc thứ tư từ bên trái. Nó chỉ là bạn có một trái và một bên phải và bạn có thể tìm kiếm một trong hai. Và như vậy tại sao điều này là hữu ích? Cách rằng đây là là hữu ích nếu bạn đang tìm kiếm để tìm kiếm thông qua các giá trị, phải không? Thay vì thực hiện nhị phân tìm kiếm trong một mảng lỗi, nếu bạn muốn để có thể chèn các nút và lấy đi các nút theo ý thích và cũng bảo tồn các tìm kiếm năng lực tìm kiếm nhị phân. Vì vậy, theo cách này, chúng ta đang loại tricking-- nhớ khi chúng ta cho biết danh sách liên kết không thể tìm kiếm nhị phân? Chúng tôi đang tạo ra một loại cấu trúc dữ liệu rằng thủ đoạn đó vào làm việc. 

Và danh sách như vậy bởi vì liên kết là tuyến tính, họ chỉ có liên kết một sau khi khác. Chúng ta có thể có loại loại khác nhau của các con trỏ điểm đó đến các nút khác nhau có thể giúp chúng ta tìm kiếm. Và như vậy ở đây, nếu tôi muốn có một cây tìm kiếm nhị phân, Tôi biết rằng giữa tôi nếu 55. Tôi chỉ cần đi để tạo ra rằng như giữa của tôi, như là người chủ của tôi, và sau đó tôi sẽ có giá trị spin off của nó. 

Vì vậy, ở đây, nếu tôi sẽ tìm kiếm giá trị của 66, tôi có thể bắt đầu ở mức 55. Đó là 66 lớn hơn 55? Có nó, vì vậy tôi biết tôi Mus tìm kiếm i n con trỏ bên phải của cây này. Tôi đi đến 77. OK, là 66 nhỏ hơn hoặc lớn hơn 77? Nó ít hơn, vì vậy bạn có biết, oh, mà đã được các nút còn lại. 

Và vì vậy ở đây chúng ta đang loại bảo quản tất cả những điều tuyệt vời về mảng, do đó, như thay đổi kích thước động của các đối tượng, được có thể chèn và xóa theo ý muốn, mà không cần phải lo lắng về sự cố định số lượng không gian. Chúng tôi vẫn còn lưu giữ tất cả những điều tuyệt vời đồng thời có thể để bảo tồn đăng nhập và thời gian tìm kiếm nhị phân tìm kiếm rằng chúng tôi chỉ là trước đây có thể có được một cụm từ. 

Cấu trúc dữ liệu thoáng mát, loại phức tạp để thực hiện, các node. Như bạn có thể thấy, tất cả nó là cấu trúc của nút là bạn có một trái và một con trỏ bên phải. Đó là tất cả nó là. Vì vậy, thay vì chỉ có một x hoặc trước đó. Bạn có một trái hoặc bên phải, và sau đó bạn có thể loại liên kết chúng lại với nhau Tuy nhiên bạn nên chọn. 

OK, chúng tôi đang thực sự đi chỉ mất một vài phút. Vì vậy, chúng ta sẽ quay trở lại đây. Như tôi đã nói trước đây, Tôi loại giải thích logic đằng sau như thế nào chúng tôi sẽ tìm kiếm thông qua này. Chúng ta sẽ cố gắng pseudocoding ra điều này để thấy nếu chúng ta loại có thể áp dụng cùng một logic của tìm kiếm nhị phân để một kiểu khác nhau của cấu trúc dữ liệu. Nếu các bạn muốn đi như một cặp vợ chồng phút để nghĩ đến điều này. ĐƯỢC. Được rồi, tôi sẽ thực sự chỉ cần cung cấp cho bạn the-- không, chúng ta sẽ nói về các giả đầu tiên. Vì vậy, không ai muốn để cung cấp cho một đâm vào những gì điều đầu tiên bạn muốn làm khi bạn đang bắt đầu tìm kiếm là gì? Nếu chúng tôi đang tìm kiếm giá trị của 66, có chuyện gì điều đầu tiên chúng tôi muốn làm nếu chúng ta muốn thành dạng nhị phân tìm kiếm cây này? 

Đung Bạn muốn nhìn bên phải và tìm kiếm bên trái và xem [không nghe] số lượng lớn hơn. 

Andi PENG: Yeah, chính xác. Vì vậy, bạn sẽ nhìn vào gốc của bạn. Có rất nhiều cách để bạn có thể gọi nó, nút cha của người nói. Tôi muốn nói root bởi đó là giống như gốc rễ của cây. Bạn sẽ nhìn vào nút gốc của bạn, và bạn sẽ gặp là 66 lớn hơn hơn hoặc ít hơn 55. Và nếu nó lớn hơn, tốt, nó là lớn hơn, nơi nào chúng ta muốn nhìn? Nơi nào chúng ta muốn tìm kiếm bây giờ, phải không? Chúng tôi muốn tìm kiếm nửa bên phải của cây này. 

Vì vậy, chúng ta có, thuận tiện, một con trỏ trỏ bên phải. Và như vậy thì chúng ta có thể thiết lập gốc mới của chúng tôi là 77. Chúng tôi chỉ có thể đi đến bất cứ nơi con trỏ trỏ đến. Vâng, oh, ở đây chúng tôi đang bắt đầu 77, và chúng ta có thể chỉ làm điều này một cách đệ quy một lần nữa và một lần nữa. Bằng cách này, bạn loại của có một chức năng. Bạn có một cách tìm kiếm mà bạn chỉ có thể lặp lại hơn và hơn và hơn, tùy thuộc vào nơi bạn muốn tìm cho đến khi bạn cuối cùng có được với giá trị mà bạn đang tìm kiếm. Có lý? 

Tôi về để cho bạn thấy thực tế mã, và nó rất nhiều mã. Không cần phải lăn tăn. Chúng tôi sẽ nói chuyện qua nó. 

Thực ra là không. Đó chỉ là giả. OK, đó mới chỉ là giả, đó là một chút phức tạp, nhưng nó hoàn toàn tốt. Tất cả mọi người sau cùng ở đây? Nếu rễ là null, trở lại sai bởi vì điều đó có nghĩa bạn thậm chí không có bất cứ điều gì ở đó. 

Nếu gốc n là giá trị, vì vậy nếu nó sẽ xảy ra là một trong những bạn đang xem, sau đó bạn đang đi để trở về đúng vì bạn biết bạn tìm thấy nó. Nhưng nếu giá trị nhỏ hơn gốc của n, bạn sẽ tìm kiếm bên trái trẻ em hoặc các lá trái, bất cứ điều gì bạn muốn gọi nó. Và nếu giá trị lớn hơn gốc, bạn đang đi để tìm kiếm cây bên phải, sau đó chỉ cần chạy chức năng thông qua tìm kiếm một lần nữa. 

Và nếu rễ là null, mà đó có nghĩa là bạn đã đạt đến kết thúc? Điều đó có nghĩa là bạn không có nhiều lá cây hơn để tìm kiếm, sau đó bạn biết, oh, tôi đoán nó không phải ở đây bởi vì sau khi tôi đã nhìn qua toàn bộ và không phải ở đây, nó chỉ có thể không có mặt ở đây. 

Điều đó có ý nghĩa với tất cả mọi người? Vì vậy, nó giống như tìm kiếm nhị phân bảo quản khả năng của danh sách liên kết. Cool, và do đó loại thứ hai cấu trúc dữ liệu các bạn có thể cố gắng thực hiện trên pset của bạn, bạn chỉ cần chọn một phương pháp. Nhưng có lẽ một phương pháp khác để bảng băm là những gì chúng ta gọi là một Trie. 

Tất cả là một Trie là một loại hình cụ thể của cây có giá trị đó đi đến các giá trị khác. Vì vậy, thay vì có một nhị phân cây trong ý nghĩa rằng chỉ có một điều có thể trỏ đến hai, bạn có thể có điểm một điều để nhiều, nhiều điều. Bạn có thực chất có mảng bên trong mà bạn lưu trữ con trỏ trỏ tới các mảng khác. 

Vì vậy, các nút của chúng tôi như thế nào sẽ xác định một Trie là chúng ta muốn có một Boolean, c từ, phải không? Vì vậy, các nút là Boolean như đúng hay sai, trước hết ở đầu mảng đó, đây là một từ? Thứ hai, bạn muốn để có con trỏ để bất cứ điều gì với phần còn lại của họ đang có. Một chút phức tạp, một trừu tượng chút, nhưng Tôi sẽ giải thích những gì mà tất cả các phương tiện. 

Vì vậy, ở đây, ở phía trên, nếu bạn có một mảng được khai báo đã có, một nút mà bạn có một Boolean giá trị được lưu trữ ở phía trước mà nói với bạn là một từ này? Này không phải là một từ? Và sau đó bạn có phần còn lại của mảng của bạn mà thực sự lưu trữ tất cả các khả năng của những gì nó có thể được. Vì vậy, ví dụ, như ở đầu trang bạn có điều đầu tiên mà nói đúng hay sai, có hay không, đây là một từ. 

Và sau đó bạn có 0 đến 26 của các chữ cái mà bạn có thể lưu trữ. Nếu tôi muốn tìm kiếm ở đây cho bat, tôi đi đến hàng đầu và tôi tìm kiếm B. Tôi tìm B trong tôi mảng, và vì vậy tôi biết, OK, là B một từ? B không phải là một từ, do đó do đó Tôi phải tiếp tục tìm kiếm. Tôi đi từ B, và tôi nhìn vào con trỏ mà B chỉ ra được sự và tôi thấy một mảng của các thông tin, cấu trúc tương tự mà chúng ta có trước. 

Và here-- oh, tiếp theo thư trong [không nghe được] là A. Vì vậy, chúng ta nhìn vào mảng đó. Chúng tôi tìm thấy những giá trị thứ tám, và sau đó chúng ta nhìn thấy, oh, hey, đó là một từ, là B-A là một từ? Nó không phải là một từ. Chúng ta phải tiếp tục tìm kiếm. 

Và như vậy thì chúng ta nhìn đến nơi con trỏ của A điểm, và nó chỉ đến một cách khác trong mà chúng tôi có giá trị lưu trữ nhiều. Và cuối cùng, chúng tôi nhận được B-A-T, đó là một từ. Và vì vậy thời gian tiếp theo bạn nhìn, bạn sẽ để có mà kiểm tra, và vâng, hàm Boolean điều này là đúng. Và như vậy trong ý nghĩa chúng ta đang loại của việc có một cây với mảng. 

Vì vậy, sau đó bạn có thể loại tìm kiếm xuống. Thay vì băm một chức năng và gán giá trị của danh sách liên kết, bạn chỉ có thể thực hiện một Trie để tìm kiếm downwords. Thực sự, thực sự phức tạp thứ. Không dễ dàng để nghĩ về vì tôi giống nhổ nước bọt rất nhiều cấu trúc dữ liệu ra vào bạn, nhưng tất cả mọi người không loại hiểu logic của các công trình này? 

OK, mát mẻ. Vì vậy, B-A-T, và sau đó bạn đang đi để tìm kiếm. Lần sau, bạn sẽ để xem, oh, hey, đó là sự thật, vì thế tôi biết điều này phải là một từ. 

Cùng một điều cho sở thú. Vì vậy, đây là điều ngay bây giờ, nếu chúng ta muốn tìm kiếm các vườn thú, ngay bây giờ, Hiện tại vườn thú không phải là một từ trong từ điển của chúng tôi bởi vì, như các bạn có thể thấy, nơi đầu tiên mà chúng ta có một Boolean trở về đúng là vào cuối zoom. Chúng tôi có Z-O-O-M. 

Và như vậy ở đây, chúng ta không thực sự có từ, sở thú, trong từ điển của chúng tôi vì hộp kiểm này không được chọn. Vì vậy, các máy tính không biết rằng sở thú là một từ vì cách làm đó, chúng tôi đã được lưu giữ nó, chỉ có một zoom đây thực sự có một giá trị Boolean đó là được trở thành sự thật. Vì vậy, nếu chúng ta muốn chèn từ, sở thú, vào trong từ điển của chúng tôi, làm thế nào chúng ta sẽ đi về làm việc đó? Những gì chúng ta phải làm gì để đảm bảo chúng tôi Máy tính sẽ biết rằng Z-O-O là một từ và không phải là từ đầu tiên là Z-O-O-M? 

Đung [Không nghe thấy] 

Andi PENG: Chính xác, chúng tôi muốn chắc chắn rằng điều này ở đây, đó là giá trị Boolean kiểm tra ra rằng đó là sự thật. Z-O-O, sau đó chúng ta sẽ kiểm tra xem, vì vậy chúng tôi biết chính xác, hey, vườn thú là một từ. Tôi sẽ nói với các máy tính mà nó là một từ quá rằng khi kiểm tra máy tính, nó biết rằng sở thú là một từ. 

Bởi vì nhớ tất cả những dữ liệu này cấu trúc, nó rất dễ dàng cho chúng tôi để nói, oh, bat là một từ. Zoo là một từ. Zoom là một từ. Nhưng khi bạn đang xây dựng nó, máy tính không có ý tưởng. 

Vì vậy, bạn phải nói cho nó chính xác ở điểm nào đây là một từ? Tại thời điểm nào là nó không phải là một từ? Và vào thời điểm những gì làm tôi cần phải tìm kiếm những điều, và vào thời điểm những gì tôi cần để đi tiếp theo? Mọi người đều rõ ràng về điều đó? Mát. 

Và do đó, sau đó đến các Vấn đề làm sao chúng tôi sẽ đi về chèn một cái gì đó đó là thực sự không có? Vì vậy, chúng ta hãy chỉ nói rằng chúng ta muốn chèn từ, phòng tắm, vào Trie của chúng tôi. Như các bạn có thể nhìn thấy như hiện nay tất cả chúng ta có bây giờ là B-A-T, và cấu trúc dữ liệu mới này có có một pint đó chỉ để null vì chúng ta giả định rằng, oh, không có lời nói sau B-A-T, tại sao chúng ta cần phải giữ có những thứ sau đó T. 

Nhưng vấn đề phát sinh nếu chúng ta làm bạn muốn có một lời nói ra sau các T. Nếu bạn có bồn tắm, bạn đang sẽ muốn một H phải. Và do đó, cách chúng ta sẽ làm điều đó là chúng ta sẽ tạo ra một nút riêng biệt. Chúng tôi không phân bổ cho bất kỳ số tiền bộ nhớ cho mảng mới này, và chúng ta sẽ gán lại con trỏ. 

Chúng tôi sẽ giao H, Trước hết, null này, chúng ta sẽ thoát khỏi. Chúng ta sẽ có xuống dưới điểm H. Nếu chúng ta nhìn thấy một H, chúng tôi muốn nó để đi đến một nơi khác. 

Tại đây, chúng ta có thể kiểm tra tắt yes. Nếu chúng ta đánh một H sau khi T, oh, sau đó chúng ta biết rằng đây là một từ. Các Boolean là sẽ trở thành sự thật. Mọi người đều rõ ràng về cách mà đã xảy ra? ĐƯỢC. 

Vì vậy, về cơ bản, tất cả các các cấu trúc dữ liệu chúng ta đã đi qua ngày hôm nay, tôi đã đi qua chúng thực sự, thực sự nhanh chóng và không để nhiều chi tiết, và đó là OK. Một khi bạn bắt đầu rối tung với nó, bạn sẽ có theo dõi các nơi tất cả các con trỏ là, những gì đang xảy ra trong bạn cấu trúc dữ liệu, vân vân. Họ sẽ rất hữu ích, và nó là vào bạn kẻ hoàn toàn tìm ra cách bạn muốn thực hiện điều này. 

Và như vậy pset4, của 5-- oh, đó là sai. Pset5 là lỗi chính tả. Như tôi đã nói trước đây, bạn sẽ, một lần một lần nữa, tải về mã nguồn từ chúng tôi. Có sẽ là ba chính điều bạn sẽ phải download. Bạn sẽ tải về từ điển, kers, và văn bản. 

Tất cả những điều này là hoặc là từ điển của từ chúng tôi muốn bạn để kiểm tra hoặc kiểm tra thông tin chúng tôi muốn bạn để kiểm tra chính tả. Và do đó, các bộ từ điển chúng tôi cung cấp cho bạn đang đi để cung cấp cho bạn những lời thực tế mà chúng tôi muốn bạn lưu trữ bằng cách nào đó trong một cách đó là hiệu quả hơn nhiều so với một mảng. Và sau đó các văn bản có sẽ là những gì chúng tôi yêu cầu bạn kiểm tra chính tả để đảm bảo tất cả các từ có từ thực tế. 

Và như vậy ba khối chương trình mà chúng tôi sẽ cung cấp cho bạn được gọi là dictionary.c, dictionary.h, và speller.c. Và vì vậy tất cả dictionary.c không được những gì bạn được yêu cầu để thực hiện. Nó nạp từ. Nó chính tả kiểm tra chúng, và nó làm cho chắc chắn rằng tất cả mọi thứ được đưa vào đúng. 

diction.h chỉ là một tập tin thư viện mà tuyên bố tất cả những chức năng. Và speller.c, chúng tôi sẽ cung cấp cho bạn. Bạn không cần phải sửa đổi bất kỳ của nó. Tất cả speller.c không là mất rằng, tải nó, kiểm tra tốc độ của nó, các bài kiểm tra benchmark của như thế nào nhanh chóng bạn có thể làm mọi việc. 

Đó là một Speller. Chỉ cần không gây rối với nó, nhưng chắc chắc chắn rằng bạn hiểu những gì nó làm. Chúng tôi sử dụng một chức năng gọi là getrusage mà kiểm tra việc thực hiện chính tả của bạn kiểm sát viên. Tất cả nó là cơ bản được kiểm tra thời gian của tất cả mọi thứ trong từ điển của bạn, do đó hãy chắc chắn rằng bạn hiểu nó. Hãy cẩn thận để không gây rối với nó hay điều gì khác sẽ không chạy đúng. 

Và phần lớn các thách thức này là dành cho các bạn để thực sự thay đổi dictionary.c. Chúng tôi sẽ cung cấp cho bạn 140.000 từ trong từ điển. Chúng tôi sẽ cung cấp cho bạn một văn bản tập tin mà có những lời nói, và chúng tôi muốn bạn để có thể tổ chức chúng vào một bảng băm hoặc một Trie bởi vì khi chúng tôi yêu cầu bạn đánh vần check-- tưởng tượng nếu bạn chính tả kiểm tra như Odyssey của Homer. Nó giống như, thử nghiệm rất lớn rất lớn này. 

Hãy tưởng tượng, nếu mỗi đơn từ mà bạn đã phải tìm thông qua một loạt các giá trị 140.000. Điều đó sẽ mất mãi mãi cho máy tính của bạn để chạy. Đó là lý do tại sao chúng tôi muốn tổ chức của chúng tôi dữ liệu vào cấu trúc dữ liệu hiệu quả hơn chẳng hạn như một bảng băm hoặc một Trie. Và sau đó các bạn có thể loại khi bạn tìm kiếm truy cập thứ dễ dàng hơn và nhanh chóng hơn. 

Và vì vậy hãy cẩn thận để giải quyết va chạm. Bạn sẽ nhận được một bó các từ đó bắt đầu với A. Bạn sẽ nhận được một lời bó bắt đầu bằng B. Up cho bạn chàng trai như thế nào bạn muốn giải quyết nó. Có lẽ có nhiều hàm băm hiệu quả hơn là chỉ các chữ cái đầu tiên của một cái gì đó, và vì vậy đó là tùy thuộc vào bạn chàng trai để loại làm bất cứ điều gì bạn muốn. 

Có lẽ bạn muốn thêm tất cả các chữ cái với nhau. Có thể bạn muốn muốn làm những điều kỳ lạ để hạch toán số của các chữ cái, sao cũng được. Up để các bạn làm thế nào bạn muốn làm. Nếu bạn muốn làm một bảng băm, nếu bạn muốn thử một Trie, hoàn toàn tùy thuộc vào bạn. Tôi sẽ cảnh báo bạn trước thời gian mà các Trie thường là một chút khó khăn hơn chỉ vì có rất nhiều nhiều con trỏ để theo dõi. Nhưng hoàn toàn vào bạn guys. Đó là hiệu quả hơn nhiều trong hầu hết các trường hợp. Bạn muốn thực sự có thể giữ theo dõi tất cả các con trỏ của bạn. Giống như làm điều tương tự rằng tôi đã làm ở đây. Khi bạn đang cố gắng để chèn giá trị vào một bảng băm hoặc xóa, hãy chắc chắn rằng bạn đang thực sự theo dõi của nơi mà mọi thứ là vì nó thực sự dễ dàng cho nếu tôi cố gắng để chèn như từ, andy. Hãy chỉ nói rằng đó là một từ thực tế, từ đó, andy, vào một danh sách khổng lồ của A từ. 

Nếu tôi chỉ xảy ra để gán lại một sai con trỏ, oops, có đi toàn bộ phần còn lại của danh sách liên kết của tôi. Bây giờ từ duy nhất tôi có là andy, và bây giờ tất cả các từ khác trong từ điển đã bị mất. Và do đó, bạn muốn chắc chắn rằng bạn theo dõi tất cả các con trỏ của bạn hoặc người nào khác bạn sẽ nhận được vấn đề lớn trong mã của bạn. Vẽ những điều trên một cách cẩn thận từng bước. Nó làm cho nó dễ dàng hơn nhiều để nghĩ đến. 

Và cuối cùng, bạn muốn để có thể kiểm tra hiệu suất của bạn trong chương trình của bạn trên bảng lớn. Nếu các bạn có một nhìn vào CS50 ngay bây giờ, chúng tôi có những gì được gọi là các bảng lớn. Đây là bảng điểm của các nhanh nhất đánh vần lần kiểm tra trên tất cả các CS50 ngay bây giờ, tôi nghĩ rằng các hàng đầu như 10 lần tôi nghĩ rằng tám trong số đó là nhân viên. Chúng tôi thực sự muốn các bạn để đánh bại chúng tôi. 

Tất cả chúng ta đã cố gắng thực hiện mã nhanh nhất có thể. Chúng tôi muốn các bạn thử để thách thức chúng tôi và thực hiện nhanh hơn so với tất cả chúng ta có thể. Và vì vậy đây thực sự là lần đầu tiên chúng tôi hỏi các bạn phải làm một pset đó bạn thực sự có thể làm trong bất cứ phương pháp bạn muốn. 

Tôi luôn luôn nói rằng, đây là giống hơn đến một giải pháp thực tế cuộc sống, phải không? Tôi nói, hey, tôi cần bạn làm điều này. Xây dựng một chương trình mà thực hiện điều này đối với tôi. Làm nó tuy nhiên bạn muốn. Tôi chỉ biết rằng tôi muốn nhanh chóng. Đó là thách thức của bạn trong tuần này. Các bạn, chúng ta đang đi để cung cấp cho bạn một công việc. Chúng tôi sẽ cung cấp cho bạn một thách thức. Và sau đó nó lên đến với bạn để hoàn toàn chỉ ra những gì là nhanh nhất và nhất cách hiệu quả để thực hiện điều này. Yeah? 

Đung Có phải chúng ta được phép nếu muốn nghiên cứu những cách nhanh hơn làm bảng băm trực tuyến, chúng tôi có thể làm đó và trích dẫn mã của người khác? Andi PENG: Vâng, hoàn toàn tốt. Vì vậy, nếu các bạn đọc spec, có một dòng trong spec nói rằng các bạn là hoàn toàn miễn phí để nghiên cứu băm chức năng về những gì là một số của các hàm băm nhanh hơn chạy qua những điều như miễn là bạn trích dẫn mã. Vì vậy, một số người đã có đã tìm ra cách nhanh chóng làm cờ chính tả, về nhanh cách lưu trữ thông tin. Hoàn toàn vào bạn nếu bạn kẻ muốn chỉ cần đi mà, phải không? Hãy chắc chắn rằng bạn đang trích dẫn. Thách thức ở đây thực sự rằng chúng tôi đang cố gắng để kiểm tra là đảm bảo rằng bạn biết theo cách của bạn xung quanh con trỏ. Theo như bạn thực hiện hàm băm thực tế và đến với như toán học để làm điều đó, các bạn có thể nghiên cứu bất cứ điều gì phương pháp trực tuyến các bạn muốn. Yeah? 

Đung chúng tôi chỉ có thể trích dẫn bằng cách sử dụng các [Không nghe thấy]? 

Andi PENG: Yeah. Bạn chỉ có thể, trong bình luận của bạn, bạn có thể trích dẫn như thế, oh, lấy từ yada, yada, yada, hàm băm. Bất cứ ai có bất kỳ câu hỏi? Chúng tôi thực sự đi lướt thông qua phần ngày hôm nay. Tôi sẽ ở đây để trả lời câu hỏi là tốt. 

Ngoài ra, như tôi đã nói, văn phòng giờ đêm nay và ngày mai. Spec tuần này là thực sự siêu dễ dàng và siêu ngắn để đọc. Tôi sẽ đề nghị dùng một cái nhìn, chỉ đọc qua toàn bộ của nó. 

Và Zamyla thực sự đi bạn qua mỗi chức năng bạn cần phải thực hiện, và vì vậy nó rất, rất rõ ràng làm thế nào để làm tất cả mọi thứ. Chỉ cần chắc chắn rằng bạn đang theo dõi các con trỏ. Đây là một pset rất khó khăn. 

Nó không phải thách thức bởi vì như thế, oh, các khái niệm là còn nhiều hơn nữa khó khăn, hoặc bạn phải học rất nhiều cú pháp mới đường mà bạn đã làm cho pset cuối cùng. Pset này là khó khăn vì có rất nhiều con trỏ, và sau đó nó rất, rất dễ dàng để một lần bạn có một lỗi trong mã của bạn không thể để tìm nơi mà lỗi đó là. 

Và để hoàn thành và niềm tin hoàn toàn vào bạn chàng trai để có thể đánh bại chúng tôi [không nghe] cách viết. Tôi thực sự không có bất kỳ mỏ bằng văn bản chưa, nhưng tôi sắp viết của tôi. Vì vậy, trong khi bạn đang viết của bạn, tôi sẽ viết tôi. Tôi sẽ cố gắng làm cho tôi nhanh hơn của bạn. Chúng tôi sẽ xem ai có một cách nhanh nhất. 

Và vâng, tôi sẽ thấy tất cả các bạn ở đây vào thứ ba. Tôi sẽ chạy một loại giống như một hội thảo pset. Tất cả các bộ phận này tuần là hội thảo pset, vậy các bạn có nhiều cơ hội giúp đỡ, giờ làm việc như mọi khi, và tôi thực sự mong muốn đọc tất cả các mã guys của bạn '. Tôi có câu đố lên đây nếu bạn kẻ muốn đến được những người. Đó là tất cả.