>> SPEAKER 1: Được rồi, vì vậy chúng tôi đang trở lại.
Chào mừng bạn đến CS50.
Đây là phần cuối của tuần bảy.
Vì vậy, nhớ lại rằng thời gian qua, chúng tôi bắt đầu nhìn hơi phức tạp hơn
cấu trúc dữ liệu.
Vì cho đến bây giờ, tất cả chúng tôi đã thực sự lúc xử lý của chúng tôi là điều này, một mảng.
>> Nhưng trước khi chúng tôi loại bỏ các mảng như không tất cả những gì thú vị, mà thực sự nó
thực sự là, những gì một số các Điểm cộng của dữ liệu đơn giản này
cấu trúc cho đến nay?
Nó tốt là những gì?
Cho đến nay như chúng ta đã thấy?
Làm những gì bạn có?
Không có gì.
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Cái gì thế?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: cố định kích thước.
OK, vậy tại sao kích thước cố định tốt mặc dù?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: OK, vì vậy hiệu quả trong nghĩa là bạn có thể phân bổ một
số tiền cố định của không gian, mà hy vọng là chính xác như nhiều
không gian như bạn muốn.
Do đó có thể được hoàn toàn một cộng.
>> Một mặt khác lên của một mảng là những gì?
Yeah?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Tất cả các - xin lỗi?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Tất cả các ô trong bộ nhớ hoặc bên cạnh nhau.
Và đó là hữu ích - lý do tại sao?
Đó là hoàn toàn đúng.
Nhưng làm thế nào chúng ta có thể khai thác sự thật đó?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Chính xác, chúng tôi có thể theo dõi nơi mà mọi thứ chỉ bằng cách biết
một địa chỉ, cụ thể là địa chỉ của byte đầu tiên là đoạn bộ nhớ.
Hoặc trong trường hợp của chuỗi, địa chỉ đầu tiên
char trong chuỗi.
Và từ đó, chúng ta có thể tìm thấy kết thúc của chuỗi.
Chúng ta có thể tìm các phần tử thứ hai, Yếu tố thứ ba, và vv.
>> Và do đó, cách ưa thích của mô tả đó tính năng là mảng cung cấp cho chúng tôi
truy cập ngẫu nhiên.
Chỉ bằng cách sử dụng khung vuông ký hiệu và một số, bạn có thể nhảy
một yếu tố cụ thể trong mảng trong thời gian liên tục, lớn O
một, vậy để nói chuyện.
>> Nhưng có được một số nhược điểm.
Thật là một mảng không làm một cách dễ dàng?
Đó là những gì không tốt?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Cái gì thế?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Mở rộng quy mô.
Vì vậy, những nhược điểm của mảng là chính xác với những gì mà các
mặt tích cực là.
Vì vậy, một trong những nhược điểm là rằng đó là một kích thước cố định.
Vì vậy, bạn có thể không thực sự phát triển nó.
Bạn có thể tái phân bổ một phần lớn của bộ nhớ, và sau đó di chuyển các yếu tố cũ
vào mảng mới.
Và sau đó tự do mảng cũ, cho Ví dụ, bằng cách sử dụng malloc hoặc tương tự
chức năng gọi là realloc, mà reallocates bộ nhớ.
>> Realloc, như một sang một bên, cố gắng để cung cấp cho bạn bộ nhớ đó là bên cạnh mảng
mà bạn đã có.
Nhưng nó có thể di chuyển mọi thứ xung quanh hoàn toàn.
Nhưng trong ngắn hạn, đó là đắt tiền, phải không?
Bởi vì nếu bạn có một đoạn bộ nhớ của kích thước này, nhưng bạn thực sự muốn một
kích thước này, và bạn muốn giữ lại các yếu tố nguyên gốc, bạn có
khoảng một tuyến tính quá trình sao chép thời gian mà cần phải xảy ra từ
mảng cũ sang mới.
Và thực tế là yêu cầu điều hành hệ thống một lần nữa và một lần nữa và
một lần nữa cho khối lớn của bộ nhớ có thể bắt đầu chi phí cho bạn một số thời gian là tốt.
Vì vậy, nó là cả một phước lành và một lời nguyền trong che giấu, thực tế là các mảng
có kích thước cố định.
Nhưng nếu chúng tôi giới thiệu thay vì một cái gì đó như thế này, mà chúng tôi gọi là một liên kết
danh sách, chúng tôi có được một vài mặt tích cực và một vài nhược điểm ở đây là tốt.
>> Vì vậy, một danh sách liên kết đơn giản chỉ là một dữ liệu cấu trúc tạo thành cấu trúc của C trong này
trường hợp, trong đó một cấu trúc, thu hồi, chỉ là một container cho một hoặc nhiều cụ thể
loại biến.
Trong trường hợp này, điều gì làm các kiểu dữ liệu xuất hiện để được bên trong các cấu trúc mà
Lần cuối cùng chúng tôi được gọi là một nút?
Mỗi một trong các hình chữ nhật là một nút.
Và mỗi hình chữ nhật nhỏ hơn bên trong của nó là một loại dữ liệu.
Những loại nào chúng ta nói họ vào thứ hai?
Yeah?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Một biến và một con trỏ, hoặc cụ thể hơn, một int, cho n,
và một con trỏ ở phía dưới.
Cả hai của những xảy ra được 32 bit, tại ít nhất là trên một máy tính như CS50 này
Thiết bị, và vì thế chúng rút ra như nhau trong kích thước.
>> Vì vậy, những gì đang sử dụng con trỏ mặc dù cho rõ ràng?
Tại sao lại thêm mũi tên này bây giờ khi mảng là như vậy tốt đẹp và sạch sẽ và đơn giản?
Là con trỏ làm những gì cho chúng tôi trong mỗi một nút?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Chính xác.
Nó nói cho bạn nơi một kế tiếp.
Vì vậy, tôi loại sử dụng sự tương tự của sử dụng một sợi để sắp xếp của
sợi các nút với nhau.
Và đó chính xác là những gì chúng tôi đang làm với con trỏ vì mỗi
khối của bộ nhớ có thể có hoặc có thể không tiếp giáp lãnh hải, trở lại trở lại để trở lại
trong bộ nhớ RAM, bởi vì mỗi khi bạn gọi malloc nói, cho tôi đủ
byte cho một nút mới, nó có thể ở đây hoặc nó có thể là đây.
Nó có thể là đây.
Bạn chỉ không biết.
>> Nhưng sử dụng con trỏ trong các địa chỉ của các nút, bạn có thể ghép chúng
với nhau một cách trông trực quan như một danh sách ngay cả khi những điều này là
tất cả các trải ra khắp một hoặc hai hoặc bốn GB bộ nhớ RAM của bạn
bên trong máy tính của riêng bạn.
>> Vì vậy, các nhược điểm, sau đó, một danh sách liên kết là gì?
Một mức giá chúng tôi là những gì dường như trả tiền?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: thêm không gian, phải không?
Chúng tôi, trong trường hợp này, tăng gấp đôi số tiền của không gian bởi vì chúng tôi đã đi
từ 32 bit cho mỗi nút, cho mỗi int, vì vậy bây giờ 64 bit bởi vì chúng ta phải
giữ xung quanh một con trỏ là tốt.
Bạn sẽ có được hiệu quả hơn nếu cấu trúc của bạn lớn hơn điều này đơn giản.
Nếu bạn thực sự có một sinh viên trong trong số đó là một vài dây cho
tên và ngôi nhà, có thể một số ID, có thể một số lĩnh vực khác hoàn toàn.
>> Vì vậy, nếu bạn có một cấu trúc đủ lớn, thì có lẽ chi phí của con trỏ
không phải là một việc lớn như vậy.
Đây là một chút của một trường hợp góc trong đó chúng tôi đang lưu trữ như một nguyên thủy đơn giản
bên trong các danh sách liên kết.
Nhưng điểm là như nhau.
Bạn chắc chắn chi tiêu nhiều hơn bộ nhớ, nhưng bạn đang nhận được
linh hoạt.
Bởi vì bây giờ nếu tôi muốn thêm một yếu tố ở đầu danh sách này,
Tôi cần phải phân bổ một nút mới.
Và tôi có phải chỉ cần cập nhật những mũi tên bằng cách nào đó bằng cách di chuyển
một số điểm xung quanh.
>> Nếu tôi muốn chèn một cái gì đó vào giữa danh sách, tôi không cần phải
đẩy sang một bên tất cả mọi người như chúng tôi đã làm trong qua tuần với các tình nguyện viên người
đại diện một mảng.
Tôi chỉ có thể phân bổ một nút mới và sau đó chỉ cần chỉ mũi tên trong
hướng khác nhau bởi vì nó không phải duy trì trong thực tế
bộ nhớ một dòng đúng như tôi đã rút ra nó ở đây trên màn hình.
>> Và sau đó cuối cùng, nếu bạn muốn chèn một cái gì đó vào cuối danh sách, đó là
thậm chí còn dễ dàng hơn.
Đây là loại ký hiệu tùy ý, nhưng con trỏ 34 của, hãy đoán.
Giá trị của con trỏ của nó nhất là những gì thể loại vẽ giống như một tuổi
ăng ten trường đó?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Đây có thể là vô giá trị.
Và quả thật đó là một trong những tác giả của đại diện của null.
Và nó là vô giá trị bởi vì bạn hoàn toàn cần phải biết nơi kết thúc của một liên kết
danh sách là, vì sợ rằng bạn giữ sau và sau và làm theo các mũi tên
một số giá trị rác.
Vì vậy, vô giá trị sẽ có nghĩa rằng không có các nút hơn ở bên phải của số 34,
trong trường hợp này.
>> Vì vậy, chúng tôi đề xuất rằng chúng ta có thể thực hiện nút này trong mã.
Và chúng tôi đã nhìn thấy loại cú pháp trước.
Typedef chỉ định nghĩa một kiểu mới chúng ta, cho chúng ta một từ đồng nghĩa như
chuỗi là cho char *.
Trong trường hợp này, nó sẽ cung cấp cho chúng tôi viết tắt ký hiệu để nút cấu trúc
có thể thay vì chỉ được viết như nút, đó là rất nhiều bụi.
Đó là rất nhiều ít tiết.
>> Bên trong của một nút là rõ ràng một int gọi là n, và sau đó một cấu trúc nút *
có nghĩa là chính xác những gì chúng ta muốn mũi tên có nghĩa là, một con trỏ đến một
nút của các kiểu dữ liệu chính xác.
Và nghĩ rằng mình có thể thực hiện một chức năng tìm kiếm như thế này, tại
Thoạt nhìn có vẻ một chút phức tạp.
Nhưng chúng ta hãy xem nó trong ngữ cảnh.
>> Hãy để tôi đi qua để thiết bị ở đây.
Hãy để tôi mở ra một tập tin gọi là danh sách không chấm h.
Và rằng chỉ có các định nghĩa chúng tôi chỉ thấy một thời điểm trước đây cho dữ liệu này
loại được gọi là một nút.
Vì vậy, chúng tôi đã đặt đó vào một tập tin chấm h.
>> Và như một sang một bên, mặc dù điều này chương trình mà bạn đang về để xem là
không tất cả những gì phức tạp, nó thực sự ước khi viết một chương trình để
đặt những thứ như các loại dữ liệu, để kéo hằng số đôi khi, bên trong của bạn
tập tin tiêu đề và không nhất thiết phải trong tập tin C của bạn, chắc chắn khi bạn
các chương trình lớn hơn và lớn hơn, do đó bạn biết nơi để tìm cho cả hai
tài liệu hướng dẫn trong một số trường hợp, hoặc cho vấn đề cơ bản như thế này,
định nghĩa của một số loại.
>> Nếu bây giờ tôi mở ra danh sách không chấm c, nhận thấy một vài điều.
Nó bao gồm một vài tập tin tiêu đề, nhất trong đó chúng tôi đã nhìn thấy trước.
Nó bao gồm các tập tin tiêu đề riêng của mình.
>> Và như một sang một bên, đó là lý do tại sao đôi báo giá ở đây, trái với góc
dấu ngoặc trên dòng Tôi đã nhấn mạnh đó?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Đúng như vậy đó là một tập tin địa phương.
Vì vậy, nếu đó là một tập tin địa phương của riêng của bạn ở đây trên dòng 15, ví dụ, bạn sử dụng
các dấu ngoặc kép thay các dấu ngoặc góc cạnh.
>> Bây giờ điều này là khá thú vị.
Nhận thấy rằng tôi đã khai báo toàn cầu biến trong chương trình này trên dòng 18
gọi là đầu tiên, ý tưởng là đây là sẽ là một con trỏ đến đầu tiên
nút trong danh sách liên kết của tôi, và tôi đã khởi tạo nó thành vô giá trị, bởi vì tôi đã
không được giao thực tế các nút chỉ được nêu ra.
>> Vì vậy, điều này thể hiện, những bức tranh, những gì chúng tôi nhìn thấy một thời điểm trước đây trong hình ảnh như
rằng con trỏ trên xa bên trái tay.
Vì vậy, ngay bây giờ, con trỏ không có một mũi tên.
Nó thay vì chỉ là vô giá trị.
Nhưng nó đại diện cho những gì sẽ được địa chỉ của thực tế đầu tiên
nút trong danh sách này.
Vì vậy, tôi đã thực hiện nó là một toàn cầu bởi vì, như bạn sẽ thấy, tất cả điều này
chương trình nào trong cuộc sống là thực hiện một danh sách liên kết cho tôi.
>> Bây giờ tôi đã có một vài nguyên mẫu đây.
Tôi quyết định thực hiện các tính năng như xóa, chèn, tìm kiếm, và
traversal -
chỉ là đi bộ cuối cùng trên danh sách, in ra thành phần của nó.
Và giờ đây là chính thường xuyên của tôi.
Và chúng tôi sẽ không dành quá nhiều thời gian trên những vì đây là loại, hy vọng
quá cũ rồi.
>> Tôi sẽ làm như sau, trong khi người sử dụng hợp tác.
Vì vậy, một, tôi sẽ in ra khỏi trình đơn này.
Và tôi đã định dạng nó như sạch như tôi có thể.
Nếu loại người sử dụng trong một, có nghĩa là họ muốn xóa một cái gì đó.
Nếu loại người sử dụng trong hai, có nghĩa là họ muốn chèn một cái gì đó.
Và vv.
Tôi sẽ sau đó nhắc nhở sau đó cho một lệnh.
Và sau đó tôi sẽ sử dụng getInt.
>> Vì vậy, đây là một menuing thực sự đơn giản giao diện mà bạn chỉ cần gõ
một bản đồ số một những lệnh trên.
Và bây giờ tôi có một chuyển đổi sạch đẹp tuyên bố rằng sẽ bật
bất cứ điều gì người dùng gõ vào
Và nếu họ đánh máy một, tôi sẽ gọi xóa và phá vỡ.
Nếu họ đánh máy hai, tôi sẽ gọi chèn và phá vỡ.
>> Và bây giờ thông báo tôi đã đưa từng trong số này trên cùng một dòng.
Đây chỉ là một quyết định phong cách.
Thông thường, chúng tôi đã nhìn thấy một cái gì đó như thế này.
Nhưng tôi chỉ quyết định, thẳng thắn, chương trình của tôi nhìn dễ đọc hơn vì
đó là chỉ có bốn trường hợp để chỉ liệt kê nó như thế này.
Sử dụng hoàn toàn hợp pháp của phong cách.
Và tôi sẽ làm điều này miễn là người sử dụng đã không đánh số không, mà tôi
quyết định sẽ có nghĩa là họ muốn bỏ thuốc lá.
>> Vì vậy, bây giờ nhận thấy những gì tôi sẽ làm gì đây.
Tôi sẽ giải phóng danh sách rõ ràng.
Nhưng thêm vào đó trong một lúc.
Trước tiên hãy chạy chương trình này.
Vì vậy, hãy để tôi làm một thiết bị đầu cuối lớn hơn cửa sổ, dấu chấm dấu gạch chéo danh sách 0.
Tôi sẽ đi trước và chèn bằng gõ hai, một số như 50, và bây giờ
bạn sẽ thấy danh sách hiện nay là 50.
Và văn bản của tôi chỉ cuộn lên một chút.
Vì vậy, bây giờ nhận thấy danh sách có chứa số 50.
>> Chúng ta hãy làm chèn khác bằng cách lấy hai.
Chúng ta hãy nhập vào các số như một.
Danh sách hiện nay là một, tiếp theo là 50.
Vì vậy, đây chỉ là một đại diện văn bản danh sách.
Và chúng ta hãy chèn thêm một số như số 42, đó là hy vọng
sẽ kết thúc ở giữa, bởi vì chương trình này trong các loại đặc biệt nó
các yếu tố như nó chèn chúng.
Vì vậy, chúng tôi đã có nó.
Chương trình siêu đơn giản mà có thể hoàn toàn đã sử dụng một mảng, nhưng tôi
xảy ra để được sử dụng một danh sách liên kết chỉ để tôi có thể tự động
phát triển và thu nhỏ nó.
>> Vì vậy, chúng ta hãy có một cái nhìn cho tìm kiếm, nếu tôi chạy lệnh ba, tôi muốn tìm kiếm
cho, nói, số 43.
Và không có gì rõ ràng được tìm thấy, bởi vì tôi đã trở lại không có phản ứng.
Vì vậy, chúng ta hãy làm điều này một lần nữa.
Tìm kiếm.
Chúng ta hãy tìm kiếm cho 50, hay đúng hơn là tìm kiếm 42, trong đó có một tốt đẹp
ít có ý nghĩa tinh tế.
Và tôi tìm thấy ý nghĩa của cuộc sống nơi đây.
Số 42, nếu bạn không biết tài liệu tham khảo, Google nó.
Được rồi.
Vì vậy, những gì đã thực hiện chương trình này cho tôi?
Nó chỉ cho phép tôi để chèn như vậy xa và tìm kiếm các yếu tố.
>> Hãy nhanh về phía trước, sau đó, để có chức năng chúng tôi liếc nhìn
vào thứ hai như một lời trêu ghẹo.
Vì vậy, chức năng này, tôi khẳng định, tìm kiếm một phần tử trong danh sách bằng cách đầu tiên
một, khiến người sử dụng và sau đó gọi GetInt để có được một int thực tế
mà bạn muốn tìm kiếm.
>> Sau đó, thông báo này.
Tôi sẽ tạo một biến tạm thời trong dòng 188 được gọi là con trỏ -
PTR -
có thể gọi nó là bất cứ điều gì.
Và đó là một con trỏ đến một nút bởi vì tôi đã nói nút * có.
Và tôi khởi tạo nó để bằng đầu tiên để tôi có hiệu quả của tôi
ngón tay, có thể nói, trên rất Yếu tố đầu tiên của danh sách.
Vì vậy, nếu bàn tay phải của tôi ở đây là PTR tôi chỉ vào cùng một điều rằng đầu tiên
được chỉ vào.
>> Vì vậy, bây giờ trở lại trong mã, những gì xảy ra tiếp theo -
đây là một mô hình phổ biến khi lặp lại trên một cấu trúc như một
danh sách liên kết.
Tôi sẽ làm như sau trong khi con trỏ không phải là bằng vô giá trị Vì vậy, trong khi
ngón tay của tôi là không chỉ tại một số rỗng giá trị, nếu con trỏ mũi tên n bằng n.
Chúng ta sẽ nhận thấy đầu tiên đó n là những gì người sử dụng gõ vào mỗi GetInts gọi đây.
>> Và con trỏ mũi tên n có nghĩa là gì?
Vâng, nếu chúng ta quay trở lại với hình ảnh ở đây, nếu tôi có một ngón tay chỉ vào
là nút đầu tiên có chứa chín, các mũi tên về cơ bản có nghĩa là đi đến đó
nút và lấy giá trị ở vị trí n, trong trường hợp này, các lĩnh vực dữ liệu được gọi là n.
>> Như một sang một bên - và chúng ta đã thấy điều này một vài tuần trước khi có ai đó hỏi -
cú pháp này là mới, nhưng nó không cung cấp cho chúng tôi sức mạnh mà chúng ta
không đã có.
Cụm từ này tương đương với việc sử dụng là những gì ký hiệu dấu chấm và một vài ngôi sao
tuần trước khi chúng tôi bóc vỏ trở lại lớp này một chút quá sớm?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Chính xác, đó là ngôi sao, và sau đó nó là ngôi sao chấm n, với
ngoặc đơn ở đây, mà trông, thẳng thắn, tôi nghĩ rằng rất nhiều
khó hiểu hơn để đọc.
Nhưng sao con trỏ, như mọi khi, phương tiện đi đó.
Và một khi bạn đang ở đó, những dữ liệu lĩnh vực bạn muốn truy cập?
Vâng, bạn sử dụng các ký hiệu dấu chấm để truy cập một trường dữ liệu cấu trúc, và tôi
đặc biệt muốn n.
>> Thành thật mà nói, tôi sẽ tranh luận này chỉ là khó khăn hơn để đọc.
Nó khó hơn để nhớ nơi làm các dấu ngoặc đơn đi,
ngôi sao và tất cả điều đó.
Vì vậy, thế giới đã thông qua một số cú pháp đường, vậy để nói chuyện.
Chỉ là một cách gợi cảm của nói, này là tương đương, và
có lẽ trực quan hơn.
Nếu con trỏ thực sự là một con trỏ, mũi tên ký hiệu phương tiện đến đó và tìm thấy
lĩnh vực trong trường hợp này được gọi là n.
>> Vì vậy, nếu tôi tìm thấy nó, nhận thấy những gì tôi làm.
Tôi chỉ đơn giản là in ra, tôi thấy phần trăm tôi, cắm vào giá trị cho int đó.
Tôi gọi ngủ trong một giây chỉ để loại tạm dừng mọi thứ trên màn hình để
cung cấp cho người dùng một giây để hấp thụ những gì vừa xảy ra.
Và sau đó tôi phá vỡ.
Nếu không, tôi phải làm gì?
Tôi cập nhật con trỏ đến bằng con trỏ mũi tên bên cạnh.
>> Vì vậy, chỉ cần được rõ ràng, điều này có nghĩa là đi ở đó, sử dụng ký hiệu trường học cũ của tôi.
Vì vậy, điều này chỉ có nghĩa là để đi đến bất cứ điều gì bạn đang chỉ tay vào, mà trong rất
Trường hợp đầu tiên là tôi chỉ vào các cấu trúc với chín trong nó.
Vì vậy, tôi đã đi ở đó.
Và sau đó là ký hiệu dấu chấm có nghĩa là, nhận được giá trị ở bên cạnh.
>> Nhưng giá trị, mặc dù nó rút ra như một thu hẹp, chỉ là một số.
Đó là một địa chỉ số.
Vì vậy, đây là một dòng mã, cho dù viết như thế này, khó hiểu hơn
cách, hoặc như thế này, nhiều hơn một chút cách trực quan, chỉ có nghĩa là di chuyển bàn tay của tôi
từ nút đầu tiên kế tiếp, và sau đó tiếp theo, và sau đó
kế tiếp, và vv.
>> Vì vậy, chúng tôi không quan tâm tới người khác triển khai các chèn và xóa
và theo cây, hai đầu tiên của mà là khá liên quan.
Và tôi nghĩ rằng nó khá dễ dàng để có được bị mất khi thực hiện nó bằng lời nói.
Nhưng những gì chúng ta có thể làm ở đây là cố gắng xác định như thế nào
tốt nhất để làm điều này trực quan.
Bởi vì tôi sẽ đề xuất rằng nếu chúng ta muốn chèn vào các yếu tố này
danh sách hiện có, mà có năm yếu tố -
9, 17, 22, 26, và 33 -
nếu tôi được là sẽ thực hiện điều này trong mã, tôi cần phải xem xét làm thế nào để đi
về việc này.
>> Và tôi sẽ đề xuất thực hiện các bước bé theo đó, trong trường hợp này tôi có nghĩa là, những gì đang có
các kịch bản có thể là chúng tôi có thể gặp ở chung?
Khi thực hiện chèn một liên kết danh sách, điều này chỉ xảy ra là một
ví dụ cụ thể về kích thước năm.
Vâng, nếu bạn muốn chèn một số, thích nói số một, và
giữ gìn trật tự sắp xếp, nơi rõ ràng là không số một cần phải
đi trong ví dụ cụ thể này?
Giống như lúc đầu.
>> Nhưng điều thú vị đó là nếu bạn muốn chèn một thành này
danh sách, những gì đặc biệt con trỏ cần được cập nhật rõ ràng?
Đầu tiên.
Vì vậy, tôi sẽ tranh luận, đây là trường hợp đầu tiên chúng ta có thể muốn xem xét, một
kịch bản liên quan đến chèn vào đầu danh sách.
>> Hãy nhổ ra có thể là một dễ dàng hoặc thậm chí trường hợp dễ dàng hơn, tương đối nói.
Giả sử tôi muốn chèn số 35 trong thứ tự sắp xếp.
Nó rõ ràng là thuộc ở đó.
Vì vậy, những gì con trỏ rõ ràng là sẽ phải được cập nhật trong kịch bản đó?
Con trỏ 34 của không trở thành vô giá trị nhưng địa chỉ của cấu trúc
chứa số 35.
Vì vậy, đó là trường hợp hai.
Như vậy, tôi đang sắp xếp của lượng tử hóa bao nhiêu công việc tôi phải làm ở đây.
>> Và cuối cùng, trường hợp giữa rõ ràng là thực sự, ở giữa, nếu tôi muốn
chèn một cái gì đó như nói 23, mà đi giữa 23 và 26, nhưng
bây giờ mọi thứ có được nhiều hơn một chút tham gia bởi vì những gì
con trỏ cần phải được thay đổi?
Vì vậy, 22 rõ ràng là cần phải thay đổi bởi vì anh ta không thể chỉ ra 26 nữa.
Anh ta cần để trỏ đến các nút mới Tôi sẽ phải phân bổ bằng cách gọi
malloc hoặc một số tương đương.
>> Nhưng sau đó tôi cũng cần có nút mới, 23 trong trường hợp này, để có con trỏ của nó
chỉ vào ai?
26.
Và có sẽ là một thứ tự của các hoạt động ở đây.
Bởi vì nếu tôi làm điều này một cách ngu ngốc, và tôi Ví dụ bắt đầu vào đầu
danh sách, và mục tiêu của tôi là để chèn 23.
Và tôi kiểm tra, hiện nó thuộc về ở đây, gần chín?
Không.
Nó thuộc về nơi này, bên cạnh 17?
Không.
Liệu nó thuộc về đây bên cạnh 22?
Vâng.
>> Bây giờ nếu tôi là ngu ngốc ở đây, và không suy nghĩ này thông qua, tôi có thể
bố trí nút mới trong 23.
Tôi có thể cập nhật con trỏ từ nút được gọi là 22, chỉ
nó tại nút mới.
Và sau đó làm những gì tôi phải cập nhật con trỏ nút mới được?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Chính xác.
Chỉ ở mức 26.
Nhưng Chết tiệt nếu tôi chưa cập nhật 22 con trỏ để chỉ vào anh chàng này, và
bây giờ tôi có trẻ em mồ côi, phần còn lại danh sách, vậy để nói chuyện.
Vì vậy, để hoạt động ở đây sẽ là quan trọng.
>> Để làm điều này tôi có thể ăn cắp, nói, sáu người tình nguyện.
Và chúng ta hãy xem nếu chúng ta không thể làm điều này trực quan thay vì mã khôn ngoan.
Và chúng tôi có một số căng thẳng đáng yêu quả bóng cho bạn ngày hôm nay.
OK, làm thế nào về một, hai, trong trở lại - ngày kết thúc ở đó.
ba, bốn, cả hai bạn kẻ trên cùng.
Và năm, sáu.
Chắc chắn.
Năm và sáu.
Tất cả các bên phải và chúng tôi sẽ đến đến với bạn lần sau.
Tất cả các bên phải, đi lên trên.
>> Được rồi, kể từ khi bạn đang lên đây lần đầu tiên, bạn muốn trở thành một trong những lúng túng
trong Google Glass đây?
Được rồi, vì vậy, OK, Thủy tinh, quay video.
OK, bạn tốt để đi.
>> Được rồi, vì vậy nếu các bạn có thể đi qua ở đây, tôi đã chuẩn bị trước
một số con số.
Được rồi, đi trên trên đây.
Và tại sao bạn không đi một chút tiếp tục như vậy.
Và chúng ta hãy xem, tên của bạn là gì, với kính Google?
>> HỌC SINH: Ben.
>> SPEAKER 1: Ben?
OK, Ben, bạn sẽ là người đầu tiên, theo nghĩa đen.
Vì vậy, chúng tôi sẽ gửi cho bạn đến cuối giai đoạn.
Tất cả các bên phải, và tên của bạn?
>> HỌC SINH: Jason.
>> SPEAKER 1: Jason, OK bạn sẽ là số chín.
Vì vậy, nếu bạn muốn theo Ben như vậy.
>> HỌC SINH: Jill.
>> SPEAKER 1: Jill, bạn sẽ được 17, mà nếu tôi đã làm điều này nhiều hơn
thông minh, tôi sẽ có bắt đầu ở đầu kia.
Bạn đi theo cách đó.
22.
Và bạn?
>> HỌC SINH: Mary.
>> SPEAKER 1: Mary, bạn sẽ có 22.
Và tên của bạn là?
>> HỌC SINH: Chris.
>> SPEAKER 1: Chris, bạn sẽ có 26.
Và sau đó cuối cùng.
>> HỌC SINH: Diana.
>> SPEAKER 1: Diana, bạn sẽ có 34.
Vì vậy, bạn đi trên trên đây.
>> Được rồi, vì vậy hoàn thiện sắp xếp đặt hàng rồi.
Và chúng ta hãy đi trước và làm điều này để chúng ta có thể thực sự -
Ben bạn chỉ cần loại tìm kiếm ra vào không nơi nào có.
OK, vì vậy chúng ta hãy đi trước và mô tả này sử dụng vũ khí, giống như tôi, chính xác,
những gì đang xảy ra.
Vì vậy, đi trước và cho mình một hoặc giữa hai chân mình.
Và đi trước và chỉ bằng một tay để bất cứ ai bạn nên chỉ vào
trên cơ sở này.
Và nếu bạn là vô giá trị chỉ điểm thẳng xuống sàn nhà.
OK, vì vậy tốt.
>> Vì vậy, bây giờ chúng tôi có một danh sách liên kết, và cho tôi đề xuất rằng tôi sẽ đóng vai trò của
PTR, vì vậy tôi sẽ không bận tâm thực hiện điều này xung quanh.
Và sau đó - một người nào đó ước ngu ngốc - bạn có thể gọi bất cứ điều gì bạn muốn này -
con trỏ trước, con trỏ pred -
nó chỉ là biệt danh chúng tôi đã cung cấp trong mẫu mã của chúng tôi để tay trái của tôi.
Mặt khác đó sẽ được giữ theo dõi của những người trong người
theo kịch bản.
>> Vì vậy, giả sử, lần đầu tiên, tôi muốn nhổ ra là ví dụ đầu tiên của chèn, nói
20, vào danh sách.
Vì vậy, tôi sẽ cần một người nào đó là hiện thân của số 20 cho chúng ta.
Vì vậy, tôi cần một người nào đó malloc từ khán giả.
Lên đây.
Tên của bạn là gì?
>> HỌC SINH: Brian.
>> SPEAKER 1: Brian, tất cả các bên phải, vì vậy bạn sẽ là nút chứa 20.
Được rồi, đi trên trên đây.
Và rõ ràng, nơi Brian không thuộc về ai?
Vì vậy, ở giữa - trên thực tế, chờ một phút.
Chúng tôi đang làm điều này trong trật tự.
Chúng tôi đang làm điều này khó khăn hơn rất nhiều hơn nó cần phải được lần đầu tiên.
OK, chúng ta sẽ tự do Brian và realloc Brian như năm.
>> OK, vì vậy bây giờ chúng tôi muốn chèn Brian là năm.
Vì vậy, đến trên hơn ở đây bên cạnh Ben chỉ là một thời điểm.
Và bạn có lẽ có thể nói nơi mà câu chuyện này đang xảy ra.
Nhưng chúng ta hãy suy nghĩ cẩn thận về thứ tự của các hoạt động.
Và đó là chính xác hình ảnh này đó là sẽ xếp hàng
với mẫu mã.
Vì vậy, ở đây tôi đã PTR chỉ ban đầu không ở Bến, cho mỗi gia nhập, nhưng tại bất cứ điều gì
đánh giá cao ông có, mà trong trường hợp này là - tên của bạn là gì nữa?
>> HỌC SINH: Jason.
>> SPEAKER 1: Jason, vì vậy cả hai Ben và tôi Jason chỉ vào tại thời điểm này.
Vì vậy, bây giờ tôi phải xác định, nơi không thuộc về Brian?
Vì vậy, điều duy nhất tôi có thể truy cập ngay bây giờ là mục dữ liệu n của mình.
Vì vậy, tôi sẽ kiểm tra, được Brian ít hơn Jason?
Câu trả lời là đúng.
>> Vì vậy, những gì bây giờ cần phải xảy ra, theo thứ tự đúng?
Tôi cần phải cập nhật bao nhiêu con trỏ trong tổng số trong câu chuyện này?
Nơi tay của tôi vẫn còn chỉ vào Jason, và bàn tay của bạn - nếu bạn muốn
đặt bàn tay của bạn như thế nào, loại, tôi không biết, một dấu hỏi.
OK, tốt.
>> Được rồi, vì vậy bạn có một vài ứng cử viên.
Hoặc Bến hoặc tôi hoặc Brian hoặc Jason hoặc những người khác, mà
con trỏ cần phải thay đổi?
Bao nhiêu trong tổng số?
>> OK, vì vậy hai.
Con trỏ của tôi không thực sự quan trọng nữa bởi vì tôi chỉ là tạm thời.
Vì vậy, nó là hai chàng trai, có lẽ, cả Ben và Brian.
Vì vậy, hãy để tôi đề xuất rằng chúng tôi cập nhật Ben, kể từ khi ông đầu tiên.
Yếu tố đầu tiên của danh sách này bây giờ sẽ là Brian.
Vì vậy, Bến điểm tại Brian.
OK, bây giờ những gì?
>> Người được chỉ vào ai?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: OK để Brian có điểm tại Jason.
Nhưng tôi đã mất liên lạc với con trỏ?
Tôi biết Jason là?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: tôi làm, vì tôi con trỏ tạm thời.
Và có lẽ, tôi đã không thay đổi chỉ tại nút mới.
Vì vậy, chúng tôi chỉ đơn giản là có thể có điểm Brian ở bất cứ ai tôi chỉ vào.
Và chúng tôi đang thực hiện.
Vì vậy, trường hợp một, chèn vào đầu danh sách.
Có hai bước chính.
Một, chúng ta phải cập nhật Ben, và sau đó chúng tôi cũng có để cập nhật Brian.
Và sau đó tôi không phải bận tâm traipsing thông qua phần còn lại của
danh sách, bởi vì chúng tôi đã tìm thấy mình vị trí, bởi vì anh ta thuộc về
bên trái của phần tử đầu tiên.
>> Được rồi, vì vậy khá dễ dàng.
Trong thực tế, cảm thấy như chúng tôi hầu như làm này quá phức tạp.
Vì vậy, bây giờ chúng ta nhổ ra cuối cùng danh sách, và nhìn thấy nơi
sự phức tạp bắt đầu.
Vì vậy, nếu bây giờ, tôi alloc từ khán giả.
Bất cứ ai muốn chơi 55?
Được rồi, tôi thấy bàn tay của bạn đầu tiên.
Lên đây.
Vâng.
Tên của bạn là gì?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Habata.
OK, đi lên trên.
Bạn sẽ có số 55.
Vì vậy, bạn, tất nhiên, thuộc về ở cuối danh sách.
Vì vậy, chúng ta hãy xem lại các mô phỏng với tôi là PTR cho chỉ là một thời điểm.
Vì vậy, tôi đầu tiên sẽ chỉ vào bất cứ điều gì Ben đã chỉ tay vào.
Chúng tôi cả hai chỉ tại Brian.
Vì vậy, 55 không phải là ít hơn năm.
Vì vậy, tôi sẽ cập nhật bản thân mình bằng trỏ đến con trỏ tiếp theo của Brian, người
bây giờ tất nhiên là Jason.
55 không phải là ít hơn chín, vì vậy Tôi sẽ cập nhật PTR.
Tôi sẽ cập nhật PTR Tôi sẽ cập nhật PTR.
Và tôi sẽ - hmm, những gì Tên của bạn một lần nữa?
>> HỌC SINH: Diana.
>> SPEAKER 1: Diana là chỉ, tất nhiên, tại vô giá trị với bàn tay trái của cô.
Vì vậy, nơi nào thực sự Habata thuộc rõ ràng không?
Bên trái, ở đây.
Vì vậy, làm thế nào để tôi biết đặt mình đây Tôi nghĩ rằng tôi đã hơi say lên.
Bởi vì là những gì PTR nghệ thuật thời điểm này trong thời gian?
Null.
Vì vậy, mặc dù, trực quan, chúng ta có thể rõ ràng là nhìn thấy tất cả các
kẻ ở đây trên sân khấu.
Tôi đã không lưu giữ theo dõi trước đó người trong danh sách.
Tôi không có một ngón tay chỉ ra, trong trường hợp này, nút số 34.
>> Vì vậy, chúng ta hãy thực sự bắt đầu trên này.
Vì vậy, bây giờ tôi thực sự cần một biến địa phương thứ hai.
Và đây là những gì bạn sẽ thấy trong các thực tế mẫu mã C, nơi mà như tôi đi,
khi tôi cập nhật tay phải của tôi chỉ Jason, do đó để lại Brian sau, tôi
tốt hơn bắt đầu sử dụng tay trái cập nhật nơi tôi ở, vì vậy mà tôi đi
thông qua danh sách này -
lúng túng hơn tôi dự định giờ đây trực quan -
Tôi sẽ đến được với các cuối danh sách.
>> Tay này vẫn còn vô giá trị, mà là khá vô dụng, khác hơn là để chỉ ra
Tôi rõ ràng vào cuối danh sách, nhưng bây giờ ít nhất tôi có điều này
con trỏ chỉ người tiền nhiệm ở đây, vì vậy bây giờ những gì đưa cho và những gì con trỏ cần
được cập nhật?
Có tay nào bạn muốn để cấu hình lại đầu tiên?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: OK, vậy Diana.
Nơi nào bạn muốn chỉ Con trỏ trái của Diana tại?
55, có lẽ, vì vậy mà chúng tôi đã đưa vào đó.
Và nơi nên 55 con trỏ đi đâu?
Xuống, đại diện cho null.
Và bàn tay của tôi, vào thời điểm này, không quan trọng bởi vì họ chỉ
các biến tạm thời.
Vì vậy, bây giờ chúng tôi đang thực hiện.
>> Vì vậy, sự phức tạp thêm có - và nó không phải là khó thực hiện,
nhưng chúng ta cần một biến thứ cấp để làm chắc chắn rằng trước khi tôi di chuyển phải của tôi
tay, tôi cập nhật các giá trị của trái tay, con trỏ pred trong trường hợp này, vì vậy
rằng tôi có một con trỏ theo sau để theo dõi các nơi tôi.
Bây giờ như một sang một bên, nếu bạn đang suy nghĩ này thông qua, điều này cảm thấy như đó là một
ít khó chịu khi phải giữ theo dõi của bàn tay trái này.
>> Điều gì sẽ một giải pháp khác cho vấn đề này đã được?
Nếu bạn đã thiết kế lại các dữ liệu cấu trúc chúng ta đang nói
thông qua ngay bây giờ?
Nếu loại chỉ này cảm thấy một chút gây phiền nhiễu có, như thế, hai con trỏ
đi qua danh sách, những người khác có thể đã, trong một thế giới lý tưởng, duy trì
thông tin cần thiết?
Yeah?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Chính xác.
Đúng như vậy không thực sự là một thú vị mầm của một ý tưởng.
Và ý tưởng này của một con trỏ trước, chỉ vào phần tử trước đó.
Nếu tôi chỉ thể hiện rằng trong danh sách chính nó?
Và nó sẽ được khó khăn để hình dung này mà không có tất cả các giấy
rơi xuống sàn nhà.
Nhưng giả sử rằng những kẻ sử dụng cả hai bàn tay của mình để có một trước
con trỏ, và một con trỏ tới, do đó thực hiện những gì chúng tôi sẽ gọi một gấp đôi
danh sách liên kết.
Điều đó sẽ cho phép tôi để sắp xếp các tua lại, dễ dàng hơn nhiều mà không có tôi, các
lập trình, phải giữ theo dõi bằng tay -
thực sự bằng tay -
nơi tôi đã được trước đó trong danh sách.
Vì vậy, chúng tôi sẽ không làm điều đó.
Chúng tôi sẽ giữ nó đơn giản bởi vì đó là sẽ đến ở một mức giá, gấp đôi
nhiều không gian cho các con trỏ, nếu bạn muốn có một thứ hai.
Nhưng đó thực sự là một chung cấu trúc dữ liệu được biết đến như một
gấp đôi danh sách liên kết.
>> Chúng ta hãy làm ví dụ cuối cùng ở đây và đặt những kẻ ra khỏi đau khổ của họ.
Vì vậy, malloc 20.
Lên đây từ các lối đi đó.
Được rồi, tên của bạn là gì?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Xin lỗi?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Demeron?
OK đi lên trên.
Bạn sẽ là 20.
Bạn rõ ràng là sẽ thuộc giữa 17 và 22.
Vì vậy, hãy để tôi học được bài học của tôi.
Tôi sẽ bắt đầu con trỏ chỉ vào Brian.
Và tôi sẽ có bàn tay trái của tôi chỉ cập nhật đến Brian như tôi di chuyển đến
Jason, kiểm tra thực hiện 20 ít hơn chín?
Không.
Là 20 ít hơn 17?
Không.
Là 20 ít hơn 22?
Vâng.
Vì vậy, những gì con trỏ hoặc tay cần phải thay đổi nơi họ đang chỉ bây giờ?
>> Vì vậy, chúng ta có thể làm 17 chỉ ở mức 20.
Vì vậy, đó là tốt.
Nơi nào chúng ta muốn chỉ con trỏ của bạn bây giờ?
Ở tuổi 22.
Và chúng tôi biết là 22, một lần nữa cám ơn để con trỏ tạm thời của tôi.
Vì vậy chúng tôi có OK.
Vì vậy, bởi vì dung lượng lưu trữ tạm thời Tôi đã lưu giữ theo dõi nơi tất cả mọi người là.
Và bây giờ bạn trực quan có thể đi vào nơi bạn thuộc về, và bây giờ chúng ta cần 1, 2, 3,
4, 5, 6, 7, 8, 9 quả bóng căng thẳng, và một tràng pháo tay cho
những người này, nếu chúng ta có thể.
Độc đáo được thực hiện.
>> [Vỗ tay]
>> SPEAKER 1: Được rồi.
Và bạn có thể giữ cho các mảnh giấy như vật lưu niệm.
>> Được rồi, vì vậy, tôi tin tưởng nó rất nhiều dễ dàng hơn để bước qua với
con người hơn là với mã thực tế.
Nhưng những gì bạn sẽ tìm thấy chỉ trong một khoảnh khắc bây giờ, là như nhau - oh, cảm ơn bạn.
Cảm ơn bạn -
là bạn sẽ thấy rằng cùng một dữ liệu cấu trúc, một danh sách liên kết, có thể thực sự
được sử dụng như là một khối xây dựng cho nhiều hơn tinh vi cấu trúc dữ liệu.
>> Và nhận ra quá chủ đề ở đây là chúng tôi đã hoàn toàn giới thiệu hơn
phức tạp trong thực hiện của thuật toán này.
Chèn, và nếu chúng ta đã đi qua nó, xóa và tìm kiếm, là một chút
phức tạp hơn là với một mảng.
Nhưng chúng ta đạt được một số tính năng động.
Chúng tôi nhận được một cấu trúc dữ liệu thích nghi.
>> Nhưng một lần nữa, chúng tôi phải trả giá của việc có một số phức tạp thêm, cả trong
thực hiện nó.
Và chúng tôi đang từ bỏ truy cập ngẫu nhiên.
Và phải trung thực, không có một số đẹp làm sạch trượt tôi có thể cung cấp cho bạn mà
nói đây là lý do tại sao một danh sách liên kết là tốt hơn so với một mảng.
Và để nó ở đó.
Vì chủ đề tái phát nữa, thậm chí nhiều hơn như vậy trong vài tuần tới, là
rằng có không nhất thiết một câu trả lời chính xác.
>> Đây là lý do tại sao chúng tôi có trục riêng biệt thiết kế cho bộ vấn đề.
Nó sẽ rất bối cảnh nhạy cảm cho dù bạn muốn sử dụng dữ liệu này
cấu trúc hoặc một, và nó sẽ phụ thuộc vào những gì quan trọng với bạn về
các nguồn lực và phức tạp.
>> Nhưng hãy để tôi đề xuất rằng các dữ liệu lý tưởng cấu trúc, Chén thánh, sẽ
cái gì đó là thời gian liên tục, không phân biệt bao nhiêu là công cụ
bên trong nó, nó sẽ không thể tuyệt vời nếu một cấu trúc dữ liệu trả về câu trả lời trong
thời gian liên tục.
Vâng.
Từ này trong từ điển lớn của bạn.
Hoặc không, từ đây không phải là.
Hoặc bất kỳ vấn đề như vậy đó.
Vâng chúng ta hãy xem nếu chúng ta không có thể ít nhất đi một bước về phía đó.
>> Hãy để tôi đưa ra một cấu trúc dữ liệu mới có thể được sử dụng cho những thứ khác nhau,
trong trường hợp này được gọi là một bảng băm.
Và vì vậy chúng tôi đang thực sự trở lại liếc tại một mảng, trong trường hợp này, và
có phần tùy tiện, tôi đã rút ra này bảng băm như một mảng với sắp xếp của một
mảng hai chiều -
hay đúng hơn là nó miêu tả đây như một hai mảng chiều - nhưng điều này chỉ là
một loạt các kích thước 26, như vậy nếu chúng ta gọi bảng mảng, khung bảng
không là hình chữ nhật ở phía trên.
Bảng khung 25 là hình chữ nhật ở phía dưới.
Và điều này là làm thế nào tôi có thể rút ra một dữ liệu cấu trúc trong đó tôi muốn để lưu trữ
người dân tên.
>> Vì vậy, ví dụ, và tôi sẽ không vẽ toàn bộ điều trên đây trên cao, nếu tôi
có mảng này, mà bây giờ tôi sẽ đến gọi một bảng băm, và điều này một lần nữa
vị trí không.
Này đây là vị trí một, và vv.
Tôi cho rằng tôi muốn sử dụng dữ liệu này cấu trúc, vì lợi ích của cuộc thảo luận,
để lưu trữ tên người, Alice và Bob và Charlie và các tên khác như vậy.
Vì vậy, nghĩ về điều này bây giờ là sự khởi đầu , nói rằng, một từ điển
với nhiều từ ngữ.
Chúng được tên trong ví dụ của chúng tôi ở đây.
Và điều này là tất cả các quá Gecman, có lẽ, để thực hiện kiểm tra chính tả, như chúng tôi
có thể cho vấn đề thiết lập sáu.
>> Vì vậy, nếu chúng ta có một loạt các kích thước tổng số 26 do đó đây là vị trí thứ 25
ở phía dưới, và tôi cho rằng Alice là từ đầu tiên trong từ điển của
tên mà tôi muốn để chèn vào bộ nhớ RAM, vào cấu trúc dữ liệu này, ở đâu
bản năng nói với bạn rằng Alice tên nên đi trong mảng này?
>> Chúng tôi có 26 tùy chọn.
Nơi mà chúng tôi muốn đưa cô ấy?
Chúng tôi muốn cô ấy trong khung không, phải không?
Một cho Alice, chúng ta hãy gọi đó là bằng không.
Và B sẽ là một, và C sẽ có hai.
Vì vậy, chúng ta sẽ viết Tên của Alice ở đây.
Nếu chúng ta sau đó chèn Bob, mình tên sẽ đi đây.
Charlie sẽ đi đây.
Và vv xuống qua cấu trúc dữ liệu này.
>> Đây là một cấu trúc dữ liệu tuyệt vời.
Tại sao?
Thời gian hoạt động cũng như là những gì chèn tên của một con người vào trong này
cấu trúc dữ liệu ngay bây giờ?
Cho rằng bảng này được thực hiện, thực sự, như một mảng.
Vâng đó là thời gian liên tục.
Đó là thứ tự của một.
Tại sao?
>> Cũng làm thế nào để bạn xác định nơi thuộc về Alice?
Bạn nhìn vào mà thư của tên cô ấy?
Là người đầu tiên.
Và bạn có thể đạt được điều đó, nếu đó là một chuỗi, bởi chỉ cần nhìn vào chuỗi
khung không.
Vì vậy, nhân vật thứ không của chuỗi.
Đó là dễ dàng.
Chúng tôi đã làm điều đó trong mật phân công tuần trước.
Và sau đó khi bạn biết rằng Alice thư được vốn A, chúng tôi có thể trừ
ra 65 hoặc vốn A chính nó, mà cho chúng ta không.
Vì vậy, bây giờ chúng ta biết rằng Alice thuộc ở vị trí số không.
>> Và đưa ra một con trỏ đến dữ liệu này cấu trúc, của một số loại, làm thế nào lâu
nó đưa tôi đến một nơi không ở một mảng?
Chỉ cần một bước, phải Đó là thời gian liên tục vì truy cập ngẫu nhiên chúng tôi
đề xuất là một tính năng của một mảng.
Vì vậy, trong ngắn hạn, tìm ra những gì các chỉ số của tên Alice là, đó là, trong
trường hợp này, là A, hoặc chúng ta hãy giải quyết mà không, trong đó B là một trong và C là
hai, tìm mà ra là thời gian liên tục.
Tôi chỉ cần nhìn vào chữ cái đầu tiên của mình, tìm ra nơi không là một
mảng cũng là thời gian liên tục.
Vì vậy, về mặt kỹ thuật đó là như hai bước bây giờ.
Nhưng đó vẫn không đổi.
Vì vậy, chúng tôi gọi đó là O lớn, nên chúng tôi đã Alice đưa vào bảng này trong
thời gian liên tục.
>> Nhưng tất nhiên, tôi là ngây thơ ở đây, phải không?
Những gì nếu có một Aaron trong lớp học?
Hoặc Alicia?
Hoặc bất kỳ tên khác bắt đầu với A. Chúng ta đi đâu để đặt
người đó, phải không?
Ý tôi là, ngay bây giờ chỉ có ba người trên bàn, có lẽ chúng ta
nên đặt tại vị trí Aaron không một hai ba.
>> Phải, tôi có thể đặt một đây.
Nhưng sau đó, nếu chúng ta cố gắng để chèn David vào danh sách này, nơi mà David đi đâu?
Bây giờ hệ thống của chúng tôi bắt đầu phá vỡ xuống, phải không?
Bởi vì bây giờ David kết thúc ở đây nếu Aaron thực sự là đây.
Và vì vậy bây giờ ý tưởng này hoàn toàn có một cấu trúc dữ liệu sạch cung cấp cho chúng tôi
chèn thời gian liên tục không còn thời gian liên tục, bởi vì tôi phải
kiểm tra, oh, damnit, một ai đó đã tại vị trí của Alice.
>> Hãy để tôi thăm dò phần còn lại của dữ liệu này cấu trúc, tìm kiếm một chỗ để đặt
một người nào đó như tên của Aaron.
Và do đó cũng đang bắt đầu dành thời gian tuyến tính.
Hơn nữa, nếu bây giờ bạn muốn tìm Aaron trong cấu trúc dữ liệu này, và bạn
kiểm tra, và tên của Aaron không phải là ở đây.
Tốt nhất, bạn sẽ chỉ cần nói của Aaron không trong cấu trúc dữ liệu.
Nhưng nếu bạn bắt đầu để có chỗ cho Aaron nơi có cần phải có được một D
hoặc E, bạn, trường hợp xấu nhất, phải kiểm tra cấu trúc dữ liệu toàn bộ, trong
trường hợp này mạn vào một cái gì đó tuyến tính trong các kích thước của bảng.
>> Vì vậy, tất cả rồi, tôi sẽ sửa lỗi này.
Vấn đề ở đây là tôi đã 26 yếu tố trong mảng này.
Hãy để tôi thay đổi nó.
Rất tiếc.
Hãy để tôi thay đổi nó để thay là của kích thước 26 trong tổng số, thông báo phía dưới
chỉ số sẽ thay đổi đến n trừ đi 1.
Nếu 26 rõ ràng là quá nhỏ đối với con người ' tên, bởi vì có hàng ngàn
tên của thế giới, chúng ta chỉ cần thực hiện trong 100 hoặc 1000, 10000.
Chúng ta hãy phân bổ không gian nhiều hơn nữa.
>> Cũng không nhất thiết phải giảm xác suất mà chúng tôi sẽ không có hai
những người có tên bắt đầu bằng A, và như vậy, bạn đã đi để cố gắng đưa một
tên ở vị trí không còn.
Họ vẫn sẽ va chạm, mà có nghĩa là chúng tôi vẫn cần một giải pháp để đưa
Alice và Aaron và Alicia và khác tên bắt đầu bằng một nơi khác.
Nhưng bao nhiêu của một vấn đề là điều này?
Xác suất là những gì mà bạn có va chạm trong một dữ liệu
cấu trúc như thế này?
>> Vâng, hãy để tôi - chúng tôi sẽ trở lại cho câu hỏi ở đây.
Và xem làm thế nào chúng ta có thể giải quyết nó đầu tiên.
Hãy để tôi kéo lên đề nghị này đây.
Một thuật toán những gì chúng tôi vừa mô tả là, để phân tích được gọi là tuyến tính
thăm dò, theo đó, nếu bạn đã cố gắng để chèn một cái gì đó ở đây trong dữ liệu này
cấu trúc, được gọi là một bảng băm, và không có phòng đó, bạn
thực sự thăm dò cấu trúc dữ liệu kiểm tra, điều này không?
Là có sẵn này có sẵn này?
Đây có phải là có sẵn?
Và khi nó cuối cùng là, bạn chèn tên mà bạn dự định ban đầu
ở những nơi khác tại địa điểm đó.
Nhưng trong trường hợp xấu nhất, các vị trí chỉ có thể là dưới cùng của dữ liệu
cấu trúc, cuối của mảng.
>> Vì vậy, tuyến tính thăm dò, trong trường hợp xấu nhất, mạn vào một thuật toán tuyến tính nơi
Aaron, nếu xảy ra sẽ được chèn vào cuối trong cấu trúc dữ liệu này, ông có thể
va chạm với vị trí đầu tiên này, nhưng sau đó kết thúc bằng cách may mắn ở cuối.
Vì vậy, đây không phải là một hằng số Hiện Chén Thánh cho chúng ta.
Cách tiếp cận này của các yếu tố chèn vào một cấu trúc dữ liệu được gọi là băm
bảng dường như không có thời gian liên tục ít nhất là trong trường hợp tổng quát.
Nó có thể phân cấp thành một cái gì đó tuyến tính.
>> Vì vậy, nếu chúng ta giải quyết va chạm hơi khác nhau?
Vì vậy, đây là một tinh vi hơn tiếp cận với những gì vẫn còn
được gọi là một bảng băm.
Và bằng cách băm, như một sang một bên, những gì Tôi có nghĩa là chỉ số
Tôi đề cập trước đó.
Để băm một cái gì đó có thể dùng như một động từ.
>> Vì vậy, nếu bạn băm Alice là một tên, một hàm băm, có thể nói,
phải trả lại một số.
Trong trường hợp này là số không nếu cô ấy thuộc về tại vị trí không, một khi cô thuộc vào
vị trí một, và vv.
Vì vậy, hàm băm của tôi vậy, đến nay đã được siêu đơn giản, chỉ nhìn vào
chữ cái đầu tiên trong tên của một ai đó.
Nhưng một hàm băm có như đầu vào một số phần dữ liệu, một
chuỗi, một int, bất cứ điều gì.
Và nó phun ra thường là một số.
Và con số đó là nơi mà dữ liệu yếu tố thuộc về một cấu trúc dữ liệu
được biết đến ở đây như một bảng băm.
>> Vì vậy, chỉ bằng trực giác, đây là một bối cảnh hơi khác nhau.
Điều này thực sự là đề cập đến một ví dụ liên quan đến ngày sinh nhật, nơi
có thể có nhiều như 31 ngày trong tháng.
Nhưng những gì đã làm người này quyết định làm trong trường hợp có va chạm?
Bối cảnh hiện nay là, không phải là một vụ va chạm của tên, nhưng một vụ va chạm của ngày sinh nhật,
nếu hai người có cùng ngày sinh trên các ngày 02 tháng 10, ví dụ.
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Vâng, vì vậy ở đây chúng tôi có sự thúc đẩy của danh sách liên kết.
Vì vậy, có vẻ một chút khác nhau hơn, chúng tôi đã thu hút nó trước đó.
Nhưng chúng tôi dường như có một mảng ở phía bên tay trái.
Đó là một chỉ số, cho không đặc biệt lý do.
Nhưng nó vẫn còn một mảng.
Nó là một mảng của con trỏ.
Và mỗi người trong số những yếu tố này, mỗi những vòng tròn hoặc dấu gạch chéo - các dấu gạch chéo
đại diện null - mỗi gợi ý rõ ràng là chỉ để
những gì cấu trúc dữ liệu?
Một danh sách liên kết.
>> Vì vậy, bây giờ chúng tôi có khả năng cứng mã vào chương trình của chúng tôi
kích thước của bảng.
Trong trường hợp này, chúng ta biết có bao giờ hơn 31 ngày trong một tháng.
Vì vậy, khó mã hóa một giá trị như 31 được hợp lý trong bối cảnh đó.
Trong bối cảnh tên, cứng mã hóa 26 là không hợp lý đó của người dân
tên chỉ bắt đầu, ví dụ, bảng chữ cái từ A đến Z. liên quan
>> Chúng ta có thể nhồi nhét tất cả vào dữ liệu cấu trúc, miễn là, khi chúng ta có được một
va chạm, chúng tôi không đặt tên ở đây, chúng tôi thay vì nghĩ về những tế bào
không như các chuỗi mình, nhưng như con trỏ đến, ví dụ, Alice.
Và sau đó Alice có thể có một con trỏ khác tên bắt đầu với
A. Và Bob thực sự đi qua đây.
>> Và nếu có một tên khác bắt đầu với B, anh ta kết thúc ở đây.
Và do đó mỗi nguyên tố này bảng hai, nếu chúng tôi thiết kế này một
ít khéo léo hơn -
đi trên -
nếu chúng tôi thiết kế này nhiều hơn một chút khéo léo, bây giờ trở thành một dữ liệu thích ứng
cấu trúc, mà không có giới hạn cứng trên bao nhiêu yếu tố bạn có thể chèn
vào nó bởi vì nếu bạn có một vụ va chạm, đó là tốt.
Chỉ cần đi trước và thêm nó vào những gì chúng ta đã thấy một chút trước đã
được biết đến như một danh sách liên kết.
>> Vâng chúng ta hãy dừng lại một lúc.
Xác suất của một vụ va chạm là những gì ở nơi đầu tiên?
Đúng, có lẽ tôi là hơn suy nghĩ, có thể Tôi làm công nghệ hơn vấn đề này,
bởi vì bạn biết gì không?
Vâng, tôi có thể đến với bất ví dụ ra khỏi đỉnh đầu của tôi như
Allison và Aaron, nhưng trong thực tế, cung cấp một phân phối thống nhất của
đầu vào, đó là một số chèn ngẫu nhiên thành một cấu trúc dữ liệu, những gì thực sự là
xác suất của một vụ va chạm?
Cũng quay ra, nó thực sự siêu cao.
Hãy để tôi khái quát này vấn đề là như thế này.
>> Vì vậy, trong một căn phòng của n CS50 sinh viên, những gì xác suất có ít nhất
hai sinh viên trong phòng có cùng ngày sinh?
Do đó, có những gì. một vài hund -
200, 300 người dân ở đây và một số trăm người ở nhà hôm nay.
Vì vậy, nếu bạn muốn tự hỏi mình những gì xác suất của hai người
trong căn phòng này có cùng ngày sinh, chúng ta có thể con số này ra.
Và tôi khẳng định trên thực tế có hai những người có cùng ngày sinh.
>> Ví dụ, không ai có ngày sinh nhật hôm nay?
Hôm qua?
Ngày mai?
Được rồi, nó cảm thấy như tôi sẽ phải làm 363 này hay như vậy hơn
Thời gian để thực sự tìm ra nếu chúng ta có một vụ va chạm.
Hoặc chúng tôi chỉ có thể làm điều này bằng toán học chứ không phải là tediously
làm điều này.
Và đề nghị sau đây.
>> Vì vậy, tôi đề nghị chúng ta có thể mô hình xác suất của hai người có
cùng sinh nhật như xác suất của 1 trừ khả năng không ai có
cùng ngày sinh nhật.
Vì vậy, để có được điều này, và điều này chỉ là cách ưa thích của văn bản này, cho
người đầu tiên trong phòng, anh ta hoặc cô có thể có bất kỳ một trong những có thể
ngày sinh nhật giả định 365 ngày trong năm, với lời xin lỗi đối với người
29 sinh nhật tháng hai.
>> Vì vậy, người đầu tiên trong căn phòng này là miễn phí có bất kỳ số lượng của ngày sinh nhật
ra khỏi khả năng 365 để chúng tôi sẽ làm điều đó 365 chia cho 365,
đó là một trong.
Người tiếp theo trong phòng, nếu mục tiêu là để tránh va chạm, có thể chỉ
có của mình hoặc sinh nhật của cô về cách nhiều ngày khác nhau có thể?
364.
Vì vậy, nhiệm kỳ thứ hai trong biểu thức này là về cơ bản làm toán đó cho chúng ta
bằng cách trừ đi một ngày có thể.
Và sau đó vào ngày hôm sau, ngày hôm sau, các Ngày hôm sau xuống với tổng số
của người trong phòng.
>> Và nếu chúng ta sau đó xem xét, sau đó là gì xác suất không của tất cả mọi người có
ngày sinh nhật độc đáo, nhưng lại trừ đi 1 rằng, một biểu hiện những gì chúng tôi nhận được là
mà có thể rất fancifully trông như thế này.
Nhưng nó thú vị hơn nhìn trực quan.
Đây là một biểu đồ mà trên trục x số lượng người trong phòng,
số ngày sinh nhật.
Trên trục y là xác suất của một vụ va chạm, hai người
có cùng ngày sinh.
>> Và takeaway từ đường cong này là rằng ngay khi bạn nhận được để thích 40
sinh viên, bạn đang lên tại một xác suất 90% combinatorically của hai
người trở lên có cùng ngày sinh nhật.
Và một khi bạn nhận được để thích 58 người đó là gần 100% cơ hội hai
người trong phòng sẽ có cùng sinh nhật, mặc dù có
365 hoặc 366 thùng có thể, và chỉ có 58 người trong phòng.
Chỉ thống kê bạn có khả năng nhận được va chạm, mà trong ngắn hạn
thúc đẩy cuộc thảo luận này.
Rằng ngay cả khi chúng tôi có được ưa thích ở đây, và bắt đầu có những dây chuyền, chúng ta vẫn còn
sẽ có va chạm.
>> Để đặt ra câu hỏi, là những gì chi phí kinh chèn và xóa bỏ
thành một cấu trúc dữ liệu như thế này?
Cũng cho tôi đề xuất -
và cho tôi quay trở lại màn hình trên ở đây - nếu chúng ta có n yếu tố trong
danh sách, vì vậy nếu chúng ta đang cố gắng để chèn n phần tử, và chúng tôi có
bao nhiêu tổng số xô?
Hãy nói rằng tổng số 31 thùng trong trường hợp của ngày sinh nhật.
Chiều dài tối đa của một là những gì của các chuỗi có khả năng?
>> Nếu một lần nữa có thể 31 ngày sinh nhật trong một tháng.
Và chúng tôi chỉ kết tụ tất cả mọi người -
thực sự đó là một ví dụ ngu ngốc.
Hãy thay vì làm 26.
Vì vậy, nếu thực sự có người có tên bắt đầu với từ A đến Z, do đó cho
chúng tôi 26 khả năng.
Và chúng tôi đang sử dụng một cấu trúc dữ liệu như mà chúng ta vừa thấy, nhờ đó chúng ta có
một mảng của các con trỏ, mỗi trong số đó trỏ đến một danh sách liên kết, nơi
danh sách đầu tiên là tất cả mọi người với tên Alice.
Danh sách thứ hai là tất cả với tên bắt đầu với A, bắt đầu
với B, và vv.
>> Chiều dài khả năng của từng là những gì những danh sách nếu chúng ta giả định một sạch đẹp
phân phối các tên từ A đến Z trên cấu trúc dữ liệu toàn bộ?
Có người n trong cấu trúc dữ liệu chia cho 26, nếu họ độc đáo
trải rộng trên toàn bộ cấu trúc dữ liệu.
Vì vậy, độ dài của mỗi chuỗi là n chia cho 26.
Nhưng trong ký hiệu O lớn, đó là những gì?
Đó thực sự là những gì?
Vì vậy, nó thực sự chỉ là n, phải không?
Bởi vì chúng tôi đã nói trong quá khứ, rằng ugh bạn chia cho 26.
Có, trong thực tế nó là nhanh hơn.
Nhưng về mặt lý thuyết, nó không phải là cơ bản tất cả những gì nhanh hơn.
>> Vì vậy, chúng tôi dường như không có gì nhiều gần Chén thánh này.
Trong thực tế, đây chỉ là thời gian tuyến tính.
Heck, vào thời điểm này, tại sao chúng ta không chỉ cần sử dụng một danh sách liên kết rất lớn?
Tại sao chúng ta không chỉ cần sử dụng một trong rất lớn mảng để lưu trữ tên của
tất cả mọi người trong phòng không?
Vâng, ở đó vẫn còn một cái gì đó hấp dẫn về một bảng băm?
Ở đó vẫn còn một cái gì đó hấp dẫn về một cấu trúc dữ liệu
trông như thế này?
Này.
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Đúng, và một lần nữa khi nó chỉ một thời gian thuật toán tuyến tính, và một
thời gian tuyến tính cấu trúc dữ liệu, tại sao không tôi chỉ lưu trữ tên của tất cả mọi người trong một lớn
mảng, hoặc trong một danh sách liên kết lớn?
Và ngăn chặn làm cho CS rất nhiều khó khăn hơn hơn nó cần phải được?
Là những gì hấp dẫn về điều này, thậm chí mặc dù tôi trầy xước nó ra?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Insertions không?
Đắt tiền nữa.
Vì vậy, có khả năng chèn có thể vẫn có thời gian liên tục, ngay cả khi dữ liệu của bạn
cấu trúc như thế này, một loạt các con trỏ, mỗi trong số đó là chỉ tại
có khả năng một danh sách liên kết.
Làm thế nào bạn có thể đạt được liên tục chèn thời gian của tên?
Dính nó ở phía trước, phải không?
>> Nếu chúng ta hy sinh một mục tiêu thiết kế từ trước đó, nơi mà chúng tôi muốn giữ
tên của tất cả mọi người, ví dụ, sắp xếp, hoặc tất cả các số trên sân khấu được sắp xếp,
Giả sử chúng ta có một danh sách liên kết được phân loại.
Nó chỉ chi phí cho chúng tôi một hoặc hai bước, như trong trường hợp của Ben và Brian
trước đó, để chèn một phần tử ở đầu danh sách.
Vì vậy, nếu chúng ta không quan tâm đến phân loại tất cả của tên bắt đầu bằng A hoặc tất cả
những cái tên bắt đầu với B, chúng tôi vẫn có thể đạt được chèn thời gian liên tục.
Bây giờ nhìn lên Alice hay Bob hoặc tên bất kỳ nói chung là vẫn còn những gì?
Đó là O lớn của n khi chia 26, trong trường hợp lý tưởng, nơi tất cả mọi người là thống nhất
phân phối, nơi có nhiều của một như có Z, mà có lẽ là
không thực tế.
Nhưng đó vẫn là tuyến tính.
>> Nhưng ở đây, chúng ta trở lại điểm ký hiệu tiệm cận là
về mặt lý thuyết đúng.
Nhưng trong thế giới thực, nếu tôi cho rằng chương trình của tôi có thể làm điều gì đó 26 lần
nhanh hơn bạn, có chương trình bạn sẽ thích sử dụng?
Bạn hay của tôi, mà là 26 lần nhanh hơn?
Thực tế, người có là 26 lần nhanh hơn, ngay cả khi về mặt lý thuyết
các thuật toán của chúng tôi chạy trong cùng một tiệm cận thời gian chạy.
>> Hãy để tôi đưa ra một khác nhau giải pháp hoàn toàn.
Và nếu điều này không thổi tâm trí của bạn, chúng tôi đang trên cấu trúc dữ liệu.
Vì vậy, đây là nó một Trie -
loại một tên ngu ngốc.
Nó xuất phát từ khả năng tìm lại, và từ được viết Trie, t-r-i-e, vì
Tất nhiên hồi âm thanh như Trie.
Nhưng đó là lịch sử của Trie từ.
>> Vì vậy, một Trie thực sự là một số loại cây, và nó cũng là một cách chơi từ đó.
Và mặc dù bạn có thể không hoàn toàn nhìn thấy nó với hình dung này, một Trie là một
cây cấu trúc, giống như một cây gia đình với một tổ tiên ở đầu và rất nhiều
các cháu và chắt như lá ở phía dưới.
Nhưng mỗi nút trong một Trie là một mảng.
Và nó trong một mảng - và chúng ta hãy đơn giản hóa cho một thời điểm - đó là một
mảng, trong trường hợp này, các kích thước 26, nơi mỗi nút lại là một mảng có kích thước
26, trong đó yếu tố thứ không trong đó mảng đại diện cho A, và cuối cùng
yếu tố trong mỗi ví dụ mảng đại diện cho Z.
>> Vì vậy, tôi đề nghị, sau đó, dữ liệu này cấu trúc, được biết đến như một Trie, có thể
cũng được sử dụng để lưu trữ từ.
Chúng ta đã thấy một thời điểm trước đây như thế nào chúng ta có thể lưu trữ từ, hoặc trong trường hợp này tên, và chúng tôi
đã thấy trước đó như thế nào chúng ta có thể lưu trữ số, nhưng nếu chúng ta tập trung vào tên hoặc dây
ở đây, nhận thấy có gì thú vị.
Tôi cho rằng các tên Maxwell là bên trong của cấu trúc dữ liệu này.
Nơi nào bạn nhìn thấy Maxwell?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Trên trái.
Vì vậy, điều thú vị với dữ liệu này cấu trúc là thay vì lưu trữ các
chuỗi M-A-X-W-E-L-L dấu chéo ngược bằng không, tất cả liên tục kế nhau, thay vì những gì bạn làm
là sau đây.
Nếu đây là một Trie như cấu trúc dữ liệu, mỗi nút mà lại là một mảng,
và bạn muốn lưu trữ Maxwell, bạn đầu tiên chỉ số và do đó nút của gốc, vì vậy
để nói chuyện, nút trên cùng, tại địa điểm M, đúng, vì vậy
khoảng vào trung lộ.
Và sau đó từ đó, bạn thực hiện theo một con trỏ tới một nút con, vậy để nói chuyện.
Vì vậy, trong ý nghĩa cây gia đình, bạn làm theo nó xuống.
Và dẫn bạn đến một nút khác trên bên trái có, đó là
chỉ là một mảng.
>> Và sau đó nếu bạn muốn lưu trữ Maxwell, bạn tìm thấy những con trỏ đại diện cho
A, đó là một trong những điều này ở đây.
Sau đó, bạn đi đến nút tiếp theo.
Và thông báo - đây là lý do tại sao của hình ảnh một chút lừa dối -
nút này nhìn siêu nhỏ.
Nhưng ở bên phải của việc này là Y và Z. Nó chỉ là tác giả đã cắt ngắn
hình ảnh để bạn thực sự nhìn thấy mọi thứ.
Nếu không hình ảnh này sẽ là vô cùng rộng.
Vì vậy, bây giờ bạn chỉ vào vị trí X, sau đó W, Sau đó, E, sau đó L, sau đó L. Sau đó, những gì
sự tò mò này?
>> Vâng, nếu chúng ta đang sử dụng loại này mới mất làm thế nào để lưu trữ một chuỗi trong một
cấu trúc dữ liệu, bạn vẫn cần phải về cơ bản đánh dấu vào trong các dữ liệu
cấu trúc một từ kết thúc ở đây.
Nói cách khác, mỗi một nút bằng cách nào đó phải nhớ rằng chúng ta
thực sự sau tất cả những con trỏ và để lại một chút
bánh cốm ở dưới đây này cấu trúc để chỉ M-A-X-W-E-L-L là
thực sự trong cấu trúc dữ liệu này.
>> Vì vậy, chúng ta có thể làm điều này như sau.
Mỗi nút trong hình chúng ta chỉ cưa có một người, một mảng có kích thước 27.
Và nó bây giờ 27, vì trong p thiết lập sáu, chúng tôi sẽ thực sự cung cấp cho bạn một dấu nháy đơn,
vì vậy chúng tôi có thể có những cái tên như O'Reilly và những người khác với dấu nháy.
Nhưng cùng một ý tưởng.
Mỗi của những yếu tố trong điểm mảng tới một cấu trúc
nút, vì vậy chỉ cần một nút.
Vì vậy, đây là rất gợi nhớ của danh sách liên kết của chúng tôi.
>> Và sau đó tôi có một Boolean, mà tôi sẽ gọi từ, mà chỉ có được
đúng nếu một từ kết thúc tại đây nút trong cây.
Nó có hiệu quả đại diện cho ít tam giác chúng ta đã thấy một thời điểm trước đây.
Vì vậy, nếu một từ kết thúc tại đó nút trong cây, mà lĩnh vực từ đó sẽ là sự thật,
được khái niệm kiểm tra tắt, hoặc chúng tôi đang vẽ hình tam giác này, có có
là một từ đây.
>> Vì vậy, đây là một Trie.
Và bây giờ câu hỏi là, những gì được của nó thời gian chạy?
Là nó lớn O n?
Nó là cái gì khác?
Vâng, nếu bạn có n tên trong dữ liệu này cấu trúc, Maxwell là một trong
họ, thời gian hoạt động là những gì chèn hoặc tìm Maxwell?
Thời gian hoạt động là những gì chèn Maxwell?
Nếu có n tên khác đã có trong bảng?
Yeah?
>> HỌC SINH: [nghe được].
>> SPEAKER 1: Vâng, đó là chiều dài của tên, phải không?
Vì vậy, M-một-x-w-e-l-l để nó cảm thấy như thế này thuật toán là O lớn trong bảy.
Bây giờ, tất nhiên, tên sẽ thay đổi chiều dài.
Có lẽ đó là một tên ngắn.
Có lẽ đó là một tên dài hơn.
Nhưng điều quan trọng ở đây là đó là một số không đổi.
Và có lẽ nó không thực sự liên tục, nhưng thần, nếu thực tế, trong một
từ điển, có lẽ một số giới hạn về số lượng ký tự trong một
tên của người đó trong một quốc gia cụ thể.
>> Và vì vậy chúng tôi có thể giả định rằng giá trị là một hằng số.
Tôi không biết nó là gì.
Đây có thể là lớn hơn chúng tôi nghĩ rằng đó là.
Bởi vì luôn có một số góc trường hợp với một tên dài điên.
Vì vậy, chúng ta hãy gọi nó k, nhưng nó vẫn là một liên tục có lẽ, bởi vì mỗi
tên trên thế giới, ít nhất là trong một quốc gia cụ thể, đó là chiều dài hoặc
ngắn hơn, vì vậy nó không đổi.
Nhưng khi chúng tôi đã nói điều gì đó lớn O của một giá trị cố định, những gì mà
thực sự tương đương với?
Đó thực sự là điều tương tự cho biết thời gian liên tục.
>> Bây giờ chúng ta đang loại gian lận, phải không?
Chúng tôi đang loại tận dụng một số lý thuyết đây để nói rằng tốt, thứ tự của k là
thực sự chỉ cần đặt hàng của một, và đó là thời gian liên tục.
Nhưng nó thực sự là.
Bởi vì cái nhìn sâu sắc quan trọng ở đây là nếu chúng ta có n tên đã có trong này
cấu trúc dữ liệu, và chúng tôi chèn Maxwell, là lượng thời gian cần chúng tôi
chèn Maxwell ở tất cả bị ảnh hưởng bao nhiêu người khác
là trong cấu trúc dữ liệu?
Dường như không có.
Nếu tôi có một tỷ phần nhiều đến thế này Trie, và sau đó chèn Maxwell, được
ông ở tất cả các ảnh hưởng?
Không.
Và đó là không giống như bất kỳ dữ liệu ngày cấu trúc, chúng tôi đã nhìn thấy vậy, đến nay, nơi
thời gian chạy của thuật toán của bạn là hoàn toàn độc lập với bao nhiêu
là công cụ hoặc chưa được trong cấu trúc dữ liệu.
>> Và như vậy với điều này dành cho bạn bây giờ là một cơ hội cho p bộ sáu, sẽ
một lần nữa liên quan đến việc thực hiện của riêng bạn kiểm tra chính tả, đọc trong 150.000
từ ngữ, cách tốt nhất để lưu trữ mà không nhất thiết phải rõ ràng.
Và mặc dù tôi đã khao khát tìm Chén thánh, tôi không
cho rằng một Trie là.
Trong thực tế, một bảng băm có thể rất tốt chứng minh được hiệu quả hơn.
Nhưng đó chỉ là -
đó chỉ là một trong những quyết định thiết kế bạn sẽ phải thực hiện.
>> Nhưng trong đóng cửa, chúng ta hãy 50 hoặc hơn giây để có một cái nhìn vào những gì nằm
tuần trước tiếp theo và xa hơn nữa, chúng tôi chuyển tiếp từ dòng lệnh này
thế giới nếu các chương trình C để điều web dựa và các ngôn ngữ như PHP và
JavaScript và internet chính nó, các giao thức như HTTP, mà bạn đã
dùng cho các cấp nhiều năm bây giờ, và gõ hầu hết tất cả
ngày, có lẽ, hoặc nhìn thấy.
Và chúng tôi sẽ bắt đầu để vỏ lại lớp của những gì là internet.
Và mã là những gì mà nền tảng công cụ hiện nay.
Vì vậy, 50 giây trêu ghẹo này đây.
Tôi cung cấp cho bạn chiến binh của mạng Internet.
>> [VIDEO xem lại]
>> -Ông đến 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 của bức tường lửa độc ác, không quan tâm thiết bị định tuyến, và nguy hiểm hơn
tồi tệ hơn cả cái chết.
Anh ấy nhanh.
Anh ấy mạnh mẽ.
Anh ấy là TCPIP.
Và ông đã nhận địa chỉ của bạn.
Chiến binh của mạng Internet.
>> [END xem video]
>> SPEAKER 1: Đó là cách mạng Internet làm việc theo tuần tới.