[MUSIC CHƠI]
>> DAVID Malan: Đây là CS50.
Và đây là cả hai bắt đầu và end-- như literally-- gần như cuối cùng
tuần sáu.
>> Tôi nghĩ rằng tôi muốn chia sẻ một chút của một thực tế thú vị.
Tôi đã kéo này lên từ một thiết lập dữ liệu của học kỳ vừa qua.
Bạn có thể nhớ lại rằng chúng tôi yêu cầu bạn trên tất cả các p thiết lập hình thức nếu bạn đã theo dõi trực tuyến
hoặc nếu bạn đã học trong người.
Và đây là dữ liệu.
Vì vậy, ngày hôm nay là rất nhiều dự đoán được.
Nhưng chúng tôi muốn dành một chút thời gian với bạn dù sao.
Bất cứ ai muốn phỏng đoán tại sao điều này đồ thị là để răng cưa, lên xuống, lên xuống,
nên nhất quán không?
Làm gì mỗi của các đỉnh núi và đáy đại diện?
>> Đung [không nghe được]
DAVID Malan: Thật vậy.
Và amusingly hơn, thần cấm, chúng tôi tổ chức một bài giảng vào ngày thứ sáu
vào đầu học kỳ, đó là những gì chúng ta thấy xảy ra.
Vì vậy, ngày hôm nay, chúng ta cùng chia sẻ một chút thêm về cấu trúc dữ liệu.
Và để cung cấp cho bạn nhiều hơn của một chất rắn mô hình tinh thần cho các vấn đề ở năm,
mà bây giờ ra.
Lỗi chính tả, trong đó, chúng ta sẽ đưa cho bạn một tập tin văn bản một số 100.000
cộng với từ tiếng Anh, và bạn sẽ có
để tìm ra cách để khéo léo tải chúng vào bộ nhớ, vào RAM, sử dụng một số dữ liệu
cấu trúc của sự lựa chọn của bạn.
>> Bây giờ một cấu trúc dữ liệu như vậy có thể được, nhưng có lẽ không nên,
danh sách liên kết khá đơn giản, mà chúng tôi giới thiệu thời gian qua.
Và một danh sách liên kết có ít nhất một lợi thế hơn một mảng.
Một lợi thế của những gì một danh sách liên kết cho là?
>> Đung Chen.
>> DAVID Malan: Đầu vào.
Bạn có ý nghĩa gì vậy?
>> Đung Anywhere cùng danh sách [không nghe được].
>> DAVID Malan: Tốt.
Vì vậy, bạn có thể chèn một phần tử bất cứ nơi nào bạn muốn ở giữa của danh sách
mà không cần phải xáo trộn bất cứ điều gì, mà chúng tôi kết luận, trong phân loại của chúng tôi
thảo luận, không phải là nhất thiết phải là một điều tốt,
bởi vì nó cần có thời gian để thực sự di chuyển tất cả những con người trái hoặc phải.
Và như vậy với một danh sách liên kết, bạn có thể chỉ phân bổ với malloc, một nút mới,
và sau đó cập nhật một vài pointers-- hai, ba hoạt động max--
và chúng tôi có thể khe cắm một người nào đó ở bất cứ nơi nào vào một danh sách.
>> Những gì người khác là thuận lợi về một danh sách liên kết?
Yeah?
>> Đung [không nghe được]
DAVID Malan: Hoàn hảo.
Perfect.
Nó thực sự năng động.
Và rằng bạn không cam kết, trước, một số kích thước cố định
đoạn bộ nhớ, như bạn sẽ phải đến với một mảng, lộn ngược trong đó
là bạn có thể bố trí các nút chỉ trên do đó nhu cầu sử dụng chỉ như nhiều không gian
khi bạn thực sự cần.
Ngược lại với một mảng, bạn có thể vô tình chia quá ít.
Và sau đó nó chỉ cần đi là một cơn đau ở cổ
tái phân bổ một mảng lớn hơn mới, sao chép tất cả mọi thứ trên, giải phóng mảng cũ,
và sau đó di chuyển về doanh nghiệp của bạn.
Hoặc tệ hơn, bạn có thể phân bổ cách bộ nhớ nhiều hơn bạn thực sự cần,
và vì vậy bạn sẽ có một rất dân cư thưa thớt mảng, vậy để nói chuyện.
>> Vì vậy, một danh sách liên kết cung cấp cho bạn những lợi thế của tính năng động và linh hoạt
với chèn và xóa bỏ.
Nhưng chắc chắn phải có một giá phải trả.
Trong thực tế, một trong những chủ đề khám phá trên bài kiểm tra không
là một vài thương mại-off chúng ta đã thấy cho đến nay.
Vì vậy, một giá phải trả hay là những gì nhược điểm của một danh sách liên kết?
Yeah.
>> ĐỐI TƯỢNG: Không có truy cập ngẫu nhiên.
>> DAVID Malan: Không có truy cập ngẫu nhiên.
Nhưng những người quan tâm?
Truy cập ngẫu nhiên không âm thanh hấp dẫn.
>> Đung [không nghe được]
DAVID Malan: Chính xác.
Nếu bạn muốn có một algorithm-- nhất định
và cho tôi thực sự đề xuất tìm kiếm nhị phân đặc biệt, mà
là một trong chúng tôi đã sử dụng khá bit-- nếu bạn không có quyền truy cập ngẫu nhiên,
bạn không thể làm điều đó số học đơn giản tìm kiếm như các yếu tố trung
và nhảy ngay đến nó.
Thay vào đó bạn phải bắt đầu từ người đầu tiên yếu tố và tuyến tính tìm kiếm từ bên trái
bên phải nếu bạn muốn tìm giữa hoặc bất kỳ yếu tố khác.
>> Đung Nó có thể mất nhiều bộ nhớ hơn.
>> DAVID Malan: Đưa bộ nhớ hơn.
Ở đâu mà thêm chi phí đến từ trong bộ nhớ?
>> Đung [không nghe được]
DAVID Malan: Chính xác.
Trong trường hợp này ở đây, chúng tôi đã có một danh sách liên kết cho các số nguyên,
nhưng chúng tôi đang tăng gấp đôi số lượng bộ nhớ
chúng ta cần bởi cũng lưu trữ các con trỏ.
Bây giờ ít hơn của một vấn đề lớn như cấu trúc của bạn nhận được lớn hơn
và bạn đang lưu trữ không phải là một số nhưng có thể là một sinh viên hoặc một số đối tượng khác.
Nhưng điểm chắc chắn vẫn còn.
Và do đó, một số hoạt động trên danh sách liên kết được gọi là
là O lớn của n-- tuyến tính.
Những điều như chèn hoặc tìm kiếm hoặc xóa trong trường hợp một yếu tố
xảy ra để được vào cuối của danh sách cho dù nó được sắp xếp hay không.
>> Đôi khi bạn có thể nhận được may mắn và trong giới hạn rất thấp trên các hoạt động này
cũng có thể là hằng số thời gian nếu bạn luôn luôn nhìn vào các yếu tố đầu tiên,
ví dụ.
Nhưng cuối cùng, chúng tôi đã hứa để đạt được Chén thánh
cấu trúc dữ liệu, hoặc một số trong đó xấp xỉ,
bằng cách hằng số thời gian.
Chúng ta có thể tìm thấy các yếu tố hoặc các yếu tố hoặc loại bỏ các yếu tố từ một danh sách?
Chúng ta sẽ thấy khá sớm.
Và nó chỉ ra rằng một các cơ chế chúng tôi
sẽ bắt đầu sử dụng ngày hôm nay, sử dụng hàng năm trong p thiết lập năm,
thực sự là khá quen thuộc.
Ví dụ, nếu điều này là một bó sách thi, mỗi trong số đó
có một học sinh đầu tiên đặt tên và tên cuối cùng trên nó,
và tôi chọn chúng từ ở phần cuối của một kỳ thi,
và tất cả đều khá nhiều theo một thứ tự ngẫu nhiên,
và chúng tôi muốn đi về phân loại các kỳ thi để khi phân loại
nó dễ dàng hơn chỉ là một rất nhiều và nhanh hơn để giao lại ra
cho học sinh theo thứ tự abc.
Những gì bản năng của bạn sẽ được cho một đống của các kỳ thi như thế này?
>> Vâng, nếu bạn đang như tôi, bạn có thể thấy rằng đây là m,
vì vậy tôi sẽ để loại đặt điều này vào, nếu điều này là bàn của tôi hoặc sàn nhà của tôi, nơi
Tôi đang lan rộng điều out-- hoặc mảng của tôi really--
Tôi có thể đặt tất cả các bà trong đó.
Oh.
Dưới đây là một A. Vì vậy, tôi có thể Khi đặt ở đây.
Oh.
Đây là một A. Tôi sẽ để đưa qua đây.
Dưới đây là một Z. Đây là một M. Và như vậy Tôi có thể bắt đầu làm cọc như thế này.
Và sau đó có lẽ tôi sẽ đi vào sau và loại rất nitpicky-ly loại
cọc cá nhân.
Nhưng vấn đề là tôi sẽ xem xét tại đầu vào rằng tôi là tay
và tôi sẽ làm cho một số tính quyết định dựa trên đầu vào đó.
Nếu nó bắt đầu với A, đặt nó ở đó.
Nếu nó bắt đầu với Z, đặt nó lên ở đó, và tất cả mọi thứ ở giữa.
>> Vì vậy, đây là một kỹ thuật đó là thường được gọi là hashing-- H-A-S-H--
mà thường có nghĩa là dùng như đầu vào và sử dụng đầu vào để tính toán
một giá trị, nói chung là một số, và số là chỉ số vào một lưu trữ
container, giống như một mảng.
Vì vậy, nói cách khác, tôi có thể có một hàm băm, như tôi đã làm trong đầu tôi,
rằng nếu tôi nhìn thấy một ai đó Tên người bắt đầu với A,
Tôi sẽ để bản đồ đó bằng không trong đầu tôi.
Và nếu tôi nhìn thấy một người nào đó với Z, tôi sẽ bản đồ đó đến 25 trong đầu của tôi
và sau đó đặt điều đó vào hầu hết đống cuối cùng.
>> Bây giờ, nếu bạn suy nghĩ về không não của tôi nhưng một chương trình C, những gì con số có thể
bạn dựa vào để đạt được điều đó kết quả tương tự?
Nói cách khác, nếu bạn có các ký tự ASCII A,
làm thế nào để bạn xác định những gì xô để đặt nó trong?
Bạn có lẽ không muốn đặt nó vào thùng 65, mà
sẽ như thế nào trên đó không có lý do tốt.
Nơi nào bạn muốn đặt A về giá trị ASCII của nó?
Nơi nào bạn muốn làm để ASCII của nó giá trị để đến với một cái xô thông minh hơn
để đặt nó trong?
>> Đung Minus A.
>> DAVID Malan: Yeah.
Vì vậy, trừ A hoặc trừ đặc biệt 65 nếu nó
A. một vốn Hoặc nếu 98 đó là một chữ thường a.
Và do đó sẽ cho phép chúng ta, rất đơn giản và rất số học,
đặt một cái gì đó vào một cái xô như thế.
Vì vậy, hóa ra chúng ta thực sự làm này là tốt ngay cả với các câu đố.
>> Vì vậy, bạn có thể nhớ lại bạn vòng của bạn Tên giáo viên trên trang bìa.
Và tên của TF đã được tổ chức vào các cột theo thứ tự abc,
tốt, có tin hay không, khi tất cả 80 cộng của chúng tôi
đã cùng nhau đêm khác đến lớp, bước cuối cùng trong quá trình chấm điểm của chúng tôi
là để băm câu đố vào một lớn không gian của sàn tại [không nghe được]
và đặt các câu đố của tất cả mọi người ra trong chính xác thứ tự của TF của họ
tên trên trang bìa, vì sau đó nó dễ dàng hơn rất nhiều cho chúng tôi
để tìm kiếm thông qua đó sử dụng tuyến tính tìm kiếm hoặc một số loại thông minh
cho một TF để tìm mình hoặc câu đố học sinh của mình.
>> Vì vậy, ý tưởng này của băm bạn sẽ thấy là
khá mạnh mẽ thực sự là khá phổ biến và rất trực quan,
giống như có thể phân chia và chinh phục là trong tuần không.
Tôi nhanh chóng đến hackathon về phía trước một vài năm trước đây.
Đây là Zamyla và một vài sinh viên nhân viên lời chào khác
khi họ bước vào.
Và chúng tôi đã có một bó toàn bộ gấp bảng đó với thẻ tên.
Và chúng tôi đã có những thẻ tên tổ chức với giống như Như trên đó
và Zs ở đó.
Và vì vậy một trong những TFs rất khéo léo đã viết này như hướng dẫn
trong ngày.
Và trong tuần 12 của học kỳ này tất cả các ý nghĩa hoàn hảo và tất cả mọi người
biết phải làm gì.
Nhưng bất cứ lúc nào bạn đã xếp hàng trong cùng một cách,
bạn đang thực hiện cùng một khái niệm về một băm.
Vì vậy, hãy chính thức hóa nó một chút.
Dưới đây là một mảng.
Nó rút ra được một chút rộng chỉ để miêu tả, trực quan,
chúng ta có thể đưa dây trong một cái gì đó như thế này.
Và mảng này là rõ ràng của tổng kích thước 26.
Và điều được gọi là bảng tùy tiện.
Nhưng điều này chỉ là màn biểu diễn của một nghệ sĩ những gì một bảng băm có thể được.
>> Vì vậy, một bảng băm bây giờ sẽ là một cấu trúc dữ liệu cấp độ cao hơn.
Vào cuối ngày chúng tôi về để thấy rằng bạn
có thể thực hiện một bảng băm, mà là giống như các dòng check-in
tại một hackathon nhiều như thế này bảng được sử dụng để phân loại sách thi.
Nhưng một bảng băm là loại cao cấp này
khái niệm mà có thể sử dụng một mảng bên dưới mui xe để thực hiện nó,
hoặc nó có thể sử dụng một danh sách dài, hoặc thậm chí có lẽ một số cấu trúc dữ liệu khác.
Và bây giờ đó là việc lấy theme-- một số trong những thành phần cơ bản
giống như một mảng và tòa nhà này ngăn chặn hiện nay của một danh sách dài
và nhìn thấy những gì khác chúng ta có thể xây dựng trên đầu trang của những người, như thành phần
vào một công thức, làm cho ngày càng nhiều kết quả cuối cùng thú vị và hữu ích.
>> Vì vậy, với bảng băm chúng ta có thể thực hiện nó
trong bộ nhớ những bức tranh như thế này, nhưng làm thế nào có thể nó thực sự được mã hóa lên?
Vâng, có lẽ là chỉ đơn giản là thế này.
Nếu NĂNG LỰC trong tất cả các mũ, chỉ là một số constant-- ví dụ 26,
26 chữ cái của alphabet-- Tôi có thể gọi là bảng biến của tôi,
và tôi có thể khẳng định rằng tôi sẽ đặt sao char trong đó, hoặc chuỗi.
Vì vậy, nó đơn giản như này nếu bạn muốn thực hiện một bảng băm.
Tuy nhiên, điều này thực sự chỉ là một mảng.
Nhưng một lần nữa, một băm bảng tại là những gì chúng tôi sẽ
gọi một kiểu dữ liệu trừu tượng mà chỉ sắp xếp của một lớp khái niệm trên
của một cái gì đó trần tục hơn hiện nay giống như một mảng.
>> Bây giờ, làm thế nào chúng ta đi về việc giải quyết vấn đề?
Vâng, trước đó tôi đã có sự sang trọng của việc có đủ không gian bảng ở đây
để tôi có thể đặt câu đố bất cứ nơi nào tôi muốn.
Vì vậy, Như có thể đi đây.
Zs có thể đi đây.
Bà có thể đi đây.
Và sau đó tôi đã có một số không gian thêm.
Nhưng đây là một chút của một cheat đúng bây giờ bởi vì bảng này, nếu tôi thực sự
nghĩ về nó như một mảng, chỉ cần là sẽ có một số kích thước cố định.
>> Vì vậy, về mặt kỹ thuật, nếu tôi kéo lên bài kiểm tra của học sinh khác
và xem, oh, người này tên bắt đầu bằng A cũng vậy,
Tôi loại muốn đặt nó ở đó.
Nhưng ngay sau khi tôi đặt nó ở đó, nếu bảng này thực sự đại diện cho một mảng,
Tôi sẽ được trọng hoặc clobbering ai đố của học sinh này là.
Phải không?
Nếu đây là một mảng, chỉ có một điều có thể đi trong mỗi tế bào hoặc các yếu tố.
Và vì vậy tôi loại có chọn và chọn.
>> Bây giờ trước đó tôi loại lừa dối và đã làm điều này hay tôi
chỉ cần loại xếp chồng lên nhau họ trên mỗi khác.
Nhưng đó không phải đi để bay trong mã.
Vì vậy, nơi tôi có thể đặt sinh viên thứ hai có tên
Một là nếu tất cả tôi đã có được này không gian bảng có sẵn?
Và tôi đã sử dụng ba khe cắm và nó có vẻ như đó chỉ là một vài người khác.
Bạn có thể làm gì?
Đung [không nghe được]
DAVID Malan: Yeah.
Có lẽ chúng ta hãy giữ nó đơn giản.
Phải không?
Nó không phù hợp với nơi tôi muốn đặt nó.
Vì vậy, tôi sẽ đặt nó về mặt kỹ thuật mà một B sẽ đi.
Bây giờ, tất nhiên, tôi bắt đầu vẽ bản thân mình vào một góc.
Nếu tôi nhận được cho một học sinh có tên thực sự là B,
doanh nghiệp B sẽ được di chuyển một chút về phía trước, như có thể xảy ra, vâng,
nếu điều này là một B, bây giờ nó có để đi đây.
>> Và vì vậy điều này rất nhanh chóng có thể trở thành vấn đề,
nhưng đó là một kỹ thuật mà thực sự được gọi là tuyến tính thăm dò,
nhờ đó mà bạn chỉ xem xét của bạn mảng là dọc theo đường.
Và bạn chỉ cần loại thăm dò hoặc kiểm tra từng yếu tố có sẵn
tìm kiếm một vị trí có sẵn.
Và ngay khi bạn tìm thấy một, bạn thả nó ở đó.
>> Bây giờ, giá được trả tiền ngay cho giải pháp này là gì?
Chúng tôi có một mảng kích thước cố định, và khi tôi chèn tên
vào nó, ít nhất ban đầu, những gì thời gian chạy của chèn
để đưa các sinh viên ' câu đố trong xô phải không?
Big O của những gì?
>> Đung n.
DAVID Malan: Tôi nghe nói O lớn của n.
Không đúng sự thật.
Nhưng chúng tôi sẽ trêu chọc nhau tại sao chỉ trong một khoảnh khắc.
Những gì khác nó có thể được?
>> Đung [không nghe được]
DAVID Malan: Và hãy để tôi làm điều đó trực quan.
Vì vậy, giả sử đây là thư S.
>> Đung Đó là một.
DAVID Malan: Đó là một.
Phải không?
Đây là một mảng, mà nghĩa là chúng ta có thể truy cập ngẫu nhiên.
Và nếu chúng ta nghĩ về điều này như bằng không và điều này là 25,
và chúng tôi nhận ra rằng, oh, đây là đầu vào S của tôi,
Tôi chắc chắn có thể chuyển đổi S, một ký tự ASCII,
một số tương ứng giữa số không và 25
và sau đó ngay lập tức đặt nó nơi mà nó thuộc về.
>> Nhưng tất nhiên, ngay sau khi tôi nhận được đến người thứ hai là người tên là A hoặc B hoặc C
cuối cùng, nếu tôi đã sử dụng tuyến tính thăm dò là giải pháp của tôi,
thời gian chạy của chèn trong trường hợp xấu nhất
thực sự là sẽ giao phận sự vào những gì?
Và tôi đã nghe nó ở đây một cách chính xác ngay từ đầu.
Đung [không nghe được]
DAVID Malan: Vì vậy, nó là n thực sự một lần bạn có một bộ dữ liệu đủ lớn.
Vì vậy, một mặt, nếu mảng của bạn là đủ lớn
và dữ liệu của bạn là thưa thớt đủ, bạn có được thời gian này liên tục đẹp.
Nhưng ngay khi bạn bắt đầu nhận được nhiều hơn và nhiều hơn nữa các yếu tố,
và chỉ thống kê bạn nhận được nhiều người bằng chữ
Một khi tên của họ hoặc các thư B, nó có thể có khả năng
giao phận sự vào một cái gì đó nhiều hơn tuyến tính.
Vì vậy, không hoàn toàn hoàn hảo.
Vì vậy, chúng ta có thể làm tốt hơn?
>> Vâng, là những gì chúng tôi giải pháp trước khi chúng tôi
muốn có sự năng động hơn một cái gì đó giống như một mảng cho phép?
Đung [không nghe được]
DAVID Malan: chúng tôi đã giới thiệu gì?
Yeah.
Vì vậy, một danh sách liên kết.
Vâng, chúng ta hãy xem những gì một liên kết danh sách có thể làm cho chúng ta thay thế.
Vâng, hãy để tôi đề xuất rằng chúng ta rút ra những hình ảnh như sau.
Bây giờ đây là một khác nhau hình ảnh từ một ví dụ
từ một văn bản khác nhau, trên thực tế, rằng thực sự là sử dụng một mảng có kích thước 31.
Và tác giả này chỉ đơn giản quyết định băm dây
không dựa trên tên của người đó, nhưng dựa trên ngày sinh của họ.
Không phân biệt của tháng, họ đã hình nếu bạn sinh vào ngày đầu tiên của một tháng
hoặc ngày 31 của một tháng, tác giả sẽ băm dựa trên giá trị đó,
để truyền bá tên ra một chút nhiều hơn chỉ là 26 điểm có thể cho phép.
Và có lẽ đó là một chút đồng đều hơn vì đi với các chữ cái chữ cái,
bởi vì tất nhiên có lẽ nhiều người trên thế giới với tên
mà bắt đầu với A hơn là chắc chắn một số chữ cái khác của bảng chữ cái.
Vì vậy, có lẽ đây là một chút nhiều đồng phục, giả sử
một phân bố đều của trẻ sơ sinh qua một tháng.
>> Nhưng, tất nhiên, điều này vẫn không hoàn hảo.
Phải không?
Chúng tôi đang có va chạm.
Nhiều người trong này cấu trúc dữ liệu vẫn còn
có ngày sinh cùng ít nhất bạn không phân biệt tháng.
Nhưng những gì tác giả đã thực hiện?
Vâng, có vẻ như chúng ta có một mảng ở phía bên tay trái rút ra theo chiều dọc,
nhưng đó chỉ là màn biểu diễn của một nghệ sĩ.
Nó không quan trọng những gì hướng bạn vẽ một mảng, nó vẫn là một mảng.
Đây là những gì một mảng rõ ràng?
>> Đung danh sách liên kết.
>> DAVID Malan: Yeah.
Có vẻ như nó là một mảng các danh sách liên kết.
Vì vậy, một lần nữa, đến thời điểm này của loại của việc sử dụng các cấu trúc dữ liệu doanh nghiệp
như thành phần để hơn giải pháp thú vị,
bạn hoàn toàn có thể mất một cơ bản, giống như một mảng,
và sau đó đi một cái gì đó nhiều hơn thú vị giống như một danh sách liên kết
và thậm chí kết hợp chúng thành một thậm chí cấu trúc dữ liệu thú vị hơn.
Và quả thực, điều này cũng sẽ được gọi là một bảng băm,
trong đó mảng là thực sự là bảng băm,
nhưng mà bảng băm có dây chuyền, có thể nói,
có thể phát triển hoặc thu nhỏ dựa trên số yếu tố mà bạn muốn chèn.
>> Bây giờ, theo đó, những gì thời gian chạy ngay bây giờ?
Nếu tôi muốn chèn một người nào đó có sinh nhật là ngày 31 tháng 10,
nơi nào họ đi đâu?
Được rồi.
Ở dưới cùng, nơi nó nói 31.
Và đó là hoàn hảo.
Đó là thời gian liên tục.
Nhưng nếu chúng ta tìm thấy một người nào khác có ngày sinh nhật được, chúng ta hãy xem,
Tháng mười, tháng mười một, 31 tháng 12?
Ở đâu anh ta hoặc cô sẽ đi đâu?
Cùng một điều.
Hai bước mặc dù.
Đó là không đổi mặc dù không phải là nó?
Được rồi.
Tại thời điểm này nó là.
Nhưng trong trường hợp chung, càng có nhiều người chúng ta thêm,
xác suất, chúng ta sẽ để có được càng nhiều va chạm.
>> Bây giờ đây là một chút tốt hơn bởi vì về mặt kỹ thuật
Hiện tại chuỗi của tôi có thể là trong trường hợp xấu nhất bao lâu?
Nếu tôi chèn n người vào hơn này cấu trúc dữ liệu phức tạp, n người,
trong trường hợp xấu nhất nó sẽ là n.
Tại sao?
>> Đung Bởi vì nếu tất cả mọi người có cùng ngày sinh,
họ sẽ có một dòng.
DAVID Malan: Hoàn hảo.
Nó có thể là một chút giả tạo, nhưng thật sự trong trường hợp xấu nhất,
nếu tất cả mọi người có cùng ngày sinh, cho đầu vào bạn có,
bạn sẽ có một chuỗi dài ồ ạt.
Và như vậy, bạn có thể gọi nó là một băm bảng, nhưng thực sự nó
chỉ là một danh sách liên kết lớn với một toàn bộ rất nhiều không gian lãng phí.
Nhưng nói chung, nếu chúng ta giả định rằng ít nhất là sinh nhật uniform--
và nó có lẽ không phải là.
Tôi đang làm mà lên.
Nhưng nếu chúng ta giả định, cho vì lợi ích của thảo luận
mà họ đang có, thì theo lý thuyết, nếu đây là đại diện dọc
của mảng, cũng sau đó hy vọng bạn sẽ nhận được chuỗi đó là, bạn biết đấy,
khoảng chiều dài tương tự mà mỗi những đại diện cho một ngày trong tháng.
>> Bây giờ nếu có 31 ngày trong tháng, đó có nghĩa là thời gian chạy của tôi thực sự
là O lớn của n hơn 31, mà cảm thấy tốt hơn so với tuyến tính.
Tuy nhiên, là một trong những gì của chúng tôi cam kết một vài tuần
trước bất cứ khi nào nó đến để bày tỏ thời gian chạy của một thuật toán?
Chỉ cần chỉ nhìn vào hạn trật tự cao.
Phải không?
31 chắc chắn là hữu ích.
Nhưng điều này vẫn là O lớn của n.
Nhưng một trong những chủ đề các vấn đề thiết lập năm
là có được để thừa nhận rằng hoàn toàn,
tiệm, về mặt lý thuyết cấu trúc dữ liệu này
là không tốt hơn so với chỉ một danh sách liên kết lớn.
Và quả thực, trong trường hợp xấu nhất, điều này bảng băm có thể giao phận sự vào đó.
>> Nhưng trong thế giới thực, với con người chúng ta rằng máy Mac của riêng hoặc máy tính hoặc bất cứ điều gì
và đang chạy thế giới thực phần mềm trên dữ liệu thế giới thực,
mà thuật toán thì bạn sẽ thích?
Một trong đó thực hiện các bước cuối cùng hoặc các một trong những mất n chia cho 31 bước
để tìm thấy một số mảnh của dữ liệu hoặc để tìm kiếm một số thông tin?
Ý tôi là, hoàn toàn làm cho 31 một sự khác biệt trong thế giới thực.
Nó là nhanh hơn 31 lần.
Và con người chúng ta là chắc chắn sẽ đánh giá cao điều đó.
>> Vì vậy, nhận ra sự phân đôi có giữa thực
nói về những điều lý thuyết và tiệm cận mà chắc chắn
có giá trị như chúng ta đã thấy, nhưng trong thế giới thực,
nếu bạn quan tâm đến chỉ làm cho hạnh phúc của con người cho đầu vào nói chung,
bạn rất có thể muốn chấp nhận thực tế là, có, đây là tuyến tính,
nhưng nó nhanh hơn 31 lần hơn tuyến tính có thể được.
Và tốt hơn, chúng tôi không chỉ phải làm điều gì đó tùy ý giống như một ngày sinh,
chúng tôi có thể dành một chút nhiều thời gian hơn và thông minh
và suy nghĩ về những gì chúng ta có thể làm, đưa ra tên của một người và có thể
ngày sinh của họ để kết hợp những thành phần để tìm ra một cái gì đó
mà thực sự hơn là thống nhất và ít răng cưa,
vậy để nói chuyện hơn hình ảnh này hiện cho thấy nó có thể được.
Làm thế nào chúng ta có thể thực hiện điều này trong mã?
Vâng, hãy để tôi đề xuất rằng chúng ta chỉ mượn một số cú pháp chúng tôi đã
sử dụng một vài lần cho đến nay.
Và tôi sẽ xác định một nút, mà lại
là một thuật ngữ chung chỉ một số container cho một số cấu trúc dữ liệu.
Tôi sẽ đề nghị một chuỗi sẽ ở đó.
Nhưng chúng ta sẽ bắt đầu tham gia đào tạo những bánh xe ra bây giờ.
>> Không có thêm thư viện CS50 thực sự, trừ khi bạn muốn
sử dụng nó cho cuối cùng của bạn dự án, đó là tốt,
nhưng bây giờ chúng ta sẽ kéo lại rèm và nói rằng nó chỉ là một ngôi sao char.
Vì vậy, từ đó là có được tên của người trong câu hỏi.
Và bây giờ tôi có một liên kết ở đây đến nút tiếp theo
do đó, các đại diện mỗi nút
trong chuỗi, có khả năng, của một danh sách liên kết.
>> Và bây giờ làm thế nào để khai báo bảng băm chính nó?
Làm thế nào để khai báo toàn bộ cấu trúc này?
Vâng, thực sự, giống như tôi đã sử dụng một con trỏ để chỉ phần tử đầu tiên của danh sách
trước đó, tương tự như tôi có thể chỉ cần nói Tôi chỉ cần một bó của con trỏ
để thực hiện toàn bộ bảng băm này.
Tôi sẽ có một mảng gọi là bảng cho bảng băm.
Nó sẽ là khả năng kích thước.
Đó là cách nhiều yếu tố có thể phù hợp với nó.
Và mỗi người trong số những yếu tố này trong mảng là có được một ngôi sao nút.
Tại sao?
Vâng, mỗi bức tranh này, những gì tôi thực hiện bảng băm như
hiệu quả trong đầu chỉ là mảng này mà chúng tôi đã rút ra theo chiều dọc,
mỗi người có hình vuông đại diện cho một con trỏ.
Đó là những người có dấu gạch chéo thông qua họ chỉ là null.
Và những người có mũi tên đi bên phải
là con trỏ thực tế để hạch thực tế, vậy thì sự bắt đầu của một danh sách liên kết.
>> Vì vậy, ở đây, sau đó là làm thế nào chúng ta có thể thực hiện một bảng băm
thực hiện xâu chuỗi riêng biệt.
Bây giờ chúng ta có thể làm tốt hơn?
Tất cả các bên phải tôi hứa lần cuối cùng chúng ta có thể đạt được thời gian liên tục.
Và tôi loại cho bạn hằng số thời gian ở đây,
nhưng sau đó cho biết không thực sự thời gian cố định vì nó vẫn còn
phụ thuộc vào tổng số số yếu tố
bạn đang nhập vào cấu trúc dữ liệu.
Nhưng giả sử chúng ta đã làm điều này.
Hãy để tôi quay trở lại màn hình ở đây.
Hãy để tôi cũng dự án này lên đây, rõ ràng màn hình, và cho rằng tôi đã làm điều này.
Giả sử tôi muốn chèn tên Daven trong vào cấu trúc dữ liệu của tôi.
>> Vì vậy, tôi muốn chèn một chuỗi Daven vào cấu trúc dữ liệu.
Nếu tôi không sử dụng một băm bảng, nhưng tôi sử dụng
một cái gì đó nhiều hơn cây giống giống như một cây gia đình, nơi
bạn có một số gốc tại đầu và sau đó các nút và lá
mà đi xuống và ra ngoài.
Giả sử sau đó, tôi thấy muốn chèn Daven của
vào những gì hiện một danh sách trống.
Tôi sẽ làm như sau: Tôi sẽ tạo ra một nút trong gia đình này
cây giống như cấu trúc dữ liệu giống một chút như thế này, mỗi trong số đó
hình chữ nhật đã, chúng ta hãy nói, bây giờ 26 yếu tố trong đó.
Và mỗi người trong các tế bào trong mảng này sẽ
đại diện cho các thư của một bảng chữ cái.
>> Cụ thể, tôi sẽ đối xử đây là A, sau đó B, sau đó C, sau đó D,
này ở đây.
Vì vậy, điều này là có hiệu quả biểu diễn chữ D.
Nhưng để chèn tất cả các Daven của tên tôi cần phải làm nhiều hơn một chút.
Vì vậy, tôi đầu tiên sẽ băm, vậy để nói chuyện.
Tôi sẽ nhìn vào các chữ cái đầu tiên trong của Daven mà rõ ràng là một D,
và tôi sẽ phải phân bổ một nút trông
this-- như một hình chữ nhật lớn lớn đủ để phù hợp với toàn bộ bảng chữ cái.
>> Bây giờ D được thực hiện.
Bây giờ A. D-A-V-E-N là mục tiêu.
Vì vậy, bây giờ những gì tôi sẽ làm được điều này.
Ngay sau khi tôi bắt đầu thông báo D không có con trỏ ở đó.
Đó là giá trị rác tại thời điểm này, hoặc tôi có thể khởi tạo nó thành vô giá trị.
Nhưng hãy để tôi tiếp tục đi với ý tưởng này xây dựng một cây.
Hãy để tôi phân bổ một một trong những các nút có 26 yếu tố trong đó.
>> Và bạn biết gì không?
Nếu đây chỉ là một nút trong bộ nhớ Tôi tạo ra với malloc, sử dụng một cấu trúc
như chúng ta sẽ sớm thấy, Tôi sẽ làm this--
Tôi sẽ vẽ một mũi tên từ điều mà đại diện D xuống
đến nút mới này.
Và bây giờ, lần đầu tiên tiếp theo thư trong tên của Daven,
V-- D-A-V-- tôi sẽ đi trước và vẽ một nút khác như thế này,
theo đó, các yếu tố V ở đây, mà chúng tôi sẽ vẽ cho tả instance--.
Chúng tôi sẽ không rút ra ở đó.
Nó sẽ đi đây.
>> Sau đó chúng ta sẽ coi đây là V.
Và sau đó xuống đây chúng ta sẽ chỉ số xuống từ V vào những gì chúng tôi sẽ xem xét E.
Và rồi từ đây chúng ta sẽ đi có một trong các nút ở đây.
Và bây giờ chúng tôi có một câu hỏi để trả lời.
Tôi cần phải bằng cách nào đó chỉ ra rằng chúng ta đang ở cuối của chuỗi Daven.
Vì vậy, tôi chỉ có thể để nó null.
>> Nhưng nếu chúng ta có Daven của tên đầy đủ cũng có, mà
là, như chúng ta đã nói, Davenport?
Vì vậy, nếu Daven là những gì thực sự là một chuỗi con,
một tiền tố của một chuỗi dài hơn nhiều?
Chúng ta không thể chỉ vĩnh viễn nói gì đang xảy ra
đến đó, bởi vì chúng tôi có thể không bao giờ chèn một từ như Davenport
vào cấu trúc dữ liệu này
>> Vì vậy, những gì chúng ta có thể làm thay vào đó là đối xử với nhau của các yếu tố
như có thể có hai các yếu tố bên trong của họ.
Một là một con trỏ, thực sự, như tôi đã làm.
Vì vậy, mỗi người trong các hộp không chỉ là một tế bào.
Nhưng nếu đầu one-- một đáy của
sẽ là vô giá trị, bởi vì không có Davenport chỉ được nêu ra.
Điều gì nếu một trong những đầu là một số giá trị đặc biệt không?
Và nó sẽ là một chút khó có thể rút ra nó kích thước này.
Nhưng giả sử nó chỉ là một dấu.
Kiểm tra.
D-A-V-E-N là một chuỗi trong cấu trúc dữ liệu này.
>> Trong khi đó, nếu tôi đã có nhiều không gian hơn ở đây, tôi có thể làm P-O-R-T,
và tôi có thể đặt kiểm tra trong các nút có chữ T ở cuối.
Vì vậy, đây là một cách ồ ạt phức tạp, tìm kiếm cấu trúc dữ liệu.
Và chữ viết tay của tôi chắc chắn không giúp đỡ.
Nhưng nếu tôi muốn chèn một cái gì đó khác, hãy xem xét những gì chúng ta sẽ làm gì.
Nếu chúng ta muốn đưa David trong, chúng tôi theo cùng một logic, D-A-V,
nhưng bây giờ tôi sẽ chỉ ở bên cạnh yếu tố không phải từ E, nhưng từ I đến D.
Vì vậy, sẽ là các nút hơn trong cây này.
Chúng tôi sẽ có cuộc gọi malloc hơn.
Nhưng tôi không muốn thực hiện một mess hoàn thành các hình ảnh này.
Vì vậy, hãy thay vì nhìn vào một đó là được xây dựng trước
như thế này với không chấm, dấu chấm, dấu chấm, nhưng mảng chỉ viết tắt.
Nhưng mỗi nút trong cây này ở đây
đại diện cho thing-- cùng một mảng Ray kích thước 26.
>> Hoặc nếu chúng ta muốn có thực sự thích hợp bây giờ, những gì
nếu tên của một ai đó như một dấu nháy đơn, chúng ta hãy
giả sử rằng mỗi nút thực sự có như 27 chỉ số trong nó, không chỉ 26.
Vì vậy, điều này bây giờ là có được một dữ liệu cấu trúc được gọi là một trie-- T-R-I-E.
Một Trie, mà được cho là lịch sử là một tên thông minh cho một cây
đó là tối ưu hóa cho thu hồi, trong đó tất nhiên,
được viết với chữ I-E vì vậy nó Trie.
Nhưng đó là lịch sử của Trie.
>> Vì vậy, một Trie là dữ liệu cây như thế này cấu trúc giống như một cây gia đình
mà cuối cùng cư xử như thế.
Và đây chỉ là một ví dụ về một bó toàn bộ các tên của người khác.
Tuy nhiên, câu hỏi bây giờ ở bàn tay là những gì có
chúng tôi đã đạt được bằng cách giới thiệu cho là một nhiều hơn cấu trúc dữ liệu phức tạp, và một,
thẳng thắn, có sử dụng rất nhiều bộ nhớ.
>> Bởi vì mặc dù, tại thời điểm này, tôi chỉ là
sử dụng con trỏ D's và A và V và Es và Ns,
Tôi đang lãng phí một heck của rất nhiều bộ nhớ.
Nhưng mà tôi dành một nguồn tài nguyên, Tôi có xu hướng để làm được lại khác.
Vì vậy, nếu tôi là chi tiêu nhiều không gian hơn, những gì có thể là hy vọng?
Mà tôi đang chi tiêu ít hơn những gì?
Đung Ít thời gian.
DAVID Malan: Time.
Bây giờ tại sao điều đó có thể được?
Vâng, chèn là những gì thời gian, trong điều khoản của O lớn bây giờ,
của một tên như Daven hoặc Davenport hay David?
Vâng, Daven là năm bước.
Davenport sẽ là chín bước, do đó, nó sẽ là một vài bước nữa.
David sẽ là năm bước là tốt.
Vì vậy, những người đang có bê tông con số, nhưng chắc chắn có
một trên ràng buộc về chiều dài của tên của một ai đó.
Và quả thực, trong các vấn đề bộ năm đặc điểm kỹ thuật,
chúng tôi sẽ đề xuất rằng đó là một cái gì đó
đó là nhân vật 40-một số lẻ.
>> Thực tế, không ai có một cái tên dài vô hạn,
mà là để nói rằng độ dài của một tên hoặc chiều dài của một chuỗi chúng ta có thể
có một số trạng thái của cấu trúc được cho là những gì?
Đó là không đổi.
Phải không?
Nó có thể là một hằng số lớn như 40-một cái gì đó, nhưng nó là hằng số.
Và nó không có sự phụ thuộc vào bao nhiêu tên khác là trong cấu trúc dữ liệu này.
Nói cách khác, nếu tôi muốn đến nay chèn
Colton hoặc Gabriel hoặc Rob hoặc Zamyla hoặc Alison hoặc Belinda hoặc bất kỳ tên khác
từ các nhân viên vào dữ liệu này cấu trúc, là thời gian chạy
chèn tên khác sẽ có mặt tại tất cả các ảnh hưởng
bởi có bao nhiêu nguyên tố khác trong cấu trúc dữ liệu chưa?
Nó không phải.
Phải không?
Bởi vì chúng ta đang sử dụng có hiệu quả nhiều lớp băm bảng này.
Và thời gian chạy của bất kỳ của các hoạt động này
không phụ thuộc vào số lượng các yếu tố có trong cấu trúc dữ liệu
hoặc được cuối cùng sẽ được trong cấu trúc dữ liệu,
nhưng về độ dài của những gì cụ thể?
>> Chuỗi là đưa vào, mà không làm
tiệm này liên tục time-- O lớn của một.
Và thẳng thắn mà nói, chỉ trong thế giới thực, điều này
có nghĩa là chèn tên của Daven mất như năm bước, hoặc Davenport chín
bước, hoặc David năm bước.
Đó là khá darn lần chạy nhỏ.
Và, thực sự, đó là một rất điều tốt, đặc biệt là khi
nó không phụ thuộc vào tổng số số yếu tố trong đó.
Vậy làm thế nào chúng ta có thể thực hiện điều này loại cấu trúc trong mã?
Đó là nhiều hơn một chút phức tạp, nhưng vẫn còn đó
chỉ là một ứng dụng của khối xây dựng cơ bản.
Tôi sẽ xác định lại nút chúng tôi như sau:
bool gọi word-- và điều này có thể được gọi là bất cứ điều gì.
Nhưng bool đại diện những gì tôi đã thu hút như một dấu.
Vâng.
Đây là phần cuối của một chuỗi trong cấu trúc dữ liệu này.
>> Và, tất nhiên, ngôi sao nút có được đề cập đến trẻ em.
Và, thực sự, giống như một cây gia đình, bạn
sẽ xem xét các nút được treo tắt
dưới cùng của một số cha mẹ yếu tố là trẻ em.
Và do đó trẻ em sẽ là một mảng của 27, một 27
chỉ là cho dấu nháy đơn.
Chúng tôi sẽ sắp xếp các trường hợp đặc biệt.
Vì vậy, bạn có thể có một số tên với dấu nháy.
Thậm chí có dấu gạch ngang nên đi ở đó, nhưng bạn sẽ
nhìn thấy trong p tập 5 chúng ta chỉ chăm sóc về chữ cái và dấu nháy.
>> Và sau đó làm thế nào để bạn đại diện cấu trúc dữ liệu riêng của mình?
Làm thế nào để bạn đại diện gốc của Trie này, vì vậy để nói chuyện?
Vâng, giống như với một danh sách liên kết, bạn cần một con trỏ đến phần tử đầu tiên.
Với một Trie bạn chỉ cần một con trỏ vào thư mục gốc của Trie này.
Và từ đó bạn có thể băm cách của bạn xuống sâu hơn và sâu hơn
để tất cả các nút khác trong cấu trúc.
Vì vậy, chỉ đơn giản với can này chúng tôi đại diện cho cấu trúc đó.
>> Bây giờ Meanwhile-- Oh, câu hỏi.
>> Đung từ bool là gì?
>> DAVID Malan: Từ Bool là chỉ hóa thân C này
những gì tôi mô tả trong hộp này đây, khi
Tôi bắt đầu chia mỗi các yếu tố của mảng thành hai mảnh.
Một là một con trỏ đến nút tiếp theo.
Các khác có được một cái gì đó giống như một hộp kiểm tra
nói có, có một từ Daven kết thúc ở đây,
bởi vì chúng tôi không muốn, tại thời điểm này, Dave.
>> Mặc dù Dave là có được một từ hợp pháp, ông không phải trong Trie
được nêu ra.
Và D không phải là một từ.
Và D-A không phải là một từ hoặc một tên.
Vì vậy, các dấu kiểm chỉ một lần duy nhất bạn
nhấn nút này là con đường trước đây của nhân vật
thực sự là một chuỗi mà bạn đã chèn.
Vì vậy, đó là tất cả các bool có được làm cho chúng ta.
>> Bất kỳ câu hỏi khác trên cố gắng?
Yeah.
>> Đung sự chồng chéo là gì?
Điều gì nếu bạn có một Dave và Daven?
DAVID Malan: Hoàn hảo.
Điều gì nếu bạn có một Dave và Daven?
Vì vậy, nếu chúng ta chèn, nói một biệt danh, cho David-- Dave-- D-A-V-E?
Đây thực sự là siêu đơn giản.
Vì vậy, chúng tôi sẽ chỉ mất bốn bước.
D-A-V-E. Và tôi có những gì để làm một lần tôi nhấn nút đó thứ tư?
Chỉ cần đi kiểm tra.
Chúng tôi đã tốt để đi.
Xong.
Bốn bước.
Thời gian cố định tiệm cận.
Và bây giờ chúng tôi đã chỉ ra rằng cả hai Dave và Daven là chuỗi trong cấu trúc.
Vì vậy, không phải là một vấn đề.
Và chú ý sự hiện diện của Daven không làm cho nó
có bất kỳ nhiều thời gian hơn hoặc ít hơn thời gian cho Dave và ngược lại.
>> Vì vậy, những gì khác chúng tôi bây giờ có thể làm gì?
Chúng tôi đã sử dụng phép ẩn dụ này trước khi khay đại diện cho một cái gì đó.
Nhưng nó chỉ ra rằng một chồng khay thực sự là
chứng minh của một dữ liệu trừu tượng type-- một cấu trúc dữ liệu cấp độ cao hơn
là lúc kết thúc ngày chỉ là giống như một mảng hoặc một danh sách liên kết
hoặc một cái gì đó trần tục hơn.
Nhưng đó là một thú vị hơn khái niệm khái niệm.
Một stack, như thế này khay ở đây trong Mather,
thường được gọi là chỉ that-- một chồng.
>> Và trong loại cấu trúc dữ liệu bạn có hai operations--
bạn có một gọi là thúc đẩy thêm một cái gì đó để ngăn xếp,
giống như đặt khay khác sao trên đỉnh của stack.
Và sau đó bật, có nghĩa là bạn lấy khay ra trên cùng.
Nhưng điều quan trọng về một chồng là nó có đặc tính tò mò này.
Khi các nhân viên phòng ăn là sắp xếp lại các khay cho bữa ăn tiếp theo,
những gì sẽ là đúng về cách sinh viên
tương tác với các cấu trúc dữ liệu này?
Đung Họ sẽ bật một off.
DAVID Malan: Họ sẽ bật một tắt, hy vọng hàng đầu.
Nếu không nó chỉ là ngu ngốc đi tất cả các cách để phía dưới.
Phải không?
Cấu trúc dữ liệu không thực sự cho phép bạn để lấy các khay dưới cùng ít nhất
một cách dễ dàng.
Vì vậy, có tò mò này tài sản để một chồng
rằng mục cuối cùng trong là sẽ là một trong ra ngoài đầu tiên.
Và các nhà khoa học máy tính gọi LIFO-- này kéo dài, ra trước.
Và nó thực sự không có ứng dụng thú vị.
Nó không nhất thiết phải rõ ràng như một số những người khác, nhưng nó có thể, thực sự, có ích,
và nó có thể, thực sự, được thực hiện trong một vài cách khác nhau.
>> Vì vậy, một, và thực sự, chúng ta hãy tôi không đi sâu vào đó.
Hãy làm điều này để thay thế.
Hãy nhìn vào một trong đó là gần như cùng một ý tưởng, nhưng đó là một chút công bằng hơn.
Phải không?
Nếu bạn là một trong những chàng trai fan hâm mộ hoặc cô gái đó thực sự thích sản phẩm của Apple
và bạn tỉnh dậy vào lúc 03:00 để xếp hàng tại một số cửa hàng
để có được iPhone mới nhất, bạn có thể xếp hàng như thế này.
>> Bây giờ một hàng đợi rất cố tình đặt tên.
Đó là một đường bởi vì có một số sự công bằng cho nó.
Phải không?
Nó sẽ loại hút nếu bạn đã đã có đầu tiên tại Apple Store
nhưng bạn có hiệu quả dưới cùng khay vì các nhân viên của Apple sau đó
bật người cuối cùng thực sự đã phù hợp.
Vì vậy, ngăn xếp và hàng đợi, mặc dù chức năng họ đang loại các same--
nó chỉ là bộ sưu tập này các nguồn lực đó là
sẽ phát triển và shrink-- có của khía cạnh công bằng này với nó,
ít nhất là trong thế giới thực, nơi mà các hoạt động tập thể dục
về cơ bản là khác nhau.
Một stack-- một hàng đợi rather-- được cho là có
hai hoạt động: n hàng đợi và d hàng đợi.
Hoặc bạn có thể gọi cho họ bất kỳ số lượng của sự vật.
Nhưng bạn chỉ muốn chụp quan điểm cho rằng một là thêm
và là một trong những cuối cùng trừ.
>> Bây giờ bên dưới mui xe, cả hai stack và một hàng đợi có thể được thực hiện như thế nào?
Chúng tôi sẽ không đi vào mã của nó bởi vì mức độ cao hơn
ý tưởng là loại rõ ràng hơn.
Tôi có nghĩa là, những gì con người làm gì?
Nếu tôi là người đầu tiên tại Apple Lưu trữ và đây là cửa trước,
bạn đã biết, tôi sẽ đứng ở đây.
Và người kế tiếp của sẽ đứng ở đây.
Vì vậy, những gì cấu trúc dữ liệu vay chính nó để một hàng đợi?
>> Đung Một hàng đợi.
DAVID Malan: Vâng, một hàng đợi.
Chắc chắn.
Những gì khác?
>> Đung Một danh sách liên kết.
>> DAVID Malan: Một liên kết danh sách bạn có thể thực hiện.
Và một danh sách liên kết là tốt đẹp vì sau đó nó có thể phát triển tùy tiện dài như trái ngược
để có một số cố định người trong cửa hàng.
Nhưng có lẽ một số cố định nơi là hợp pháp.
Bởi vì nếu họ chỉ có như 20 iPhone vào ngày đầu tiên, có thể
họ chỉ cần một mảng có kích thước 20 đại diện cho rằng hàng đợi, mà
chỉ để nói bây giờ khi chúng tôi bắt đầu nói chuyện về những vấn đề cấp cao hơn,
bạn có thể thực hiện nó trong bất kỳ số cách.
Và có lẽ chỉ cần đi là một thương mại giảm trong không gian và thời gian
hoặc chỉ phức tạp mã riêng của bạn.
>> Những gì về một chồng?
Vâng, một chồng, chúng tôi đã nhìn thấy quá chỉ có thể là những khay.
Và bạn có thể thực hiện điều này một mảng.
Tuy nhiên, tại một số điểm nếu bạn sử dụng một mảng, những gì sẽ xảy ra với các khay
bạn đang cố gắng để đặt xuống?
Được rồi.
Bạn sẽ chỉ có thể đi quá cao.
Và tôi nghĩ rằng trong Mather họ thực sự lõm trong việc mở cửa đó.
Vì vậy, thực sự, nó gần như như Mather đang sử dụng
một mảng có kích thước cố định, bởi vì bạn chỉ có thể
phù hợp với rất nhiều khay trong đó mở cửa trong tường xuống dưới đầu gối của người dân.
Và do đó có thể cho là một mảng,
nhưng chúng tôi chắc chắn có thể thực hiện điều đó nói chung với một danh sách liên kết.
>> Vâng, những gì về cấu trúc dữ liệu khác?
Hãy để tôi kéo lên một hình ảnh khác ở đây.
Một cái gì đó như thế nào về việc này ở đây?
Tại sao nó có thể là hữu ích để có không một cái gì đó là ưa thích như một Trie, mà
chúng tôi đã thấy có các nút này rất rộng, mỗi trong số đó là trong một mảng?
Nhưng nếu chúng ta làm điều gì đó nhiều hơn đơn giản, giống như một cây gia đình trường học cũ,
từng có các nút ở đây chỉ là lưu trữ một số.
Thay vì một tên hoặc một hậu duệ chỉ là lưu trữ một số lượng như thế này.
>> Vâng, các thuật ngữ chúng tôi sử dụng trong cấu trúc dữ liệu là cả hai cố gắng
và cây, nơi một Trie, một lần nữa, là chỉ một mà các nút là mảng,
vẫn là những gì bạn có thể sử dụng từ trường lớp
khi bạn đã thực hiện một gia đình tree-- lá và gốc
của cây và trẻ em của cha mẹ và anh chị em biết.
Và chúng ta có thể thực hiện một cây, Ví dụ như chỉ đơn giản như thế này.
Một cây, nếu nó như là một nút, một trong những những vòng tròn này có một số,
nó sẽ không có một con trỏ, nhưng hai.
Và ngay khi bạn thêm một con trỏ thứ hai, bạn
thực sự bây giờ có thể làm cho loại dữ liệu hai chiều
cấu trúc trong bộ nhớ.
Giống như một hai chiều mảng, bạn có thể
có loại hai chiều danh sách liên kết, nhưng những người
mà theo một mô hình nơi không có chu kỳ.
Đó thực sự là một cái cây với một cách ông bà lên ở đây và sau đó
một số phụ huynh và trẻ em và cháu và chắt.
và vv.
>> Nhưng những gì thực sự gọn gàng về việc này quá, chỉ để trêu chọc bạn với một chút mã,
thu hồi đệ quy từ một thời gian trở lại, nhờ đó mà
bạn viết một chức năng mà tự gọi mình.
Đây là một cơ hội đẹp để thực hiện một cái gì đó
như đệ quy, bởi vì xem xét việc này.
>> Đây là một cây.
Và tôi đã được một hậu môn nhỏ với cách Tôi đặt các số nguyên vào các đường phố.
Vì vậy, nhiều như vậy mà nó có một đặc biệt name-- một cây tìm kiếm nhị phân.
Bây giờ chúng ta đã nghe nói về nhị phân tìm kiếm, nhưng có thể bạn
làm việc ngược từ tên của điều này?
Mô hình như thế nào tôi là gì chèn các số nguyên vào cây này?
Đó không phải là tùy ý.
Có một số mô hình.
Yeah.
>> Đung những người nhỏ hơn ở bên trái.
>> DAVID Malan: Yeah.
Những cái nhỏ hơn là bên trái.
Những người lớn hơn là ở bên phải.
Như vậy mà một tuyên bố đúng là một cha mẹ là lớn hơn con trái của nó,
nhưng ít hơn con phải của nó.
Và rằng một mình là ngay cả một định nghĩa bằng lời nói đệ quy
bởi vì bạn có thể áp dụng được cùng một logic để tất cả các nút
và nó chỉ có đáy ra, một trường hợp cơ sở nếu bạn
sẽ, khi bạn nhấn một trong lá, có thể nói,
nơi nghỉ không có con nữa.
>> Bây giờ làm thế nào bạn có thể tìm thấy các số 44?
Bạn sẽ bắt đầu ở gốc và nói, hm.
55 không phải là 44 Vì vậy, tôi muốn đi đúng hay tôi muốn đi sang trái?
Vâng, rõ ràng là bạn muốn đi bên trái.
Và do đó, nó chỉ giống như điện thoại Ví dụ trong cuốn sách tìm kiếm nhị phân
nói chung.
Nhưng chúng tôi đang thực hiện nó bây giờ là một ít năng động hơn
là một mảng có thể cho phép.
Và trong thực tế, nếu bạn muốn tìm vào mã, ở cái nhìn đầu tiên chắc chắn.
Nó trông giống như một bó toàn bộ các dòng.
Nhưng nó đẹp đơn giản.
Nếu bạn muốn thực hiện một chức năng được gọi là tìm kiếm có mục đích trong cuộc sống
là để tìm kiếm một giá trị như n, một số nguyên,
và bạn đang thông qua trong một pointer-- một con trỏ đến nút của rễ,
đúng hơn, của cây mà từ đó bạn có thể truy cập vào tất cả mọi thứ khác,
thông báo một cách thẳng thắn bạn có thể thực hiện logic.
Nếu cây là null, rõ ràng là nó không có ở đó.
Hãy chỉ trả về false.
Phải không?
Nếu bạn đưa nó không có gì, không có gì có.
>> Khác, nếu n là ít hơn cây mũi tên n-- tại mũi tên n,
nhớ lại chúng tôi giới thiệu siêu một thời gian ngắn ngày khác,
và điều đó chỉ có nghĩa là de-tham khảo con trỏ và nhìn vào các lĩnh vực được gọi là n.
Vì vậy, nó có nghĩa là đi đến đó và nhìn vào các lĩnh vực được gọi là n.
Vì vậy, nếu n, giá trị mà bạn đang đưa ra, ít hơn giá trị trong số nguyên cây,
nơi nào bạn muốn đi đâu?
Về bên trái.
>> Vì vậy, chú ý đến đệ quy.
Tôi returning-- không đúng sự thật.
Không sai.
Tôi trở lại bất cứ câu trả lời là từ một cuộc gọi đến bản thân mình, đi qua
một n một lần nữa, đó là không cần thiết, nhưng những gì hơi khác nhau bây giờ?
Làm thế nào tôi làm cho vấn đề nhỏ hơn?
Tôi đang đi qua trong khi thứ hai đối số, không phải là gốc của cây,
nhưng con trái trong trường hợp này.
Vì vậy, tôi đi qua trong con trái.
>> Trong khi đó, nếu n lớn hơn nút tôi hiện đang xem xét,
Tôi tìm kiếm phía bên tay phải.
Khác, nếu cây không phải là null, và nếu các yếu tố không phải sang trái
và nó không phải bên phải, những gì là tuyệt vời như vậy?
Chúng tôi đã thực sự tìm thấy các nút trong câu hỏi, và vì vậy chúng tôi trở thành sự thật.
>> Vì vậy, chúng tôi đã chỉ trầy xước bề mặt bây giờ một số các cấu trúc dữ liệu.
Trong vấn đề thiết lập năm bạn sẽ thấy khám phá những chưa thêm,
và bạn sẽ được đưa ra thiết kế của bạn lựa chọn thế nào để đi về việc này.
Những gì tôi muốn kết luận về chỉ là một lời trêu ghẹo thứ hai 30
về những gì đang chờ đợi vào tuần tới và xa hơn nữa.
>> Như chúng ta begin-- may mắn bạn có thể think-- quá trình chuyển đổi của chúng tôi từ từ
từ thế giới của C và thấp hơn chi tiết quá trình thực hiện,
đến một thế giới mà chúng ta có thể cho cấp mà người khác có cuối cùng
thực hiện các dữ liệu cấu trúc cho chúng ta,
và chúng ta sẽ bắt đầu hiểu được thế giới thực có nghĩa là thực hiện
các chương trình dựa trên web và các trang web nói chung
và cũng là an ninh rất hàm ý rằng chúng tôi chỉ đã
bắt đầu làm xước bề mặt.
Đây là những gì chờ đợi chúng ta trong những ngày tới.
>> [VIDEO PLAYBACK]
>> -Anh Đi kèm với một tin nhắn, với một giao thức tất cả của riêng mình.
Ông đã đến một thế giới tàn nhẫn tường lửa, router không quan tâm,
và nguy hiểm tồi tệ hơn cả cái chết.
Ông nhanh chóng.
Anh ấy mạnh mẽ.
Anh ấy là TCP / IP, và ông đã nhận địa chỉ của bạn.
"Warriors of the Net".
[END Video PLAYBACK]
DAVID Malan: Đến tuần tiếp theo.
Chúng tôi sẽ nhìn thấy bạn sau đó.
[VIDEO PLAYBACK]
-Và Bây giờ, "Suy nghĩ sâu" bởi Daven Farnham.
-David Luôn luôn bắt đầu các bài giảng với, "Được rồi."
Tại sao không, "Đây là giải pháp cho vấn đề thiết lập trong tuần này "
hoặc "Chúng tôi đang đem lại cho tất cả các bạn một A?"
[Cười]
[END Video PLAYBACK]