[MUSIC CHƠI]
SPEAKER 1: Tất cả các bên phải.
Tất cả mọi người chào đón trở lại phần.
Tôi hy vọng tất cả các bạn thành công thu hồi từ bài kiểm tra của bạn
từ tuần trước.
Tôi biết đó là một chút điên ở lần.
Như tôi đã nói trước đây, nếu bạn trong độ lệch chuẩn,
không thực sự lo lắng về nó, đặc biệt là cho một phần không thoải mái.
Đó là về nơi mà bạn nên có.
>> Nếu bạn đã làm rất tốt, sau đó tuyệt vời.
Thanh danh cho bạn.
Và nếu bạn cảm thấy như bạn cần một chút giúp đỡ thêm, xin vui lòng
cảm thấy tự do để đạt được ra bất kỳ của TF.
Chúng tôi là tất cả ở đây để giúp đỡ.
>> Đó là lý do tại sao chúng tôi dạy.
Đó là lý do tại sao tôi ở đây mỗi thứ Hai cho bạn guys và tại văn phòng giờ ngày thứ năm.
Vì vậy, xin vui lòng cho tôi biết nếu bạn đang lo lắng về bất cứ điều gì
hoặc nếu có bất cứ điều gì về các bài kiểm tra mà bạn thực sự muốn giải quyết.
>> Vì vậy, chương trình nghị sự cho ngày hôm nay là tất cả về cấu trúc dữ liệu.
Một số được chỉ có được chỉ để giúp bạn làm quen với các.
Bạn có thể không bao giờ thực hiện họ trong lớp học này.
Một số người bạn sẽ, như cho pset Speller của bạn.
>> Bạn sẽ có sự lựa chọn của bạn giữa các bảng băm và cố gắng.
Vì vậy, chúng tôi chắc chắn sẽ được đi trên những người.
Nó sẽ là chắc chắn hơn các loại của một bộ phận cao cấp hiện nay, mặc dù,
bởi vì có rất nhiều trong số họ, và nếu chúng tôi đã đi vào các chi tiết thực hiện
trên tất cả trong số này, chúng ta sẽ không thậm chí có được thông qua danh sách liên kết
và có lẽ một chút của bảng băm.
>> Vì vậy, chịu với tôi.
Chúng tôi sẽ không được làm càng nhiều mã hóa thời gian này.
Nếu bạn có bất kỳ câu hỏi về nó hoặc bạn muốn nhìn thấy nó thực hiện
hoặc thử nó cho chính mình, Tôi chắc chắn khuyên
sẽ study.cs50.net, mà có các ví dụ của tất cả các.
Nó sẽ có PowerPoints của tôi với các ghi chú mà chúng tôi
xu hướng sử dụng cũng như một số chương trình bài tập, đặc biệt là cho những thứ
như danh sách liên kết và nhị phân cây ngăn xếp và tín hiệu.
Vì vậy, ít mức độ cao hơn, có thể được tốt đẹp cho các bạn.
>> Vì vậy, với điều đó, chúng tôi sẽ bắt đầu.
Và cũng có thể, câu đố yes--.
Tôi nghĩ rằng hầu hết bạn của những người trong phần của tôi có câu đố của bạn,
nhưng có ai đến ở hoặc một số lý do bạn không làm, họ đang phải ở đây ở phía trước.
>> Vì vậy, danh sách liên kết.
Tôi biết điều này loại đi để sao lưu trước khi bài kiểm tra của bạn.
Đó là tuần trước rằng chúng ta học về việc này.
Nhưng trong trường hợp này, chúng tôi sẽ chỉ đi thêm một chút chiều sâu.
>> Vì vậy, tại sao chúng ta có thể chọn một danh sách liên kết trên một mảng?
Điều gì phân biệt chúng?
Có?
>> Đung Bạn có thể mở rộng một liên kết liệt kê so với kích thước cố định của một mảng.
SPEAKER 1: Đúng vậy.
Một mảng có kích thước cố định trong khi một danh sách liên kết có kích thước biến.
Vì vậy, nếu chúng ta không biết làm thế nào nhiều chúng tôi muốn lưu trữ,
một danh sách liên kết cho chúng ta một lớn cách để làm điều đó bởi vì chúng ta có thể chỉ
thêm vào một nút khác và thêm vào một nút và thêm vào một nút khác.
Nhưng những gì có thể là một thương mại-off?
Có ai nhớ thương mại-off giữa các mảng và danh sách liên kết?
Mmhmm?
>> Đung Bạn phải đi qua tất cả các cách
thông qua danh sách liên kết tìm một phần tử trong một danh sách.
Trong một mảng, bạn có thể chỉ cần tìm một phần tử.
>> SPEAKER 1: Đúng vậy.
Vì vậy, với arrays--
>> Đung [không nghe được].
>> SPEAKER 1: Với mảng, chúng ta có những gì được gọi là truy cập ngẫu nhiên.
Có nghĩa là nếu chúng ta muốn là những gì từng điểm thứ năm của một danh sách
hoặc điểm thứ năm của chúng tôi mảng, chúng ta chỉ có thể lấy nó.
Nếu đó là một danh sách liên kết, chúng tôi có để lặp qua, phải không?
Vì vậy, truy cập vào một yếu tố trong một mảng là hằng số thời gian,
trong khi với một danh sách liên kết nó sẽ rất có thể là thời gian tuyến tính bởi vì có lẽ
yếu tố của chúng tôi là tất cả các cách ở cuối.
Chúng ta phải tìm kiếm thông qua tất cả mọi thứ.
Vì vậy, với tất cả những dữ liệu này cấu trúc chúng ta sẽ
được chi tiêu một ít thời gian hơn vào, những ưu điểm và khuyết điểm là gì.
Khi chúng ta có thể muốn sử dụng một trong khác không?
Và đó là loại của điều lớn hơn để lấy đi.
>> Vì vậy, chúng tôi có ở đây định nghĩa của một nút.
Nó giống như một phần tử trong danh sách liên kết của chúng tôi, phải không?
Vì vậy, chúng ta đều quen thuộc với cấu trúc typedef của chúng tôi,
mà chúng tôi đã đi qua trong việc xem xét thời gian qua.
Đó là về cơ bản chỉ tạo một loại dữ liệu mà chúng ta có thể sử dụng.
>> Và trong trường hợp này, đó là một số nút rằng sẽ tổ chức một số nguyên trong.
Và sau đó phần thứ hai là những gì ở đây?
Bất cứ ai?
>> Đung [không nghe được].
>> SPEAKER 1: Yeah.
Đó là một con trỏ đến nút tiếp theo.
Vì vậy, đây thực sự cần được lên đây.
Đây là một con trỏ kiểu nút để điều tiếp theo.
Và đó là những gì họ bao gồm các nút của chúng tôi.
Cool.
>> Tất cả các bên phải, như vậy với tìm kiếm, như chúng tôi đã chỉ cần nói trước mặt, nếu bạn
sẽ tìm kiếm thông qua, bạn phải thực sự lặp đi lặp lại
thông qua danh sách liên kết của bạn.
Vì vậy, nếu chúng tôi đang tìm kiếm các số 9, chúng tôi sẽ bắt đầu vào đầu của chúng tôi
và chỉ cho chúng ta ngay từ đầu của danh sách liên kết của chúng tôi, phải không?
Và chúng ta nói, OK, thực hiện điều này nút chứa số 9?
Không có?
>> Tất cả các bên phải, đi đến kế tiếp.
Thực hiện theo nó.
Liệu nó có chứa số 9?
Không.
Thực hiện theo các kế tiếp.
>> Vì vậy, chúng ta phải thực sự lặp đi lặp lại thông qua danh sách liên kết của chúng tôi.
Chúng ta không thể đi trực tiếp vào nơi 9 là.
Và nếu các bạn thực sự muốn thấy một số mã giả trên đó.
Chúng tôi có một số chức năng tìm kiếm ở đây mà có in-- những gì nó có trong?
Bạn nghĩ gì?
Vì vậy, dễ dàng một.
Này là gì?
Đung [không nghe được].
SPEAKER 1: Số lượng chúng tôi đang tìm kiếm.
Phải không?
Và điều này sẽ tương ứng với?
Đó là một con trỏ đến?
>> Đung A node.
>> SPEAKER 1: Một nút vào danh sách mà chúng ta đang nhìn vào, phải không?
Vì vậy, chúng tôi có một số nút là con trỏ ở đây.
Đây là một điểm đó là sẽ thực sự lặp thông qua danh sách của chúng tôi.
Chúng tôi thiết lập nó bằng danh sách bởi vì đó chỉ
thiết lập nó bằng với bắt đầu của danh sách liên kết của chúng tôi.
>> Và trong khi nó không phải là NULL, trong khi chúng tôi vẫn có những thứ trong danh sách của chúng tôi,
kiểm tra xem nút đó có số lượng chúng tôi đang tìm kiếm.
Return true.
Nếu không, cập nhật nó, phải không?
>> Nếu nó là NULL, chúng ta thoát khỏi chúng tôi trong khi vòng lặp và trả về false
bởi vì đó có nghĩa là chúng tôi đã không tìm thấy nó.
Có tất cả mọi người có được như thế nào mà làm việc?
OK.
>> Vì vậy, với chèn, bạn có ba cách khác nhau.
Bạn có thể thêm vào trước, bạn có thể thêm và bạn có thể chèn vào cả mọi loại.
Trong trường hợp này, chúng tôi sẽ làm một thêm vào trước.
Có ai biết làm thế nào những ba trường hợp có thể khác nhau?
>> Vì vậy, thêm vào trước có nghĩa là bạn đặt nó ở phía trước của danh sách của bạn.
Vì vậy, điều đó có nghĩa rằng không có vấn đề những gì nút của bạn, không có vấn đề
những gì giá trị là, bạn sẽ để đặt nó ở đây ở phía trước, OK?
Nó sẽ là người đầu tiên phần tử trong danh sách của bạn.
>> Nếu bạn thêm nó, nó sẽ để đi đến trở lại danh sách của bạn.
Và chèn vào cả mọi loại có nghĩa là bạn sẽ đặt thực sự vào nơi
nơi nó giữ danh sách liên kết của bạn được sắp xếp.
Một lần nữa, làm thế nào bạn sử dụng những người và khi bạn sử dụng
họ sẽ thay đổi tùy thuộc vào trường hợp của bạn.
Nếu nó không cần phải được sắp xếp, thêm vào trước có xu hướng
là những gì hầu hết mọi người sử dụng bởi vì bạn không
phải đi qua toàn bộ danh sách để tìm kết thúc để thêm nó vào, đúng không?
Bạn chỉ có thể dính nó ngay.
>> Vì vậy, chúng ta sẽ đi qua một chèn 1 ngay bây giờ.
Vì vậy, có một điều mà tôi sẽ khuyên trên pset này
là để rút ra những điều trên, như mọi khi.
Nó rất quan trọng là bạn cập nhật con trỏ của bạn theo thứ tự đúng
bởi vì nếu bạn cập nhật chúng hơi trong trật tự,
bạn sẽ kết thúc mất phần danh sách của bạn.
>> Vì vậy, ví dụ, trong trường hợp này, chúng tôi nói với người đứng đầu để chỉ điểm cho 1.
Nếu chúng ta chỉ làm điều đó mà không cần tiết kiệm 1 này,
chúng tôi không có ý tưởng gì 1 nên chỉ đến nay
bởi vì chúng ta đã mất những gì người đứng đầu chỉ ra.
Vì vậy, một điều cần nhớ khi bạn đang làm một thêm vào trước
là để tiết kiệm những gì điểm đầu đến đầu tiên,
sau đó gán lại nó, và sau đó cập nhật những nút mới của bạn sẽ trỏ đến.
Trong trường hợp này, đây là một cách để làm điều đó.
>> Vì vậy, nếu chúng tôi đã thực hiện nó theo cách này nơi chúng tôi chỉ bố trí đầu,
chúng ta mất đi cơ bản của chúng tôi toàn bộ danh sách, phải không?
Một cách để làm điều đó là có 1 điểm tiếp theo, và sau đó có điểm đầu đến 1.
Hoặc bạn có thể làm giống như các lưu trữ tạm thời, mà tôi nói chuyện về.
>> Nhưng chuyển nhượng của bạn con trỏ theo thứ tự đúng
sẽ là rất, rất quan trọng đối với pset này.
Nếu không, bạn sẽ có một băm bảng hoặc một thử đó là chỉ cần đi để được
chỉ là một phần của những từ mà bạn muốn và sau đó mmhmm you're--?
Đung gì là tạm thời điều lưu trữ mà bạn đã nói về?
SPEAKER 1: lưu trữ tạm thời.
Vì vậy, về cơ bản khác cách bạn có thể làm điều này
được lưu trữ đầu của một cái gì đó, như lưu trữ nó biến tạm thời.
Gán cho nó 1 và sau đó cập nhật 1 điểm
để bất cứ điều gì đầu sử dụng để trỏ đến.
Bằng cách này là rõ ràng thanh lịch hơn bởi vì bạn
không cần phải có giá trị tạm thời, nhưng chỉ cần cung cấp một cách khác để làm điều đó.
Và chúng tôi thực sự không có một số mã cho việc này.
Vì vậy, danh sách liên kết, chúng tôi thực sự có một số mã.
Vì vậy, chèn ở đây, điều này được thêm vào trước.
Vì vậy, đây vào nó ở đầu.
>> Vì vậy, điều đầu tiên, bạn cần phải tạo nút mới của bạn, tất nhiên,
và kiểm tra NULL.
Luôn luôn tốt.
Và sau đó bạn cần phải gán các giá trị.
Bất cứ khi nào bạn tạo một nút mới, bạn không biết những gì nó đang trỏ đến tiếp theo,
do đó bạn muốn khởi tạo nó để NULL.
Nếu nó kết thúc chỉ vào một cái gì đó khác, nó được bố trí và điều đó là tốt.
Nếu đó là điều đầu tiên trong danh sách, nó cần
để trỏ đến NULL vì đó là cuối danh sách.
>> Vì vậy, sau đó chèn nó, chúng ta thấy ở đây chúng tôi được gán giá trị tiếp theo của nút của chúng tôi
là bất cứ điều gì đầu là, đó là những gì chúng tôi có ở đây.
Đó là những gì chúng ta đã làm.
Và sau đó chúng ta đang gán đầu đến điểm đến nút mới của chúng tôi, vì nhớ,
mới là một con trỏ tới một nút, và đó chính xác là những gì đầu.
Đó chính là lý do tại sao chúng tôi có mũi tên này accessor.
Mát mẻ?
Mmhmm?
>> Đung Chúng ta phải khởi tạo mới tiếp theo để NULL đầu tiên,
hoặc có thể chúng ta chỉ cần khởi tạo nó để đi?
>> SPEAKER 1: New tiếp theo cần phải được NULL để bắt đầu
bởi vì bạn không biết nơi mà nó có được.
Ngoài ra, đây là loại giống như một mô hình.
Bạn đặt nó bằng NULL chỉ để làm cho chắc chắn rằng tất cả các căn cứ của bạn được bảo hiểm
trước khi bạn làm bất cứ giao lại để bạn luôn được đảm bảo rằng nó sẽ
được trỏ đến một giá trị cụ thể so với giống như một giá trị rác.
Bởi vì, yeah, chúng ta gán mới tiếp theo tự động,
nhưng đó là giống như một thực hành tốt để khởi tạo nó
theo cách đó và sau đó phân công lại.
>> OK, vì vậy gấp đôi danh sách liên kết bây giờ.
Chúng ta nghĩ gì?
Có gì khác nhau với gấp đôi danh sách liên kết?
>> Vì vậy, trong danh sách liên kết của chúng tôi, chúng tôi có thể chỉ di chuyển theo một hướng, phải không?
Chúng tôi chỉ có tiếp theo.
Chúng tôi chỉ có thể đi tiếp.
>> Với một danh sách gấp đôi liên kết, chúng tôi cũng có thể di chuyển về phía sau.
Vì vậy, chúng tôi không chỉ có những số mà chúng ta muốn lưu trữ,
chúng tôi có nơi nó trỏ tới tiếp theo và chúng ta chỉ đến từ.
Vì vậy, điều này cho phép một số traversal tốt hơn.
>> Vì vậy, gấp đôi các nút liên kết, rất giống nhau, phải không?
Chỉ có khác biệt bây giờ là chúng tôi có một kế tiếp và trước đó.
Đó là khác biệt duy nhất.
>> Vì vậy, nếu chúng ta thêm vào trước hoặc append-- chúng tôi không có bất kỳ mã này lên here--
nhưng nếu bạn đã cố gắng và chèn nó, điều quan trọng
là bạn cần phải thực hiện chắc chắn rằng bạn đang gán
cả hai trước đó của bạn và của bạn con trỏ tới một cách chính xác.
Vì vậy, trong trường hợp này, bạn sẽ không chỉ khởi tạo tiếp theo,
bạn khởi tạo trước đó.
Nếu chúng ta đang ở đầu của danh sách, chúng tôi sẽ không chỉ làm đầu bằng mới,
nhưng nên trước mới của chúng tôi chỉ vào đầu, phải không?
>> Đó là khác biệt duy nhất.
Và nếu bạn muốn thực hành nhiều hơn với những việc này với danh sách liên kết, với chèn,
với xóa, với chèn vào một danh sách các loại,
xin vui lòng kiểm tra study.cs50.net.
Có một loạt các bài tập tuyệt vời.
Tôi khuyên họ.
Tôi muốn chúng tôi có thời gian để đi qua chúng nhưng có rất nhiều cấu trúc dữ liệu
để có được thông qua.
>> OK, vì vậy các bảng băm.
Đây có lẽ là nhất bit hữu ích cho pset của bạn
ở đây bởi vì bạn sẽ được thực hiện một trong những, hoặc một thử.
Tôi thực sự thích các bảng băm.
Họ đang khá mát mẻ.
>> Vì vậy, về cơ bản những gì xảy ra là một bảng băm
là khi chúng ta thực sự cần nhanh chóng chèn, xóa, và tra cứu.
Đó là những điều mà chúng tôi ưu tiên trong một bảng băm.
Họ có thể nhận được khá lớn, nhưng như chúng ta sẽ thấy có cố gắng,
có những điều lớn hơn nhiều.
>> Nhưng về cơ bản, tất cả băm bảng là một hàm băm
mà nói với bạn mà xô để đưa từng dữ liệu của bạn, mỗi yếu tố của bạn trong.
Một cách đơn giản để nghĩ về một bảng băm là nó chỉ là xô của sự vật,
phải không?
Vì vậy, khi bạn đang sắp xếp mọi thứ bằng như chữ cái đầu tiên của tên của họ,
đó là loại giống như một bảng băm.
>> Vì vậy, nếu tôi được nhóm các bạn là thành các nhóm của bất cứ ai tên bắt đầu
với A trên đây, hoặc bất cứ ai sinh nhật là là vào tháng Giêng, tháng Hai, tháng Ba,
bất cứ điều gì, đó là hiệu quả tạo ra một bảng băm.
Nó chỉ tạo ra xô đó bạn sắp xếp các yếu tố của bạn thành
để bạn có thể tìm thấy chúng dễ dàng hơn.
Vì vậy, cách này khi tôi cần để tìm một trong các bạn,
Tôi không phải tìm kiếm qua từng tên của bạn.
Tôi có thể được như thế, oh, tôi biết rằng Sinh nhật của Danielle là in--
Đung --April.
SPEAKER 1: Tháng Tư.
Vì vậy, tôi tìm vào tháng Tư của tôi xô, và với bất kỳ may mắn,
cô ấy sẽ là người duy nhất trong đó và thời gian của tôi là không đổi trong ý nghĩa đó,
trong khi đó nếu tôi phải nhìn thông qua một bó toàn bộ người dân,
nó sẽ mất nhiều thời gian hơn nhiều.
Vì vậy, bảng băm thực sự chỉ là xô.
Cách dễ dàng để nghĩ về họ.
>> Vì vậy, một điều rất quan trọng về một bảng băm là một hàm băm.
Vì vậy, những điều tôi vừa nói đến, như chữ cái đầu tiên của tên đầu tiên của bạn
hoặc tháng sinh nhật của bạn, đây là những ý tưởng mà
thực sự tương quan đến một hàm băm.
Nó chỉ là một cách để quyết định xô bạn yếu tố đang đi vào, OK?
Vì vậy, cho pset này, bạn có thể tìm kiếm khá nhiều bất kỳ chức năng hash bạn muốn.
>> Không phải là của riêng bạn.
Có một số những người thực sự mát mẻ có mà làm tất cả các loại của toán học điên.
Và nếu bạn muốn làm cho bạn kiểm tra chính tả siêu nhanh,
Tôi sẽ chắc chắn nhìn vào một trong những.
>> Nhưng đó cũng là những cái đơn giản, giống như tính toán
tổng của các từ, như mỗi chữ cái có một số.
Tính toán tổng.
Xác định xô.
Họ cũng có những người dễ dàng mà cũng giống như tất cả các của A ở đây,
tất cả các B ở đây.
Bất kỳ một trong những người.
>> Về cơ bản, nó chỉ cho bạn biết mảng chỉ số phần tử của bạn nên đi vào.
Chỉ cần quyết định bucket-- đó là tất cả một hàm băm là.
Vì vậy, ở đây chúng ta có một ví dụ đó là chỉ là chữ cái đầu tiên của chuỗi
rằng tôi đã chỉ nói về.
>> Vì vậy, bạn có một số hash đó chỉ là chữ cái đầu tiên của chuỗi trừ của bạn A,
mà sẽ cung cấp cho bạn một số số giữa 0 và 25.
Và những gì bạn muốn làm là chắc chắn rằng điều này thể hiện
kích thước của hash của bạn table-- bao nhiêu xô có.
Với rất nhiều các hàm băm, họ
sẽ được trả về giá trị mà có thể được xa trên số xô
mà bạn thực sự có trong bảng băm của bạn,
vì vậy bạn cần phải thực hiện chắc chắn và mod bởi những người.
Nếu không, nó sẽ nói, oh, nó phải ở trong thùng 5000
nhưng bạn chỉ có 30 xô trong bảng băm của bạn.
Và tất nhiên, chúng ta đều biết đó là sẽ dẫn đến một số lỗi điên.
Vì vậy, hãy chắc chắn để mod bởi các Kích thước của bảng băm của bạn.
Cool.
Vì vậy, va chạm.
Là tất cả mọi người tốt cho đến nay?
Mmhmm?
>> Đung Tại sao nó trả lại một giá trị lớn như vậy?
>> SPEAKER 1: Tùy thuộc vào các thuật toán rằng hàm băm của bạn sử dụng.
Một số trong số họ sẽ làm nhân điên.
Và đó là tất cả về nhận một phân bố,
do đó, họ làm một số thực sự đôi khi những điều điên rồ.
Đó là tất cả.
Bất cứ điều gì khác?
OK.
>> Vì vậy, va chạm.
Về cơ bản, như tôi đã nói trước đó, trong trường hợp kịch bản tốt nhất,
bất kỳ xô tôi nhìn vào là sẽ có một điều,
vì vậy tôi không cần phải xem xét tất cả, phải không?
Tôi có thể biết nó có hay nó không, và đó là những gì chúng ta thực sự muốn.
Nhưng nếu chúng ta có hàng chục ngàn điểm dữ liệu và ít hơn con số đó
xô, chúng ta sẽ có va chạm nơi cuối cùng một cái gì đó
là sẽ phải kết thúc trong một thùng đó đã có một phần tử.
>> Vì vậy, câu hỏi là, những gì Chúng ta phải làm trong trường hợp đó?
Chúng tôi làm gì?
Chúng tôi đã có một cái gì đó?
Chúng ta chỉ cần ném nó ra?
>> Không.
Chúng tôi phải giữ cả hai.
Vì vậy, cách mà chúng ta thường làm điều đó là gì?
Cấu trúc dữ liệu là gì chúng tôi chỉ nói chuyện về?
Đung danh sách liên kết.
SPEAKER 1: Một danh sách liên kết.
Vì vậy, bây giờ, thay vì mỗi người trong các xô chỉ có một yếu tố,
nó sẽ chứa một danh sách liên kết các yếu tố đó đã băm vào nó.
OK, tất cả mọi người không loại có được ý tưởng đó?
Bởi vì chúng ta không thể có một mảng bởi vì chúng ta không biết bao nhiêu điều
đang có được trong đó.
Một danh sách liên kết cho phép chúng tôi có chỉ số chính xác mà
được băm vào thùng đó, phải không?
>> Vì vậy, tuyến tính thăm dò là về cơ bản idea-- này
nó là một cách để đối phó với một vụ va chạm.
Những gì bạn có thể làm là nếu, trong này trường hợp, berry được băm vào 1
và chúng tôi đã có một cái gì đó, bạn chỉ cần
tiếp tục đi xuống cho đến khi bạn tìm thấy một khe trống.
Đó là một cách để xử lý nó.
Một cách khác để xử lý đó là với những gì chúng ta chỉ
called-- các liên kết danh sách được gọi là loạt.
>> Vì vậy, ý tưởng này hoạt động nếu bảng băm của bạn, bạn nghĩ
là lớn hơn nhiều so với dữ liệu của bạn thiết lập hoặc nếu bạn
muốn thử và giảm thiểu chaining cho đến khi nó hoàn toàn cần thiết.
Vì vậy, có một điều tuyến tính thăm dò rõ ràng có nghĩa
rằng hàm băm của bạn không phải là khá hữu ích
bởi vì bạn sẽ kết thúc bằng cách sử dụng hàm băm của bạn, nhận được đến một điểm,
bạn tuyến tính thăm dò xuống một số nơi có sẵn.
Nhưng bây giờ, tất nhiên, bất cứ điều gì khác mà kết thúc ở đó,
bạn sẽ phải tìm kiếm thậm chí còn tiếp tục xuống.
>> Và có rất nhiều chi phí tìm kiếm
đi vào nhập vào một yếu tố trong bảng băm của bạn bây giờ, phải không?
Và bây giờ khi bạn đi và cố gắng và tìm thấy berry một lần nữa, bạn sẽ băm nó,
và nó sẽ nói, oh, nhìn trong thùng 1,
và nó sẽ không được trong thùng 1, vì vậy bạn
sẽ phải đi qua thông qua phần còn lại của các.
Vì vậy, nó là đôi khi hữu ích, nhưng trong nhiều trường hợp,
chúng ta sẽ nói rằng chaining là những gì bạn muốn làm.
>> Vì vậy, chúng ta đã nói về điều này trước đó.
Tôi có một chút trước của bản thân mình.
Nhưng xâu chuỗi là cơ bản mà mỗi thùng trong bảng băm của bạn
chỉ là một danh sách liên kết.
>> Vì vậy, một cách khác, hoặc kỹ thuật hơn cách, suy nghĩ của một bảng băm
là nó chỉ là một mảng của danh sách liên kết, mà
khi bạn đang viết từ điển của bạn và bạn đang cố gắng để tải nó,
suy nghĩ về nó như một mảng các danh sách liên kết
sẽ làm cho nó dễ dàng hơn nhiều để bạn có thể khởi tạo.
>> Đung Vì vậy, bảng băm có kích thước định trước,
giống như một [không nghe được] xô?
>> SPEAKER 1: Đúng vậy.
Vì vậy, nó có một số thiết lập của nhóm bạn determine--
mà các bạn nên cảm thấy tự do để chơi với.
Nó có thể là khá mát mẻ để xem những gì sẽ xảy ra
khi bạn thay đổi số của bạn xô.
Nhưng yeah, nó có một thiết lập số xô.
Những gì cho phép bạn để phù hợp như nhiều yếu tố như bạn cần
là xâu chuỗi riêng biệt này, nơi bạn có danh sách liên kết trong mỗi nhóm.
Điều đó có nghĩa bảng băm của bạn sẽ được chính xác kích thước
mà bạn cần nó được, phải không?
Đó là toàn bộ điểm của danh sách liên kết.
Cool.
>> Vì vậy, tất cả mọi người có OK?
Được rồi.
Ah.
Chuyện gì vừa xảy ra?
Thực sự bây giờ.
Đoán ai đó giết chết tôi.
>> OK chúng ta sẽ đi vào cố gắng, đó là một chút điên rồ.
Tôi thích các bảng băm.
Tôi nghĩ rằng họ đang thực sự mát mẻ.
Cố gắng là mát mẻ, quá.
>> Vì vậy, không ai nhớ những gì một thử là?
Bạn nên đã đi qua nó ngắn gọn trong bài giảng?
Bạn có nhớ loại làm thế nào nó hoạt động?
Đung Tôi chỉ gật đầu rằng chúng tôi đã đi qua nó.
SPEAKER 1: Chúng tôi đi qua nó.
OK, chúng tôi đang thực sự sẽ đi hơn nó bây giờ là những gì chúng ta đang nói.
>> Đung Đó là một cây hồi.
>> SPEAKER 1: Yeah.
Đó là một cây hồi.
Tuyệt vời.
Vì vậy, một điều cần chú ý ở đây là chúng tôi đang xem xét đặc điểm cá nhân
ở đây, phải không?
>> Vì vậy, trước khi với hàm băm của chúng tôi, chúng tôi đang tìm kiếm tại các từ như một toàn thể,
và bây giờ chúng tôi đang tìm kiếm nhiều hơn tại các nhân vật, phải không?
Vì vậy, chúng tôi có Maxwell trên đây và Mendel.
Vì vậy, về cơ bản một try-- một cách để suy nghĩ về việc này là tất cả các cấp ở đây
là một mảng của các chữ cái.
Vì vậy, đây là nút gốc của bạn ở đây, phải không?
Điều này có tất cả các ký tự của bảng chữ cái cho sự bắt đầu của mỗi từ.
>> Và những gì bạn muốn làm là nói, OK, chúng tôi có một số M từ.
Chúng tôi sẽ tìm kiếm Maxwell, vì vậy chúng tôi đi đến M. Và M điểm để toàn bộ
một mảng khác, nơi mọi từ, miễn là có
là một từ có A là lá thư thứ hai,
miễn là có là một từ mà có B là lá thư thứ hai,
nó sẽ có một con trỏ đi đến một số mảng tới.
>> Có lẽ không phải là một từ đó MP một cái gì đó,
để ở vị trí P trong này mảng, nó sẽ chỉ được NULL.
Nó sẽ nói, OK, không có từ M đã theo sau là một P, OK?
Vì vậy, nếu chúng ta nghĩ về nó, mỗi một trong những điều nhỏ
thực sự là một trong những mảng lớn từ A đến Z.
Vì vậy, những gì có thể là một trong những điều đó là loại một nhược điểm của một thử?
>> Đung A rất nhiều bộ nhớ.
>> SPEAKER 1: Đó là một tấn của bộ nhớ, phải không?
Mỗi một trong những khối ở đây đại diện cho 26 không gian, 26 mảng yếu tố.
Vì vậy, cố gắng có được không gian vô cùng nặng nề.
>> Nhưng họ rất nhanh.
Vì vậy, cực kỳ nhanh chóng nhưng không gian thực sự không hiệu quả.
Loại phải tìm ra cái nào bạn muốn.
Đây là thực sự mát mẻ cho pset của bạn, nhưng họ làm mất rất nhiều bộ nhớ,
vì vậy bạn đánh đổi.
Yeah?
>> Đung Nó sẽ có thể để thiết lập một thử và sau đó
một khi bạn có tất cả các dữ liệu trong nó mà bạn need--
Tôi không biết nếu điều đó sẽ có ý nghĩa.
Tôi đã nhận được thoát khỏi tất cả các NULL ký tự, nhưng sau đó
bạn sẽ không có khả năng chỉ số them--
>> SPEAKER 1: Bạn vẫn cần họ.
>> Đung - theo cùng một cách mỗi lần.
SPEAKER 1: Yeah.
Bạn cần các nhân vật NULL để cho Bạn có biết nếu không có một từ đó.
Bạn Ben đã có một cái gì đó bạn muốn?
OK.
Tất cả các bên phải, vì vậy chúng ta sẽ đi hơn một chút
vào chi tiết kỹ thuật đằng sau một cố gắng và làm việc thông qua một ví dụ.
>> OK, vì vậy đây là điều tương tự.
Trong khi đó, trong một danh sách liên kết, chính chúng tôi loại of-- từ tôi muốn là những gì? -
như xây dựng khối là một nút.
Trong một cố gắng, chúng tôi cũng có một nút, nhưng nó được định nghĩa khác nhau.
>> Vì vậy, chúng tôi có một số bool mà đại diện cho dù một từ thực sự
tồn tại ở vị trí này, và sau đó chúng tôi có một số mảng here-- hay đúng hơn,
đây là một con trỏ đến một mảng 27 ký tự.
Và đây là cho, trong trường hợp này, điều này 27-- tôi chắc chắn rằng tất cả các bạn là như thế, chờ đợi,
có 26 chữ cái trong bảng chữ cái.
Tại sao chúng ta có 27?
>> Vì vậy, tùy thuộc vào cách bạn thực hiện điều này,
này là từ một pset đó cho phép dấu nháy.
Vì vậy, đó là lý do tại sao một trong những phụ.
Bạn cũng sẽ có trong một số trường hợp terminator rỗng
được bao gồm như là một trong những các ký tự mà nó được phép có,
và đó là cách họ kiểm tra xem nếu nó là sự kết thúc của từ này.
Nếu bạn quan tâm, hãy kiểm tra Video Kevin trên study.cs50,
cũng như Wikipedia có một số nguồn tài nguyên tốt ở đó.
>> Nhưng chúng ta sẽ đi qua chỉ loại làm thế nào bạn có thể làm việc thông qua một thử
nếu bạn đang đưa ra một.
Vì vậy, chúng tôi có một siêu đơn giản ở đây mà có các từ "dơi" và "zoom" trong đó.
Và như chúng ta thấy ở đây, không gian nhỏ bé này ở đây
đại diện bool của chúng tôi nói, vâng, đây là một từ.
Và sau đó điều này có của chúng tôi mảng của các nhân vật, phải không?
>> Vì vậy, chúng ta sẽ đi qua tìm kiếm "bat" trong thử này.
Vì vậy, bắt đầu ở đầu, phải không?
Và chúng ta biết rằng b tương ứng với chỉ số thứ hai, yếu tố thứ hai
trong mảng này, bởi vì a và b.
Vì vậy, khoảng thứ hai.
>> Và nó nói, OK, mát mẻ, theo đó vào mảng tiếp theo, bởi vì nếu chúng ta nhớ,
nó không phải là mỗi một trong các thực sự có chứa nguyên tố này.
Mỗi một trong những mảng chứa một con trỏ, phải không?
Đây là một khác biệt quan trọng để thực hiện.
>> Tôi biết điều này sẽ cố gắng là be-- thực sự khó khăn để có được vào thời gian đầu tiên,
vì vậy ngay cả nếu điều này là lần thứ hai hoặc thứ ba
và nó vẫn còn loại của vẻ khó khăn,
Tôi hứa nếu bạn đi xem ngày mai ngắn một lần nữa,
nó có thể sẽ có ý nghĩa hơn rất nhiều.
Phải mất rất nhiều để tiêu hóa.
Tôi vẫn còn đôi khi là như thế, chờ đợi, một thử là gì?
Làm thế nào để sử dụng này?
>> Vì vậy, chúng tôi có b trong trường hợp này, đó là chỉ số thứ hai của chúng tôi.
Nếu chúng ta có, nói, c hoặc d hoặc bất kỳ thư khác,
chúng ta cần phải bản đồ lại cho rằng chỉ số của mảng của chúng tôi rằng tương ứng với.
Vì vậy, chúng tôi sẽ có như rchar và chúng tôi chỉ trừ ra một bản đồ nó vào 0-25.
Mọi người đều tốt như thế nào chúng tôi bản đồ nhân vật của chúng tôi?
OK.
>> Vì vậy, chúng tôi đi đến thứ hai và chúng tôi thấy rằng, có, nó không phải là để NULL.
Chúng tôi có thể chuyển sang mảng tiếp theo này.
Vì vậy, chúng tôi đi vào mảng tiếp theo này ở đây.
>> Và chúng ta nói, OK, bây giờ chúng tôi cần phải xem một là ở đây.
Một là null hay không nó thực sự di chuyển về phía trước?
Vì vậy, một thực sự di chuyển chuyển tiếp trong mảng này.
Và chúng ta nói, OK, t là lá thư cuối cùng của chúng tôi.
Vì vậy, chúng tôi đi đến t ở các chỉ số.
Và sau đó chúng tôi di chuyển về phía trước bởi vì có một số khác.
Và điều này về cơ bản nói rằng, có, nó nói rằng đó là một từ here--
rằng nếu bạn làm theo điều này đường dẫn, bạn đã đến
tại một từ, mà chúng ta biết là "con dơi".
Có?
>> ĐỐI TƯỢNG: Có tiêu chuẩn để có mà như chỉ số 0 và sau đó có một loại 1
hoặc có ở cuối?
>> SPEAKER 1: No.
Vì vậy, nếu chúng ta nhìn lại chúng tôi khai ở đây, đó là một bool,
do đó, nó là yếu tố riêng của mình trong nút của bạn.
Vì vậy, nó không phải là một phần của mảng.
Cool.
Vì vậy, khi chúng tôi kết thúc từ của chúng tôi và chúng tôi ở mảng này, những gì chúng tôi muốn làm
là làm một kiểm tra cho là này một từ.
Và trong trường hợp này, nó sẽ trở lại có.
>> Vì vậy, trên lưu ý rằng, chúng ta biết rằng "sở thú" - chúng ta biết rằng con người là "sở thú" là một từ,
phải không?
Nhưng được thử ở đây sẽ nói, không, nó không phải.
Và nó sẽ nói rằng bởi vì chúng tôi đã không được chỉ định nó như là một lời ở đây.
Mặc dù chúng tôi có thể đi qua thông qua vào mảng này,
thử này có thể nói rằng, không có, vườn thú không phải là trong từ điển của bạn
bởi vì chúng tôi đã không được chỉ định nó như vậy.
>> Vì vậy, một cách để làm that-- oh, xin lỗi, cái này.
Vì vậy, trong trường hợp này, "sở thú" không phải là một từ, nhưng nó là trong thử của chúng tôi.
Nhưng trong vụ việc này, nói rằng chúng ta muốn nó giới thiệu từ "tắm", những gì xảy ra
là chúng tôi làm theo through-- b, a, t.
Chúng tôi đang ở trong mảng này, và chúng tôi đi để tìm kiếm h.
>> Trong trường hợp này, khi chúng ta nhìn vào con trỏ tại h,
nó trỏ đến NULL, OK?
Vì vậy, trừ khi đó là một cách rõ ràng trỏ đến mảng khác,
bạn cho rằng tất cả các con trỏ trong mảng này được trỏ đến null.
Vì vậy, trong trường hợp này, h đang trỏ null vì vậy chúng tôi không thể làm bất cứ điều gì,
vì vậy nó cũng sẽ quay trở lại sai lầm, "tắm" không phải là ở đây.
Vì vậy, bây giờ chúng tôi đang thực sự sẽ đi qua
làm sao chúng ta thực sự nói rằng "sở thú" là trong thử của chúng tôi.
Làm thế nào để chúng ta chèn "sở thú" thành thử chúng tôi?
Vì vậy, trong cùng một cách mà chúng tôi bắt đầu với danh sách liên kết của chúng tôi, chúng tôi bắt đầu từ gốc rễ.
Khi nghi ngờ, bắt đầu từ gốc rễ của những điều này.
>> Và chúng ta sẽ nói, OK, z.
z tồn tại trong này, và nó.
Vì vậy, bạn đang di chuyển trên để mảng tiếp theo của bạn, OK?
Và sau đó vào tiếp theo, chúng ta nói, OK, không o tồn tại?
Nó thực hiện.
Điều này một lần nữa.
>> Và như vậy tiếp theo của chúng tôi, chúng tôi đã nói, OK, "sở thú" đã tồn tại ở đây.
Tất cả chúng ta cần làm là thiết lập bằng này đúng sự thật, rằng có một từ đó.
Nếu bạn đã theo dõi tất cả mọi thứ đến trước thời điểm đó,
đó là một từ, vì vậy chỉ cần thiết lập nó bằng như vậy.
Có?
>> Đung Vì vậy, sau đó thực hiện điều đó có nghĩa là "ba" là một từ cũng?
>> SPEAKER 1: No.
Vì vậy, trong trường hợp này, "ba", chúng tôi sẽ nhận được ở đây, chúng ta sẽ nói nó là một từ,
và nó vẫn sẽ không có.
OK?
Mmhmm?
>> Đung Vì vậy, một khi bạn nó là một từ và bạn nói có, sau đó nó
sẽ chứa để đi đến m?
>> SPEAKER 1: Vì vậy, điều này đã làm with-- bạn đang tải này.
Bạn nói "sở thú" là một từ.
Khi bạn đi đến check-- như thế, nói rằng bạn muốn nói,
không "sở thú" tồn tại trong từ điển này?
Bạn sẽ chỉ tìm kiếm cho "vườn thú" và sau đó kiểm tra để xem nếu nó là một từ.
Bạn sẽ không bao giờ để di chuyển thông qua để m bởi vì đó không phải là
những gì bạn đang tìm kiếm.
>> Vì vậy, nếu chúng ta thực sự muốn thêm "tắm" vào thử này,
chúng tôi sẽ làm điều tương tự như chúng ta đã làm với "sở thú"
ngoại trừ chúng ta sẽ thấy rằng khi chúng ta thử và nhận được đến h, nó không tồn tại.
Vì vậy, bạn có thể nghĩ về điều này như cố gắng để thêm một nút mới vào một danh sách liên kết,
vì vậy chúng tôi sẽ cần phải thêm một một trong những mảng, như vậy.
Và sau đó những gì chúng tôi làm là chúng ta chỉ cần thiết lập h phần tử của mảng này chỉ vào này.
>> Và sau đó những gì chúng tôi muốn làm ở đây?
Thêm nó bằng đúng sự thật bởi vì nó là một từ.
Cool.
Tôi biết.
Cố gắng không phải là thú vị nhất.
Hãy tin tôi, tôi biết.
>> Vì vậy, một điều nhận ra có cố gắng, Tôi đã nói, họ đang rất hiệu quả.
Vì vậy, chúng tôi đã nhìn thấy họ mất một tấn của không gian.
Họ đang loại khó hiểu.
Vì vậy, tại sao chúng ta không bao giờ sử dụng những?
Chúng tôi sử dụng những vì họ vô cùng hiệu quả.
>> Vì vậy, nếu bạn đã bao giờ tìm kiếm lên một từ, bạn chỉ
giới hạn bởi chiều dài của từ này.
Vì vậy, nếu bạn đang tìm kiếm một từ đó là chiều dài của năm,
bạn chỉ bao giờ sẽ phải làm cho ít nhất năm so sánh, OK?
Vì vậy, nó làm cho nó về cơ bản là một hằng số.
Giống như chèn và tra cứu về cơ bản là hằng số thời gian.
>> Vì vậy, nếu bạn đã bao giờ có thể nhận được một cái gì đó trong thời gian liên tục,
đó là tốt như nó được.
Bạn không thể có được tốt hơn hằng số thời gian cho những việc này.
Vì vậy, đó là một trong những ưu điểm rất lớn của cố gắng.
>> Nhưng đó là rất nhiều không gian.
Vì vậy, bạn hẳn sẽ có những quyết định những gì quan trọng với bạn hơn.
Và trên các máy tính ngày nay, không gian mà một thử có thể mất
có lẽ không ảnh hưởng đến bạn rằng nhiều, nhưng có lẽ
bạn đang làm việc với một cái gì đó có những thứ xa, xa hơn,
và một thử chỉ là không hợp lý.
Có?
>> ĐỐI TƯỢNG: Chờ đợi, vì vậy bạn có 26 chữ cái trong mỗi một đơn?
>> SPEAKER 1: Mmhmm.
Yeah, bạn có 26.
Bạn có một số là đánh dấu từ và sau đó bạn có 26 con trỏ trong mỗi một.
Và họ đang point--
>> Đung Và mỗi 26, Họ từng có 26?
>> SPEAKER 1: Có.
Và đó là lý do tại sao, như bạn có thể thấy, nó mở rộng khá nhanh chóng.
Được rồi.
Vì vậy, chúng ta sẽ nhận được vào cây, Tôi cảm thấy thích được dễ dàng hơn và có thể sẽ
được hoãn thi hành án ít tốt đẹp từ cố gắng đó.
Vì vậy, hy vọng nhất của bạn đã thấy một cái cây trước.
Không giống như khá những người bên ngoài, mà tôi
không biết nếu bất cứ ai đi ngoài trời gần đây.
Tôi đi táo chọn cuối tuần này, và oh chúa ơi, nó thật đẹp.
Tôi không biết lá có thể nhìn thấy khá.
>> Vì vậy, đây chỉ là một cây, phải không?
Nó chỉ là một số nút, và nó chỉ ra một loạt các nút khác.
Như bạn thấy ở đây, đây là loại một chủ đề định kỳ.
Các nút trỏ đến nút là loại bản chất của nhiều cấu trúc dữ liệu.
Nó chỉ phụ thuộc vào cách chúng ta có chúng trỏ đến nhau
và làm thế nào chúng tôi đi qua thông qua họ và làm thế nào chúng ta
chèn những điều mà xác định đặc điểm khác nhau của họ.
>> Vì vậy, chỉ một số thuật ngữ, mà tôi đã sử dụng trước.
Vì vậy, gốc rễ là bất cứ điều gì là ở đầu.
đó là nơi chúng tôi luôn luôn bắt đầu.
Bạn có thể nghĩ về nó như người đứng đầu cũng.
Nhưng đối với cây cối, chúng ta có xu hướng đề cập đến nó như là gốc.
>> Bất cứ điều gì ở phía dưới here-- ở rất, rất bottom--
là lá xem xét.
Vì vậy, nó đi cùng với các toàn bộ điều cây, phải không?
Lá ở các cạnh của cây.
>> Và sau đó chúng tôi cũng có một vài điều kiện để nói chuyện về các nút liên quan
với nhau.
Vì vậy, chúng tôi có cha mẹ, trẻ em, và anh chị em.
Vì vậy, trong trường hợp này, 3 là mẹ của 5, 6, và 7.
Vì vậy, cha mẹ là bất cứ điều gì một bước trên bất cứ điều gì bạn
đề cập đến, vì vậy chỉ cần giống như một cây gia đình.
Hy vọng rằng, đây là tất cả một chút bit trực quan hơn so với cố gắng.
>> Anh chị em là bất kỳ có cùng cha mẹ, phải không?
Họ đang ở trên cùng cấp ở đây.
Và sau đó, như tôi đã nói rằng, trẻ em chỉ là
bất cứ điều gì là một trong những bước dưới đây nút trong câu hỏi, OK?
Cool.
Vì vậy, một cây nhị phân.
Ai cũng có thể gây nguy hiểm đoán về một trong các đặc tính của cây nhị phân?
>> Đung Max hai lá.
>> SPEAKER 1: Đúng vậy.
Vì vậy, tối đa của hai lá.
Vì vậy, trong một này trước đây, chúng tôi đã có một này rằng có ba, nhưng trong một cây nhị phân,
bạn có một tối đa của hai trẻ em mỗi phụ huynh, phải không?
Có một đặc điểm thú vị.
Có ai biết không?
Cây nhị phân.
>> Vì vậy, một cây nhị phân sẽ có tất cả mọi thứ trên the-- này là không sorted--
nhưng trong một cây nhị phân được sắp xếp, tất cả mọi thứ ở bên phải
lớn hơn cha mẹ, và tất cả mọi thứ trên trái
là ít hơn so với cha mẹ.
Và đó là một bài kiểm tra câu hỏi trước, vì vậy tốt để biết.
Vì vậy, cách chúng ta định nghĩa này, một lần nữa, chúng tôi có một nút khác.
Điều này trông rất giống với những gì?
Gấp đôi
>> Danh sách liên kết: TƯỢNG
>> SPEAKER 1: Một danh sách liên kết đôi, phải không?
Vì vậy, nếu chúng ta thay thế này với trước và sau,
đây sẽ là một danh sách gấp đôi liên kết.
Nhưng trong trường hợp này, chúng tôi thực sự có trái và bên phải và đó là nó.
Nếu không, nó giống hệt nhau.
Chúng tôi vẫn còn có các yếu tố bạn đang tìm kiếm,
và bạn chỉ có hai con trỏ đi bất cứ điều gì tiếp theo.
Yeah, cây tìm kiếm nhị phân như vậy.
Nếu chúng tôi nhận thấy, tất cả mọi thứ trên ngay ở đây là than-- lớn hơn
hoặc tất cả mọi thứ ngay lập tức bên phải ở đây
là lớn hơn, tất cả mọi thứ ở đây là ít hơn.
>> Vì vậy, nếu chúng ta tìm kiếm thông qua, nó nên nhìn rất gần với tìm kiếm nhị phân
ở đây, phải không?
Ngoại trừ thay vì tìm kiếm một nửa mảng,
chúng ta chỉ nhìn vào một trong hai bên trái phía này hay phía bên phải của cây.
Vì vậy, nó được một chút đơn giản, tôi nghĩ.
>> Vì vậy, nếu gốc của bạn là NULL, rõ ràng là nó chỉ là sai.
Và nếu nó có, rõ ràng đó là sự thật.
Nếu nó ít hơn, chúng ta tìm kiếm bên trái.
Nếu nó lớn hơn, chúng ta tìm kiếm bên phải.
Đó là chính xác như tìm kiếm nhị phân, chỉ là một cấu trúc dữ liệu khác nhau
mà chúng ta đang sử dụng.
Thay vì một mảng, nó chỉ là một cây nhị phân.
>> OK, ngăn xếp.
Và cũng có thể, nó trông giống như chúng tôi có thể có một chút thời gian.
Nếu chúng ta làm, tôi đang hạnh phúc để đi hơn bất kỳ này một lần nữa.
OK, vì vậy ngăn xếp.
Có ai nhớ những gì stacks-- bất kỳ đặc điểm của một chồng?
>> OK, vì vậy hầu hết chúng ta, tôi nghĩ rằng, ăn trong ăn uống halls--
nhiều như chúng tôi có thể không thích.
Nhưng rõ ràng, bạn có thể nghĩ một chồng nghĩa đen chỉ là một chồng khay
hoặc một chồng của sự vật.
Và điều quan trọng để nhận ra là nó
something-- đặc tính mà chúng ta gọi nó là by-- LIFO.
Có ai biết những gì mà là viết tắt của?
Mmhmm?
>> Đung cuối cùng trong, đầu tiên ra.
>> SPEAKER 1: Phải, kéo dài, ra trước.
Vì vậy, nếu chúng ta biết, nếu chúng ta đang xếp thứ lên, điều dễ nhất để lấy off--
và có lẽ điều duy nhất chúng ta có thể lấy off nếu chồng của chúng tôi là enough-- lớn
là yếu tố hàng đầu.
Vì vậy, bất cứ điều gì đã được đưa vào last-- như chúng ta thấy ở đây,
bất cứ điều gì đã được đẩy trên hầu hết các recently-- là
sẽ là người đầu tiên điều mà chúng tôi bật ra, OK?
>> Vì vậy, những gì chúng tôi có ở đây là một cấu trúc typedef.
Điều này thực sự giống như một sụp đổ khóa học trong cấu trúc dữ liệu,
do đó, có rất nhiều ném vào bạn guys.
Tôi biết.
Vì vậy, thêm một cấu trúc.
Yay cho các cấu trúc.
>> Và trong trường hợp này, đó là một số con trỏ để một mảng có một số năng lực.
Vì vậy, đây đại diện cho chồng của chúng tôi ở đây, giống như mảng thực tế của chúng tôi
đó là tổ chức các yếu tố của chúng tôi.
Và sau đó ở đây chúng tôi có một số kích thước.
>> Và thông thường, bạn muốn giữ lại theo dõi lớn như thế nào ngăn xếp của bạn là
bởi vì những gì nó sẽ cho phép bạn phải làm là nếu bạn biết kích thước,
nó cho phép bạn nói, OK, tôi hết công suất?
Tôi có thể thêm bất cứ điều gì nhiều hơn?
Và nó cũng cho bạn nơi đầu chồng của bạn
là để bạn biết những gì bạn có thể thực sự cất cánh.
Và điều đó thực sự sẽ được rõ ràng hơn một chút ở đây.
>> Vì vậy, để thúc đẩy, có một điều, nếu bạn đã bao giờ thực hiện đẩy,
như tôi đã chỉ nói, của bạn stack có một kích thước giới hạn, phải không?
Mảng của chúng tôi đã có một số năng lực.
Đây là một mảng.
Đó là một kích thước cố định, vì vậy chúng ta cần phải đảm bảo rằng chúng tôi không đưa thêm
vào mảng của chúng ta hơn chúng ta thực sự có không gian cho.
>> Vì vậy, khi bạn đang tạo ra một sự thúc đẩy chức năng, điều đầu tiên bạn làm là nói, OK,
Tôi có không gian trong ngăn xếp của tôi?
Bởi vì nếu tôi không, xin lỗi, Tôi không thể lưu trữ phần tử của bạn.
Nếu tôi làm, sau đó bạn muốn để lưu trữ nó ở trên cùng của ngăn xếp, phải không?
>> Và đây là lý do tại sao chúng tôi có để theo dõi kích thước của chúng tôi.
Nếu chúng ta không theo dõi kích thước của chúng tôi, chúng tôi không biết được nơi để đặt nó.
Chúng tôi không biết bao nhiêu điều là trong mảng của chúng tôi rồi.
Giống như rõ ràng là có nhiều cách rằng có lẽ bạn có thể làm điều đó.
Bạn có thể khởi tạo tất cả mọi thứ để NULL và sau đó kiểm tra cho NULL mới nhất,
nhưng một điều dễ dàng hơn nhiều chỉ là để nói, OK, theo dõi các kích thước.
Giống như tôi biết tôi có bốn yếu tố trong mảng của tôi, do đó, điều tiếp theo
mà chúng tôi đưa vào, chúng tôi đi để lưu trữ tại chỉ số 4.
Và sau đó, tất nhiên, điều này có nghĩa là bạn đã đẩy thành công một cái gì đó
vào ngăn xếp của bạn, bạn muốn tăng kích thước
để bạn biết bạn đang ở đâu vậy mà bạn có thể đẩy mọi thứ thêm về.
>> Vì vậy, nếu chúng tôi đang cố gắng để bật một cái gì đó ra khỏi stack,
những gì có thể là điều đầu tiên mà chúng tôi muốn kiểm tra?
Bạn đang cố gắng để có một cái gì đó ra khỏi ngăn xếp của bạn.
Bạn có chắc chắn có một cái gì đó trong ngăn xếp của bạn?
Không.
Vì vậy, những gì chúng ta có thể muốn kiểm tra?
>> Đung [không nghe được].
SPEAKER 1: Kiểm tra kích thước?
Kích thước.
Vì vậy, chúng tôi muốn kiểm tra xem kích thước của chúng tôi là lớn hơn 0, OK?
Và nếu có, sau đó chúng tôi muốn giảm kích thước của chúng tôi bằng 0 và quay trở lại đó.
Tại sao?
>> Trong giai đoạn đầu chúng tôi đẩy, chúng ta đã đẩy nó
vào kích thước và kích thước sau đó cập nhật.
Trong trường hợp này, chúng tôi đang giảm các kích thước và sau đó dùng nó đi, nó tuốt
từ mảng của chúng tôi.
Tại sao chúng ta có thể làm điều đó?
Vì vậy, nếu tôi có một điều về chồng của tôi, những gì sẽ là kích thước của tôi tại thời điểm đó?
1.
>> Và đâu là 1 phần tử được lưu trữ?
Tại những gì chỉ số?
Đung 0.
SPEAKER 1: 0.
Vì vậy, trong trường hợp này, chúng tôi luôn luôn cần phải thực hiện sure--
thay vì trả lại kích thước trừ đi 1, bởi vì chúng tôi
biết rằng yếu tố của chúng tôi là sẽ được lưu trữ ở 1 ít
bất cứ kích thước của chúng tôi là, điều này chỉ chăm sóc của nó.
Đó là một cách hơi thanh lịch hơn.
Và chúng tôi chỉ giảm giá trị của chúng tôi kích thước và sau đó trở về kích thước.
Mmhmm?
>> Đung tôi đoán chỉ nói chung, tại sao cấu trúc dữ liệu này
có lợi?
>> SPEAKER 1: Nó phụ thuộc vào ngữ cảnh của bạn.
Vì vậy, đối với một số lý thuyết, nếu bạn đang làm việc with-- OK,
cho tôi xem nếu có một lợi đó là mang lại lợi ích cho hơn bên ngoài
của CS.
Với ngăn xếp, bất cứ lúc nào bạn cần để theo dõi một cái gì đó
là gần đây nhất được thêm vào là khi bạn sẽ muốn sử dụng một chồng.
>> Và tôi không thể nghĩ ra một tốt ví dụ đó ngay bây giờ.
Nhưng bất cứ khi nào gần đây nhất điều quan trọng nhất đối với bạn,
đó là khi một chồng sẽ là hữu ích.
Tôi đang cố gắng để nghĩ rằng nếu có một tốt nhất cho việc này.
Nếu tôi nghĩ về một ví dụ tốt trong tiếp theo 20 phút, tôi chắc chắn sẽ cho bạn biết.
>> Nhưng nhìn chung, nếu có bất cứ điều gì, như tôi đã nói hầu hết, gần đây, nơi nhất
là quan trọng nhất, đó là nơi một chồng đến chơi.
Trong khi đó, hàng đợi là loại ngược lại.
Và tất cả những con chó nhỏ.
Đó không phải là tuyệt vời, phải không?
Tôi cảm thấy như tôi nên chỉ có một video bunny
ngay ở giữa phần cho các bạn
bởi vì đây là một phần dữ dội.
>> Vì vậy, một hàng đợi.
Về cơ bản một danh sách giống như một dòng.
Các bạn tôi chắc chắn rằng sử dụng hàng ngày này, giống như trong nhà ăn của chúng tôi.
Vì vậy, chúng tôi phải đi ở và nhận được khay của chúng tôi, tôi
chắc chắn bạn phải chờ đợi trong dòng swipe hoặc nhận được thức ăn của bạn.
>> Vì vậy, sự khác biệt ở đây là đây là FIFO.
Vì vậy, nếu LIFO lần cuối trong, đầu tiên ra, FIFO là lần đầu tiên trong, ra đầu tiên.
Vì vậy, đây là nơi mà bất cứ điều gì bạn đặt về đầu tiên là quan trọng nhất của bạn.
Vì vậy, nếu bạn đã chờ đợi trong một line-- có thể bạn
hãy tưởng tượng nếu bạn đã đi đến đi lấy iPhone mới
và đó là một ngăn xếp nơi người cuối cùng trong dòng nhận nó đầu tiên,
mọi người sẽ giết lẫn nhau.
>> Vì vậy, FIFO, chúng tôi tất cả đều rất quen thuộc với trong thế giới thực sự ở đây,
và tất cả đã làm với thực tế loại tái tạo toàn bộ dòng này
xếp hàng và cấu trúc.
Vì vậy, trong khi với chồng, chúng tôi có push và pop.
Với một hàng đợi, chúng tôi có enqueue và dequeue.
Vì vậy, về cơ bản có nghĩa là enqueue đặt nó lên lưng,
và các phương tiện dequeue mất ra từ phía trước.
Vì vậy, cấu trúc dữ liệu của chúng tôi là một một chút phức tạp hơn.
Chúng tôi có một điều thứ hai để theo dõi.
>> Vì vậy, không có người đứng đầu, điều này là chính xác một chồng, phải không?
Đây là cấu trúc giống như một chồng.
Điều duy nhất khác nhau bây giờ là chúng tôi có đầu này, mà làm những gì bạn nghĩ
sẽ theo dõi?
>> Đung Người đầu tiên.
>> SPEAKER 1: Đúng, các Điều đầu tiên mà chúng tôi đưa vào.
Người đứng đầu hàng đợi của chúng tôi.
Ai là lần đầu tiên trong dòng.
Tất cả các bên phải, vì vậy nếu chúng ta làm enqueue.
Một lần nữa, với bất kỳ các cấu trúc dữ liệu,
kể từ khi chúng tôi đang làm việc với một mảng, chúng ta cần phải kiểm tra xem chúng tôi có không gian.
>> Đây là loại giống như tôi nói các bạn, nếu bạn mở một tập tin,
bạn cần phải kiểm tra null.
Với bất kỳ các ngăn xếp và hàng đợi, bạn cần
để xem nếu có không gian bởi vì chúng tôi đối phó với một mảng kích thước cố định,
như chúng ta thấy here-- 0, 1 tất cả lên đến 5.
Vì vậy, những gì chúng tôi làm trong trường hợp đó là kiểm tra để xem nếu chúng ta vẫn còn có không gian.
Là kích thước của chúng tôi ít hơn năng lực?
>> Nếu vậy, chúng ta cần phải lưu trữ nó ở đuôi và chúng tôi cập nhật kích thước của chúng tôi.
Vì vậy, những gì có thể đuôi được trong trường hợp này?
Nó không phải một cách rõ ràng bằng văn bản ra.
Làm thế nào chúng ta có thể lưu trữ nó?
Điều gì sẽ đuôi được?
>> Vì vậy, hãy đi bộ qua ví dụ này.
Vì vậy, đây là một mảng có kích thước 6, phải không?
Và chúng tôi có ngay bây giờ, kích thước của chúng tôi là 5.
Và khi chúng ta đặt nó trong, nó sẽ để đi vào chỉ số thứ năm, phải không?
Vì vậy, lưu trữ ở đuôi.
>> Một cách khác để viết đuôi sẽ chỉ là mảng của chúng tôi ở chỉ số kích thước, phải không?
Đây là kích thước 5.
Điều tiếp theo là sẽ đi vào 5.
Mát mẻ?
OK.
Nó trở nên phức tạp hơn một chút khi chúng tôi bắt đầu rối tung với người đứng đầu.
Có?
>> Đung Điều đó có nghĩa rằng chúng ta đã có thể tuyên bố một mảng
đã lâu năm yếu tố và sau đó chúng tôi đang thêm vào nó?
>> SPEAKER 1: No.
Vì vậy, trong trường hợp này, đây là một chồng.
Điều này sẽ được công bố như một mảng có kích thước 6.
Và trong trường hợp này, chúng tôi chỉ có một không gian trống.
>> OK, vì vậy có một điều trong này trường hợp, nếu người đứng đầu của chúng tôi là ở 0,
sau đó chúng tôi chỉ có thể thêm nó ở kích thước.
Nhưng nó được một chút phức tạp hơn bởi vì trên thực tế, họ
không có một slide cho điều này, vì vậy tôi sẽ
để vẽ một bởi vì nó không khá đơn giản khi bạn
bắt đầu nhận được thoát khỏi điều này.
Vì vậy, trong khi với một chồng bạn chỉ bao giờ có
phải lo lắng về những gì kích thước là khi bạn đang thêm một cái gì đó trên,
với một hàng đợi bạn cũng cần phải thực hiện chắc chắn rằng đầu của bạn được hạch toán,
bởi vì một điều thú vị về hàng đợi là nếu bạn không hết công suất,
bạn thực sự có thể làm cho nó quấn quanh.
>> OK, vì vậy một thing-- oh, này là phấn khủng khiếp.
Một điều cần xem xét là trường hợp.
Chúng tôi sẽ chỉ làm năm.
OK, vì vậy chúng ta sẽ nói người đứng đầu ở đây.
Đây là 0, 1, 2, 3, 4.
>> Người đứng đầu là có, và xin vui lòng có những thứ trong đó.
Và chúng tôi muốn thêm một cái gì đó trong, phải không?
Vì vậy, điều mà chúng ta cần biết là người đứng đầu luôn luôn là
sẽ di chuyển theo cách này và sau đó lặp lại xung quanh, OK?
>> Vì vậy, hàng đợi này có không gian, phải không?
Nó có không gian trong đầu, loại đối lập này.
Vì vậy, những gì chúng ta cần làm là chúng tôi cần phải tính toán đuôi.
Nếu bạn biết rằng bạn đầu đã không di chuyển, đuôi
chỉ là mảng của bạn tại chỉ số của kích thước.
>> Nhưng trong thực tế, nếu bạn đang sử dụng một hàng đợi, đầu của bạn có thể được cập nhật.
Vì vậy, những gì bạn cần làm là thực sự tính toán đuôi.
Vì vậy, những gì chúng tôi làm công thức này là ở đây, mà tôi sẽ để cho bạn
kẻ suy nghĩ về, và sau đó chúng ta sẽ nói về nó.
Vì vậy, đây là năng lực.
>> Vì vậy, đây sẽ thực sự cung cấp cho bạn một cách để làm điều đó.
Bởi vì trong trường hợp này, những gì?
Đầu của chúng tôi là 1, kích thước của chúng tôi là 4.
Nếu chúng ta mod đó thêm 5, chúng tôi nhận được 0, đó là nơi mà chúng ta nên đầu vào nó.
>> Vì vậy, sau đó trong trường hợp tiếp theo, nếu chúng ta làm điều này,
chúng ta nói, OK, chúng ta hãy dequeue một cái gì đó.
Chúng tôi dequeue này.
Chúng tôi đưa ra yếu tố này, phải không?
>> Và bây giờ đầu của chúng tôi là chỉ ở đây, và chúng tôi muốn thêm vào một chuyện khác.
Điều này về cơ bản là trở lại của dòng của chúng tôi, phải không?
Hàng đợi có thể quấn xung quanh mảng.
Đó là một trong những khác biệt chính.
Stacks, bạn không thể làm điều này.
>> Với hàng đợi, bạn có thể bởi vì tất cả những vấn đề
là bạn biết những gì gần đây nhất được thêm vào.
Kể từ khi tất cả mọi thứ sẽ được thêm vào trong hướng về phía trái này, trong trường hợp này,
và sau đó quấn xung quanh, bạn có thể tiếp tục đưa vào các yếu tố mới
ở phía trước của mảng bởi vì nó không thực sự
phía trước của mảng nữa.
Bạn có thể nghĩ đầu mảng như là nơi đầu của bạn thực sự là.
>> Vì vậy, công thức này là như thế nào bạn tính toán đuôi của bạn.
Điều đó làm cho tinh thần?
OK.
OK, dequeue, và sau đó các bạn có 10 phút
hỏi tôi bất kỳ câu hỏi làm rõ bạn muốn, bởi vì tôi biết đó là điên.
>> Tất cả các bên phải, vì vậy trong way-- cùng Tôi không biết nếu các bạn để ý,
nhưng CS là tất cả về mô hình.
Những điều được khá nhiều tương tự, chỉ với vài tinh chỉnh nhỏ.
Vì vậy, cùng một điều ở đây.
Chúng tôi cần phải kiểm tra để xem nếu chúng ta thực sự có một cái gì đó trong hàng đợi của chúng tôi, phải không?
Nói, OK, là kích thước của chúng tôi lớn hơn 0?
Cool.
>> Nếu chúng ta làm, sau đó chúng tôi di chuyển đầu của chúng tôi, là những gì tôi chỉ thể hiện ở đây.
Chúng tôi cập nhật đầu của chúng tôi là một trong hơn.
Và sau đó chúng tôi giảm giá trị của chúng tôi kích thước và quay trở lại phần tử.
>> Nhiều hơn bê tông có mã trên study.cs50.net,
và tôi rất khuyên bạn nên đi qua nó nếu bạn có thời gian,
thậm chí nếu nó chỉ là một pseudo-code.
Và nếu các bạn muốn nói chuyện qua với tôi, một ngày một, xin vui lòng cho tôi
biết.
Tôi muốn được hạnh phúc để.
Cấu trúc dữ liệu, nếu bạn có CS 124, bạn sẽ
biết rằng cấu trúc dữ liệu nhận được rất niềm vui và điều này chỉ mới bắt đầu.
>> Vì vậy, tôi biết đó là khó khăn.
Đó là OK.
Chúng tôi đấu tranh.
Tôi vẫn làm.
Vì vậy, đừng lo lắng quá nhiều về nó.
>> Nhưng đó là về cơ bản bạn sụp đổ khóa học trong cấu trúc dữ liệu.
Tôi biết nó rất nhiều.
Có điều gì đó chúng tôi muốn đi qua một lần nữa?
Bất cứ điều gì chúng ta muốn nói qua?
Có?
>> Đung Ví dụ đó, vì vậy đuôi mới là 0 trên đó?
SPEAKER 1: Có.
Đung OK.
Vì vậy, sau đó đi qua, bạn muốn có 1 cộng với 4 or--
>> SPEAKER 1: Vì vậy, bạn đã nói, khi chúng ta muốn đi làm điều này một lần nữa?
Đung Yeah.
Vì vậy, nếu bạn đang tìm out-- ở đâu bạn tính toán đuôi từ trong đó?
>> SPEAKER 1: Vì vậy, đuôi là in-- tôi đã thay đổi này.
Vì vậy, trong ví dụ này ở đây, đây là mảng chúng tôi đang tìm kiếm, OK?
Vì vậy, chúng tôi có điều trong 1, 2, 3 và 4.
Vì vậy, chúng tôi có đầu của chúng tôi là bằng 1 tại thời điểm này, và kích thước của chúng tôi là bằng 4
tại thời điểm này, phải không?
>> Các bạn đồng ý đó là trường hợp?
Vì vậy, chúng ta làm người đứng đầu cộng với kích thước, mà cho chúng ta 5, và sau đó chúng tôi mod bởi 5.
Chúng tôi nhận được 0, mà cho chúng ta biết là 0 đâu là đuôi của chúng tôi, nơi chúng tôi có không gian.
>> Đung một nắp là gì?
>> SPEAKER 1: năng lực.
Xin lỗi.
Vì vậy, đó là kích thước của mảng của bạn.
Có?
>> Đung [không nghe được] trước chúng tôi trở lại các yếu tố?
>> SPEAKER 1: Vì vậy, chúng tôi di chuyển đứng đầu hoặc quay trở lại thời điểm này?
Vì vậy, nếu chúng ta di chuyển một, giảm các kích thước?
Giữ trên.
Tôi chắc chắn quên khác.
Đừng bận tâm.
Không có một công thức khác.
Yeah, bạn sẽ muốn quay trở lại người đứng đầu và sau đó di chuyển nó trở lại.
>> Đung OK, bởi vì Tại đây điểm, người đứng đầu là 0,
và sau đó bạn muốn quay trở lại chỉ số 0 và sau đó làm cho đầu 1?
>> SPEAKER 1: Đúng vậy.
Tôi nghĩ rằng có một công thức loại như thế này.
Tôi không có nó ở trên đầu của tôi như Tôi không muốn cung cấp cho bạn một sai lầm.
Nhưng tôi nghĩ rằng đó là hoàn toàn hợp lệ nói, OK, lưu trữ element-- này bất cứ điều gì
yếu tố đầu của is-- giảm giá trị của bạn kích thước, di chuyển đầu của bạn hơn, và trở lại
bất cứ yếu tố đó là.
Đó là hoàn toàn hợp lệ.
OK.
Tôi cảm thấy như thế này không phải là như most-- bạn không
sẽ đi bộ ra khỏi đây như, có, tôi biết cố gắng.
Tôi có tất cả.
Đó là OK.
Tôi hứa.
Tuy nhiên, cấu trúc dữ liệu là một cái gì đó phải mất rất nhiều thời gian để làm quen.
Có lẽ một trong những khó khăn nhất điều, tôi nghĩ rằng, trong khóa học.
>> Vì vậy, nó chắc chắn có lặp lại và tìm kiếm at-- tôi
thực sự không biết danh sách liên kết cho đến khi tôi đã làm quá nhiều với họ,
trong cùng một cách mà tôi đã làm không thực sự hiểu con trỏ
cho đến khi tôi đã dạy nó cho hai năm và làm psets riêng của tôi với nó.
Phải mất rất nhiều của sự lặp lại và thời gian.
Và cuối cùng, nó sẽ loại nhấn chuột.
>> Nhưng trong khi chờ đợi, nếu bạn có loại một sự hiểu biết cao cấp của những gì
những làm, ưu của họ cons-- và đó là những gì
chúng tôi thực sự có xu hướng nhấn mạnh, đặc biệt là trong quá trình giới thiệu.
Giống như, tại sao chúng ta sẽ sử dụng một thử trên một mảng?
Giống như, những mặt tích cực là gì và tiêu cực của mỗi người?
>> Và sự hiểu biết về thương mại-off giữa mỗi của các cấu trúc
là những gì là quan trọng hơn nhiều ngay bây giờ.
Có thể có một điên hoặc hai câu hỏi là
sẽ yêu cầu bạn thực hiện đẩy hoặc thực hiện pop hoặc enqueue và dequeue.
Nhưng đối với hầu hết các phần, có mà hiểu biết mức độ cao hơn và nhiều hơn nữa
của một nắm bắt trực quan là quan trọng hơn thực tế
có khả năng để thực hiện nó.
>> Nó muốn được thực sự tuyệt vời nếu tất cả các bạn có thể đi ra ngoài và đi thực hiện một thử,
nhưng chúng tôi hiểu nó không nhất thiết điều hợp lý nhất ngay bây giờ.
Nhưng bạn có thể trong pset của bạn, nếu bạn muốn đến, và sau đó bạn sẽ nhận được thực tế,
và sau đó có thể bạn sẽ thấy thực sự hiểu nó.
Có?
>> Đung OK, vì vậy mà những người có chúng tôi có nghĩa là để sử dụng trong pset?
Tôi có cần phải sử dụng một trong số họ?
SPEAKER 1: Có.
Vì vậy, bạn có sự lựa chọn của bạn.
Tôi đoán trong trường hợp này, chúng ta có thể nói về pset một chút
bởi vì tôi chạy qua này.
Vì vậy, trong pset của bạn, bạn có của bạn lựa chọn hoặc cố gắng bảng băm.
Một số người sẽ cố gắng và sử dụng bộ lọc nở,
nhưng những kỹ thuật là không chính xác.
Bởi vì bản chất xác suất của họ, họ cung cấp cho dương tính giả đôi khi.
Họ nhìn mát mẻ vào, mặc dù.
Khuyên bạn nên tìm kiếm tại họ ít nhất.
Nhưng bạn có sự lựa chọn của bạn giữa một bảng băm và một thử.
Và đó sẽ là nơi bạn nạp trong từ điển của bạn.
>> Và bạn sẽ cần phải chọn hàm băm của bạn,
bạn sẽ cần phải chọn bao nhiêu xô bạn có, và nó sẽ thay đổi.
Cũng giống như nếu bạn có nhiều xô, có thể nó sẽ chạy nhanh hơn.
Nhưng có lẽ bạn đang lãng phí một rất nhiều không gian theo cách đó, mặc dù.
Bạn phải tìm ra nó.
Mmhmm?
>> ĐỐI TƯỢNG: Bạn nói trước đó chúng ta có thể sử dụng hàm băm khác,
rằng chúng ta không cần phải tạo một hàm băm?
>> SPEAKER 1: Vâng, đúng.
Vì vậy, theo nghĩa đen cho hàm băm của bạn, như google "hàm băm"
và tìm kiếm một số những người mát mẻ.
Bạn không được dự kiến ​​sẽ xây dựng hàm băm của riêng bạn.
Mọi người dành của họ luận án về những điều này.
>> Vì vậy, đừng lo lắng về việc xây dựng của riêng bạn.
Tìm một trực tuyến để bắt đầu.
Một số trong số họ, bạn phải thao tác một chút
để đảm bảo loại trở lại phù hợp và không có điều gì, vì vậy trong đầu,
Tôi sẽ khuyên bạn nên sử dụng một cái gì đó thực sự dễ dàng mà có thể chỉ
băm vào chữ cái đầu tiên.
Và sau đó một khi bạn đã làm việc đó, kết hợp một hàm băm mát.
Mmhmm?
>> Đung một sẽ cố gắng được hoặc hiệu quả nhưng chỉ khó, like--
>> SPEAKER 1: Vì vậy, một thử, tôi nghĩ rằng, là trực giác khó thực hiện
nhưng là rất nhanh.
Tuy nhiên, có nhiều không gian hơn.
Một lần nữa, bạn có thể tối ưu hóa cả của những người trong cách khác nhau và có những cách đối với:
ĐỐI TƯỢNG: Làm thế nào chúng ta có phân loại về điều này?
Liệu nó matter--
>> SPEAKER 1: Vì vậy, bạn đang phân loại theo cách thông thường.
Bạn sẽ được chấm điểm dựa trên thiết kế.
Tùy theo cách bạn làm, bạn muốn chắc chắn rằng nó là thanh lịch như nó có thể được
và hiệu quả như nó có thể được.
Nhưng nếu bạn chọn một thử hoặc băm bảng, miễn là nó hoạt động,
chúng tôi hạnh phúc với điều đó.
Và nếu bạn sử dụng một cái gì đó băm trên các chữ cái đầu tiên, đó là tốt,
như có lẽ giống như thiết kế khôn ngoan.
Chúng tôi cũng đạt điểm trong semester-- này
Tôi không biết nếu bạn kẻ noticed-- nếu bạn
lớp pset giảm một chút vì thiết kế và không có điều gì,
đó là hoàn toàn tốt đẹp.
Nó nhận được đến một điểm mà bạn các chương trình đang nhận được phức tạp hơn.
Có rất nhiều nơi hơn bạn có thể cải thiện.
>> Vì vậy, nó hoàn toàn bình thường.
Nó không phải là bạn làm tồi tệ hơn vào pset của bạn.
Nó chỉ là chúng ta đang bị khó khăn hơn về bạn bây giờ.
Vì vậy, mọi người cảm thấy nó.
Tôi chỉ phân loại tất cả các psets của bạn.
Tôi biết mọi người đang cảm thấy nó.
>> Vì vậy, không phải lo lắng về điều đó.
Và nếu bạn có bất kỳ câu hỏi về psets trước hoặc cách bạn có thể cải thiện,
Tôi cố gắng và bình luận cụ thể nơi, nhưng đôi khi nó là muộn
và tôi cảm thấy mệt mỏi.
Có những thứ khác về cấu trúc dữ liệu?
Tôi chắc rằng các bạn không thực sự muốn nói về họ nữa,
nhưng nếu có, tôi hạnh phúc đến đi qua họ, cũng như bất cứ điều gì
từ bài giảng vừa qua tuần hoặc cuối tuần trước.
>> Tôi biết tuần trước đã xem xét tất cả, vì vậy chúng tôi có thể đã bỏ qua một số xét
từ bài giảng.
Bất kỳ câu hỏi khác tôi có thể trả lời?
OK, được rồi.
Vâng, các bạn có được ra sớm 15 phút.
>> Tôi hy vọng điều này là bán hữu ích ít nhất, và tôi sẽ gặp các bạn vào tuần tới,
hoặc thứ năm giờ hành chính.
Có những yêu cầu cho bữa ăn nhẹ cho tuần tới, đó là điều?
Bởi vì tôi quên kẹo ngày hôm nay.
Và tôi đã mang kẹo cuối cùng tuần, nhưng nó đã Columbus Day,
như vậy có giống như sáu người có bốn túi kẹo cho bản thân.
Tôi có thể mang lại Starbursts một lần nữa nếu bạn muốn.
Starbursts?
OK, âm thanh tốt.
Có một ngày tuyệt vời, guys.