[MUSIC CHƠI]
DAVID J. Malan: Được rồi.
Đây là CS50.
Đây là tuần năm tiếp tục, và chúng tôi có một số tin tốt và một tin xấu.
Vì vậy, tin tốt là CS50 ra mắt vào thứ sáu này.
Nếu bạn muốn tham gia với chúng tôi, đầu vào URL thông thường ở đây.
Tin tức Thậm chí tốt hơn, không có bài giảng này đến thứ hai 13.
Hơi ít tin tức tốt hơn, bài kiểm tra không là thứ tư tới.
Thông tin chi tiết có thể tìm thấy tại URL này ở đây.
Và trong vài ngày tới chúng tôi sẽ điền vào chỗ trống
liên quan đến các phòng rằng chúng tôi sẽ đã đặt.
Tin tức tốt hơn là có sẽ thấy được đánh giá quá trình toàn
phiên này tới Thứ hai vào buổi tối.
Hãy theo dõi quá trình của trang web cho vị trí và chi tiết.
Phần, mặc dù nó là một kỳ nghỉ, cũng sẽ đáp ứng là tốt.
Tin tức tốt nhất, giảng vào thứ sáu tới.
Vì vậy, đây là một truyền thống chúng tôi có, theo các giáo trình.
Just-- nó sẽ là tuyệt vời.
Bạn sẽ thấy những thứ như thời gian cố định cấu trúc dữ liệu
và các bảng và cây và cố gắng băm.
Và chúng ta sẽ nói về vấn đề sinh nhật.
Một bó toàn bộ công cụ đang chờ đợi vào thứ sáu tới.
OK.
Nhưng dù sao.
>> Vì vậy, nhớ lại rằng chúng ta đã tập trung vào hình ảnh của những gì
bên trong bộ nhớ máy tính của chúng tôi.
Vì vậy, bộ nhớ hoặc bộ nhớ RAM là nơi mà các chương trình tồn tại trong khi bạn đang chạy chúng.
Nếu bạn kích đúp vào một biểu tượng để chạy một số chương trình
hoặc nhấp đúp vào một biểu tượng để mở một số tập tin,
nó được nạp từ đĩa cứng của bạn ổ đĩa hoặc ổ đĩa trạng thái rắn
vào bộ nhớ RAM, bộ nhớ truy cập ngẫu nhiên, nơi nó sống cho đến khi bị cúp điện tắt,
nắp máy tính xách tay đóng cửa, hoặc bạn thoát khỏi chương trình.
>> Bây giờ nhớ rằng, mà bạn có thể có
1 gigabyte những ngày này, 2 gigabyte, hoặc thậm chí nhiều hơn nữa,
thường được đặt ra cho một chương trình nhất định
trong loại hình chữ nhật mô hình khái niệm
nhờ đó chúng ta có ngăn xếp ở phía dưới và một loạt các công cụ khác ở đầu trang.
Điều ở đầu chúng tôi đã nhìn thấy trên hình ảnh này
trước nhưng không bao giờ nói về là cái gọi là đoạn văn bản.
Đoạn văn bản chỉ là một cách ưa thích nói rằng các số không và những người
soạn chương trình biên dịch thực tế của bạn.
>> Vì vậy, khi bạn nhấp đúp Microsoft Word trên máy Mac hoặc máy PC của bạn,
hoặc khi bạn chạy chấm giảm Mario trên Máy tính Linux ở cửa sổ thiết bị đầu cuối của bạn,
các số không và những người soạn Word hoặc Mario được lưu trữ tạm thời
trong bộ nhớ RAM của máy tính trong cái gọi là đoạn văn bản cho một chương trình cụ thể.
Dưới đây mà đi khởi tạo và dữ liệu chưa được khởi tạo.
Đây là công cụ như biến toàn cầu, mà chúng tôi đã không được sử dụng nhiều,
nhưng vào dịp chúng tôi đã đã biến toàn cầu
hay tĩnh xác định chuỗi được mã hóa cứng từ như "hello"
không được thực hiện trong từ người sử dụng được mã hóa cứng vào chương trình của bạn.
>> Bây giờ, xuống phía dưới chúng tôi có cái gọi là chồng.
Và chồng, cho đến nay, chúng tôi đã sử dụng cho những loại mục đích?
Có gì ngăn xếp được sử dụng cho?
Vâng?
>> TƯỢNG: Chức năng.
>> DAVID J. Malan: Đối với chức năng?
Trong ý nghĩa nào cho các chức năng?
>> TƯỢNG: Khi bạn gọi một chức năng, đối số được sao chép vào stack.
>> DAVID J. Malan: Chính xác.
Khi bạn gọi một chức năng, nó đối số được sao chép vào stack.
Vì vậy, bất kỳ của X hoặc Y hoặc A hoặc B rằng bạn đang đi vào một chức năng
được tạm thời đưa vào cái gọi là chồng,
giống như một trong những Annenberg khay phòng ăn, và cũng có những thứ
như các biến địa phương.
Nếu chức năng foo hoặc trao đổi của bạn chức năng có các biến địa phương,
như nhiệt độ, hai kết thúc trên stack.
Bây giờ, chúng tôi sẽ không nói quá nhiều về họ, nhưng các biến môi trường
ở phía dưới chúng ta đã thấy trong một thời gian trước khi Tôi đã futzing vào bàn phím một ngày
và tôi bắt đầu truy cập thứ như argv 100 hoặc argv 1000,
chỉ elements-- tôi quên các numbers-- nhưng điều đó
đã không có quyền được truy cập bởi tôi.
Chúng tôi bắt đầu nhìn thấy một số biểu tượng sôi nổi trên màn hình.
Đó là những cái gọi là biến môi trường
như thiết lập chung cho tôi chương trình cho máy tính của tôi, không
không liên quan đến gần đây lỗi mà chúng ta đã thảo luận,
Shellshock, đó là được gây rắc rối cho một vài máy tính.
>> Bây giờ cuối cùng, tập trung ngày hôm nay cuối cùng chúng ta sẽ có trên heap.
Đây là một đoạn bộ nhớ.
Và về cơ bản tất cả điều này bộ nhớ là những thứ tương tự.
Đó là cùng một phần cứng.
Chúng tôi loại điều trị các cụm khác nhau
của byte cho các mục đích khác nhau.
Các đống cũng sẽ là nơi biến và bộ nhớ mà bạn yêu cầu
từ hệ điều hành được lưu trữ tạm thời.
>> Nhưng có loại của một vấn đề ở đây, như hình ảnh ngụ ý.
Chúng tôi có hai loại tàu sắp va chạm.
Bởi vì khi bạn sử dụng nhiều hơn và nhiều hơn nữa của chồng, và như chúng ta thấy ngày nay
trở đi, khi bạn sử dụng nhiều hơn và nhiều hơn nữa của đống, chắc chắn những điều xấu có thể xảy ra.
Và quả thực, chúng ta có thể tạo ra mà cố ý hoặc vô ý.
Vì vậy, cuối cùng cliffhanger thời gian là chương trình này,
mà không phục vụ cho bất kỳ chức năng mục đích nào khác hơn là để chứng minh
làm thế nào bạn như một kẻ xấu thực sự có thể lợi dụng lỗi trong chương trình của một ai đó
và đi qua một chương trình hoặc thậm chí một toàn bộ hệ thống máy tính hoặc máy chủ.
Như vậy chỉ cần lướt qua một thời gian ngắn, bạn nhận thấy rằng chính ở phía dưới
mất trong dòng lệnh lập luận, theo argv.
Và nó có một cuộc gọi đến một hàm f, cơ bản là một chức năng không tên gọi
f, và nó đi qua trong argv [1].
>> Vì vậy, bất cứ điều gì từ các loại sử dụng trong lúc dấu nhắc sau khi tên của chương trình này,
và sau đó chức năng này tùy ý lên đầu, e, mất trong một chuỗi, AKA char *,
như chúng tôi đã bắt đầu thảo luận, và nó chỉ gọi nó là "quán bar."
Nhưng chúng ta có thể gọi nó là bất cứ điều gì.
Và sau đó nó tuyên bố, bên trong f, một mảng ký tự
gọi là c-- 12 ký tự như vậy.
>> Bây giờ, bởi những câu chuyện tôi đã nói một thời điểm trước đây, nơi mà trong bộ nhớ
là c, hoặc là những người 12 ký tự sẽ kết thúc?
Chỉ cần được rõ ràng.
Vâng?
>> TƯỢNG: Trên stack.
>> DAVID J. Malan: Trên stack.
Vì vậy, c là một biến địa phương.
Chúng tôi đang yêu cầu 12 ký tự hoặc 12 byte.
Những người sẽ kết thúc về cái gọi là chồng.
Bây giờ cuối cùng là chức năng khác này đó là thực sự khá hữu ích,
nhưng chúng tôi đã không thực sự sử dụng nó chính mình, strncopy.
Nó có nghĩa là sao chép chuỗi, nhưng chỉ có n chữ cái, n ký tự.
Vì vậy, n ký tự sẽ sao chép từ thanh vào c.
Và bao nhiêu?
Chiều dài của thanh.
Vì vậy, nói cách khác, đó một dòng, strncopy,
sẽ sao chép hiệu quả thanh vào c.
>> Bây giờ, chỉ để loại dự đoán đạo đức của câu chuyện này,
những gì là khả năng có vấn đề ở đây?
Mặc dù chúng tôi đang kiểm tra chiều dài thanh và đi qua nó vào strncopy,
những gì được đường ruột của bạn nói với bạn là vẫn bị hỏng về chương trình này?
Vâng?
>> TƯỢNG: Không bao gồm phòng cho các ký tự null.
DAVID J. Malan: Không bao gồm phòng cho các ký tự null.
Có khả năng, không giống như trong thực hành qua, chúng tôi thậm chí không
có rất nhiều như là một cộng thêm 1 để thích rằng nhân vật null.
Nhưng nó thậm chí còn tệ hơn nữa.
Chúng tôi những gì khác không làm gì?
Vâng?
>> TƯỢNG: [không nghe được]
DAVID J. Malan: hoàn hảo.
Chúng tôi đã cứng mã hoá 12 khá tùy tiện.
Đó không phải là quá nhiều vấn đề, nhưng thực tế
mà chúng ta thậm chí không kiểm tra nếu chiều dài của thanh là dưới 12,
trong trường hợp này sẽ là an toàn để đặt nó vào trong bộ nhớ
gọi là c mà chúng tôi đã được phân bổ.
Thật vậy, nếu thanh giống như 20 ký tự,
chức năng này dường như được sao chép 20 nhân vật từ thanh vào c, do đó
tham gia ít nhất 8 byte rằng nó không nên.
Đó là ý nghĩa ở đây.
>> Vì vậy, trong ngắn hạn chương trình, bị hỏng.
Không phải là một vấn đề lớn.
Có lẽ bạn nhận được một lỗi phân khúc.
Tất cả chúng ta đã có lỗi trong chương trình.
Chúng ta đều có thể có lỗi trong các chương trình ngay bây giờ.
Tuy nhiên, ý nghĩa là gì?
Vâng, đây là một phiên bản thu nhỏ trong các mà hình ảnh của bộ nhớ máy tính của tôi.
Đây là dưới cùng của ngăn xếp của tôi.
Và quả thực, ở dưới cùng là những gì gọi là chồng thường xuyên phụ huynh, cách ưa thích
nói đó là chính.
Vì vậy, bất cứ ai gọi là chức năng e rằng chúng ta đang nói về.
Vì vậy, đây là đáy của ngăn xếp.
Địa chỉ trở lại là một cái gì đó mới.
Nó luôn ở đó, luôn ở trong hình ảnh đó.
Chúng tôi không bao giờ được gọi là chú ý đến nó.
Bởi vì nó chỉ ra các cách c công trình là rằng khi một cuộc gọi chức năng khác,
không chỉ làm các đối số cho rằng chức năng được đẩy vào stack,
không chỉ làm địa phương của hàm biến được đẩy vào stack,
một cái gì đó gọi là địa chỉ trở lại cũng được đưa vào ngăn xếp.
Cụ thể, nếu cuộc gọi chính foo, của chính địa chỉ riêng trong bộ nhớ, con bò một cái gì đó,
hiệu quả được đưa vào ngăn xếp để khi f được thực hiện thực hiện nó
biết nơi để nhảy trở lại trong văn bản phân khúc để tiếp tục thực hiện.
>> Vì vậy, nếu chúng ta ở đây khái niệm, trong chính, sau đó f được gọi là.
Làm thế nào để biết ai f để kiểm soát tay trở lại?
Vâng, điều này ít mẩu bánh mì màu đỏ ở đây,
được gọi là địa chỉ trả lại, nó chỉ kiểm tra, địa chỉ trở lại là gì?
Oh, hãy để tôi nhảy trở lại chính ở đây.
Và đó là một chút của một sự đơn giản hóa,
vì số không và những người cho chính về mặt kỹ thuật
ở đây trong phân khúc công nghệ cao.
Nhưng đó là ý tưởng. f chỉ cần có để biết những gì
đến nơi kiểm soát cuối cùng quay trở lại.
>> Nhưng các máy tính cách từ lâu đã đặt ra những điều
như các biến địa phương và đối số là như thế này.
Vì vậy, trong đầu hình ảnh này trong màu xanh là khung stack cho f, vì vậy tất cả
của bộ nhớ f đặc biệt là sử dụng.
Vì vậy, theo đó, nhận thấy rằng thanh là trong ảnh này.
Bar là lập luận của mình.
Và chúng tôi cho rằng lập luận để chức năng được đẩy vào stack.
Và c, tất nhiên, là cũng trong ảnh này.
>> Và chỉ cho mục đích ký hiệu, nhận thấy ở góc phía trên bên trái
là những gì sẽ là c khung 0 và sau đó giảm nhẹ về bên phải
là c khung 11.
Vì vậy, nói cách khác, bạn có thể tưởng tượng rằng có một mạng lưới các byte
ở đó, đầu tiên là trên bên trái, phía dưới đó
là cuối cùng của những 12 byte.
>> Nhưng bây giờ cố gắng để nhanh chóng về phía trước.
Là những gì sắp xảy ra nếu chúng tôi vượt qua trong một quán bar chuỗi dài hơn c?
Và chúng tôi không kiểm tra nếu nó thực sự dài hơn 12.
Mà một phần của bức tranh này là sẽ được ghi đè bởi byte 0, 1, 2, 3,
dot dot dot, 11, và sau đó xấu, 12, 13 đến 19?
Điều gì sẽ xảy ra ở đây, nếu bạn suy ra từ đặt hàng
mà khung c 0 là trên đầu trang và c khung 11 là loại xuống
bên phải?
Vâng?
>> TƯỢNG: Vâng, nó sẽ để ghi đè lên char * quán bar.
>> DAVID J. Malan: Vâng, có vẻ như bạn sẽ ghi đè lên char * quán bar.
Và tồi tệ hơn, nếu bạn gửi trong một thực sự lâu dài chuỗi, bạn thậm chí có thể ghi đè lên những gì?
Địa chỉ hồi âm.
Mà một lần nữa, giống như một mẩu bánh mì để cho các chương trình mà
quay trở lại khi f được thực hiện được gọi.
>> Vì vậy, những gì kẻ xấu thường làm là nếu họ đi qua một chương trình
rằng họ đang tò mò xem là khai thác, lỗi theo cách như vậy
rằng họ có thể mất lợi dụng lỗi,
nói chung là họ không nhận được quyền này lần đầu tiên.
Họ chỉ bắt đầu gửi, ví dụ, chuỗi ngẫu nhiên vào chương trình của bạn,
dù ở bàn phím, hay nói thẳng là họ có thể
viết một chương trình nhỏ để chỉ tự động tạo ra các chuỗi,
và bắt đầu đập vào chương trình của bạn bằng cách gửi vào rất nhiều yếu tố đầu vào khác nhau
ở độ dài khác nhau.
>> Ngay sau khi tai nạn chương trình của bạn, đó là một điều tuyệt vời.
Bởi vì nó có nghĩa là ông hay cô đã phát hiện ra
những gì có lẽ thực sự là một lỗi.
Và sau đó họ có thể nhận được thông minh hơn và bắt đầu tập trung hẹp hơn
làm thế nào để khai thác lỗi.
Đặc biệt, những gì em có thể làm là gửi, trong trường hợp tốt nhất, xin chào.
Không có vấn đề lớn.
Đó là một chuỗi đó là đủ ngắn.
Nhưng nếu anh ta hoặc cô gửi, và chúng tôi sẽ khái quát nó như là,
tấn công code-- nên số không và những người mà làm những việc
như rm-rf, mà loại bỏ tất cả mọi thứ từ ổ đĩa cứng hoặc gửi thư rác
hoặc bằng cách nào đó tấn công máy tính này?
>> Vì vậy, nếu mỗi người trong các chữ cái từ A đến như biểu tượng,
khái niệm, tấn công, tấn công, tấn công, tấn công, một số mã xấu
mà người khác đã viết, nhưng nếu người đó là đủ thông minh
không chỉ bao gồm tất cả những rm-RFS, mà còn
có vài byte cuối cùng của mình là một con số tương ứng
đến địa chỉ của mình mình mã tấn công riêng
rằng người đó đã thông qua chỉ bằng cách cung cấp nó tại dấu nhắc,
bạn có hiệu quả có thể lừa máy tính vào nhận thấy khi f được thực hiện thực hiện,
oh, đó là thời gian cho tôi để nhảy trở lại địa chỉ trở lại màu đỏ.
Nhưng vì người đó có bằng cách nào đó chồng chéo địa chỉ trở lại
với số lượng riêng của họ, và họ đủ thông minh
đã cấu hình mà số để tham khảo, như bạn
nhìn thấy trong siêu hàng đầu bên trái góc đó,
địa chỉ thực tế của máy tính bộ nhớ của một số mã tấn công của họ,
một kẻ xấu có thể lừa máy tính vào thực thi mã riêng của mình.
>> Và mã số đó, một lần nữa, có thể là bất cứ điều gì.
Nó thường được gọi là mã shell, mà chỉ là
một cách khác để nói rằng nó không phải nói chung là một cái gì đó đơn giản như rm-rf.
Nó thực sự là một cái gì đó giống như Bash, hoặc một chương trình thực tế mà đưa cho anh
hoặc điều khiển chương trình của mình để thực hiện bất cứ thứ gì họ muốn.
Vì vậy, trong ngắn hạn, điều này tất cả xuất phát từ thực tế đơn giản
rằng lỗi này liên quan không kiểm tra ranh giới của mảng của bạn.
Và bởi vì đường máy tính làm việc là họ
sử dụng ngăn xếp từ hiệu quả, khái niệm,
dưới lên trên, nhưng sau đó các yếu tố bạn đẩy vào ngăn xếp phát triển trên xuống dưới,
này là cực kỳ có vấn đề.
Bây giờ, có nhiều cách để làm việc này.
Và thẳng thắn mà nói, có những ngôn ngữ mà để làm việc này.
Java là miễn dịch, ví dụ, đến vấn đề này cụ thể.
Bởi vì họ không cung cấp cho bạn con trỏ.
Họ không cung cấp cho bạn địa chỉ bộ nhớ trực tiếp.
Vì vậy, với quyền lực này mà chúng ta có chạm vào bất cứ điều gì trong bộ nhớ
chúng tôi muốn đến, thừa nhận, nguy cơ rất lớn.
>> Vì vậy, giữ một mắt ra.
Nếu, thẳng thắn, trong những tháng hoặc năm tới, bất cứ lúc nào
bạn đọc về một số khai thác của một chương trình hoặc một máy chủ,
nếu bạn đã bao giờ nhìn thấy một dấu hiệu của một cái gì đó như một cuộc tấn công tràn bộ đệm,
hoặc tràn stack là một kiểu khác tấn công, tinh thần tương tự,
nhiều như truyền cảm hứng cho trang web của tên, nếu bạn biết điều đó,
đó là tất cả nói về chỉ tràn kích thước của một số nhân vật
mảng hoặc một mảng nói chung.
Mọi câu hỏi, sau đó, về điều này?
Đừng cố gắng này ở nhà.
>> Tất cả các quyền.
Vì vậy, malloc vậy, đến nay đã được mới của chúng tôi người bạn ở đó chúng ta có thể cấp phát bộ nhớ
mà chúng ta không nhất thiết phải biết tiến mà chúng ta muốn nên chúng tôi không có
cứng mã thành của chúng tôi số chương trình như 12.
Một khi người sử dụng cho chúng ta biết bao nhiêu dữ liệu mà họ muốn đầu vào,
chúng ta có thể malloc nhiều bộ nhớ.
>> Vì vậy, malloc nó quay ra, vào mức độ nào đó, chúng tôi đã sử dụng nó,
một cách rõ ràng thời gian qua, và sau đó các bạn đã được sử dụng nó
cho GetString vô cho vài tuần, tất cả các bộ nhớ của malloc
xuất phát từ cái gọi là heap.
Và đây là lý do tại sao getString, ví dụ, có thể cấp phát bộ nhớ động
mà không biết những gì bạn đang sẽ đánh trước,
trao lại cho bạn một con trỏ tới bộ nhớ, và bộ nhớ vẫn là của bạn để giữ,
ngay cả sau khi GetString lợi nhuận.
Bởi vì thu hồi sau khi tất cả những gì ngăn xếp được liên tục đi lên và xuống,
lên và xuống.
Và ngay khi nó đi xuống, có nghĩa là bất kỳ bộ nhớ
Chức năng này được sử dụng nên không được sử dụng bởi bất cứ ai khác.
Đó là giá trị rác bây giờ.
>> Nhưng đống lên ở đây.
Và những gì tốt đẹp về malloc là khi malloc cấp phát bộ nhớ lên đây,
nó không bị ảnh hưởng, cho nhất một phần, bởi chồng.
Và vì vậy bất kỳ chức năng có thể truy cập bộ nhớ đã được malloc'd,
ngay cả bởi một chức năng như getString, ngay cả sau khi nó được trả về.
>> Bây giờ, chuyện của malloc là miễn phí.
Và quả thực, các quy tắc bạn cần phải bắt đầu áp dụng
là bất kỳ, bất kỳ, bất cứ lúc nào bạn sử dụng malloc bản thân bạn phải sử dụng miễn phí, cuối cùng,
vào đó con trỏ tương tự.
Tất cả thời gian này, chúng tôi đã được viết lỗi, mã lỗi, vì nhiều lý do.
Tuy nhiên, một trong số đó đã được sử dụng thư viện CS50, mà
chính nó là cố tình lỗi, nó rò rỉ bộ nhớ.
Bất cứ lúc nào bạn đã gọi là getString trong vài tuần qua
chúng tôi yêu cầu các hoạt động hệ thống, Linux, cho bộ nhớ.
Và bạn đã bao giờ một lần cho nó trở lại.
Và đây không phải là, trong thực hành, một điều tốt.
>> Và Valgrind, một trong những các công cụ được giới thiệu trong Pset 4,
là tất cả về giúp bạn bây giờ tìm thấy lỗi như thế.
Nhưng may mắn cho Pset 4 bạn không cần sử dụng thư viện CS50 hoặc getString.
Vì vậy, bất kỳ lỗi nào liên quan đến bộ nhớ cuối cùng sẽ là của riêng bạn.
>> Vì vậy, malloc là nhiều hơn chỉ thuận tiện cho mục đích này.
Chúng ta có thể thực hiện giải quyết vấn đề cơ bản khác nhau,
và cơ bản giải quyết vấn đề hơn hiệu quả như là một lời hứa tuần số không.
Cho đến nay đây là gợi cảm nhất cấu trúc dữ liệu chúng ta đã có.
Và bởi cấu trúc dữ liệu tôi chỉ có nghĩa là một cách khái niệm bộ nhớ
trong một cách mà vượt xa chỉ cần nói, đây là một int, đây là một char.
Chúng tôi có thể bắt đầu điều cụm lại với nhau.
>> Vì vậy, một mảng trông như thế này.
Và những gì là quan trọng trong khoảng một mảng là nó cung cấp cho bạn
back-to-back khối bộ nhớ, mỗi trong số đó
là có được cùng loại, int, int, int, int, hoặc char, char, char,
char.
Nhưng có một vài nhược điểm.
Điều này ví dụ, là một mảng có kích thước sáu.
Giả sử bạn điền vào mảng này với sáu số và sau đó, vì bất cứ lý do,
người dùng của bạn muốn cung cấp cho bạn một số thứ bảy.
Nơi nào bạn đặt nó?
>> Giải pháp là gì nếu bạn có tạo ra một mảng trên stack,
Ví dụ, chỉ với tuần hai ký hiệu mà chúng tôi giới thiệu,
trong dấu ngoặc vuông với một số bên trong?
Vâng, bạn đã có sáu con số trong các ô.
Những gì bản năng của bạn sẽ là gì?
Trong trường hợp bạn muốn đặt nó?
>> TƯỢNG: [không nghe được]
>> DAVID J. Malan: Xin lỗi?
>> TƯỢNG: Đặt nó vào cuối.
>> DAVID J. Malan: Đặt nó vào cuối.
Vì vậy, chỉ hơn bên phải, bên ngoài của hộp này.
Đó sẽ là tốt đẹp, nhưng nó Hóa ra bạn không thể làm điều đó.
Bởi vì nếu bạn đã không hỏi cho đoạn này của bộ nhớ,
nó có thể là do trùng hợp ngẫu nhiên rằng điều này đang được sử dụng bởi một số biến khác
hoàn toàn.
Hãy suy nghĩ lại một tuần hoặc lâu hơn khi chúng ta đặt ra Zamyla và Davin và Gabe của tên
trong bộ nhớ.
Họ nghĩa đen trở lại trở lại trở lại.
Vì vậy, chúng ta có thể không nhất thiết phải tin tưởng rằng bất cứ điều gì của
ở đây có sẵn cho tôi để sử dụng.
>> Vì vậy, những gì khác bạn có thể làm gì?
Vâng, một khi nhận ra bạn cần một mảng có kích thước bảy,
bạn chỉ có thể tạo ra một mảng có kích thước bảy sau đó sử dụng
một vòng lặp hoặc một vòng lặp trong khi, sao chép nó vào mảng mới,
và sau đó bằng cách nào đó chỉ có được loại bỏ mảng này hoặc chỉ cần ngừng sử dụng nó.
Nhưng đó không phải là đặc biệt hiệu quả.
Trong ngắn hạn, các mảng không cho phép bạn tự động thay đổi kích thước.
>> Vì vậy, một mặt bạn sẽ có được truy cập ngẫu nhiên, mà là tuyệt vời.
Bởi vì nó cho phép chúng tôi làm những việc như phân chia và chinh phục,
tìm kiếm nhị phân, tất cả chúng tôi đã nói về trên màn hình ở đây.
Nhưng bạn vẽ mình vào một góc.
Ngay sau khi bạn nhấn kết thúc của mảng của bạn,
bạn phải làm rất hoạt động đắt tiền
hoặc viết một bó toàn bộ mã đến nay giải quyết vấn đề đó.
>> Vì vậy, nếu thay vào đó chúng tôi đã có một cái gì đó gọi là một danh sách,
hoặc một danh sách liên kết đặc biệt?
Điều gì nếu thay vì phải hình chữ nhật sao lưu để sao lưu để sao lưu,
chúng tôi có hình chữ nhật để lại một chút bit của căn phòng thoải mái ở giữa chúng?
Và mặc dù tôi đã vẽ này hình ảnh hoặc điều chỉnh hình ảnh này
từ một trong những văn bản vào đây để được trở lại trở lại trở lại rất có trật tự, trong thực tế,
một trong những hình chữ nhật có thể lên ở đây trong bộ nhớ.
Một trong số đó có thể lên ở đây.
Một trong số đó có thể lên đây, ở đây, và vv.
>> Nhưng nếu chúng ta thu hút, trong trường hợp này, mũi tên
mà bằng cách nào đó liên kết các hình chữ nhật với nhau?
Thật vậy, chúng tôi đã nhìn thấy một kỹ thuật hóa thân của một mũi tên.
Chúng ta đã sử dụng trong gần đây ngày đó, bên dưới mui xe,
là đại diện của một mũi tên?
Một con trỏ, phải không?
>> Vì vậy, nếu những gì, thay vì chỉ lưu trữ các số,
như 9, 17, 22, 26, 34, nếu chúng ta không lưu trữ
chỉ có một số nhưng một con trỏ bên cạnh mỗi số như vậy?
Vì vậy, giống như bạn sẽ một sợi kim thông qua một bó toàn bộ vải,
điều bằng cách nào đó buộc với nhau, tương tự có thể
chúng tôi với con trỏ, như nhập thể bởi mũi tên ở đây,
loại đan xen với nhau các hình chữ nhật cá nhân
bởi hiệu quả sử dụng một con trỏ bên cạnh mỗi số đó
chỉ ra một số số tiếp theo, đó chỉ ra, lần lượt, một số số tiếp theo?
Vì vậy, nói cách khác, những gì nếu chúng ta thực sự muốn
để thực hiện một cái gì đó như thế này?
Cũng may, những hình chữ nhật, ít nhất là một với 9, 17, 22,
và vv, đây là những không còn quảng trường đẹp với những con số duy nhất.
Phía dưới, hình chữ nhật 9 dưới đây, ví dụ,
đại diện cho những gì nên là một con trỏ, 32 bit.
Bây giờ, tôi chưa biết về bất kỳ kiểu dữ liệu trong C cung cấp cho bạn không chỉ là một int
nhưng một con trỏ hoàn toàn.
>> Vì vậy, giải pháp là gì nếu chúng ta muốn phát minh ra câu trả lời của chúng tôi với điều này?
Vâng?
>> TƯỢNG: [không nghe được]
>> DAVID J. Malan: Cái gì thế?
>> TƯỢNG: cấu trúc mới.
>> DAVID J. Malan: Vâng, vậy tại sao chúng ta không tạo ra một cấu trúc mới,
hoặc C, một cấu trúc?
Chúng tôi đã nhìn thấy cấu trúc trước đây, nếu một thời gian ngắn, nơi mà chúng tôi xử lý một cấu trúc sinh viên
như thế này, những người có một cái tên và một ngôi nhà.
Trong Pset 3 đột phá mà bạn sử dụng toàn bộ bó GRect structs-- và GOvals
mà Stanford tạo ra để thông tin cụm lại với nhau.
Vì vậy, nếu chúng ta có ý tưởng này cùng các từ khóa "typedef" và "cấu trúc"
và sau đó một số công cụ sinh viên cụ thể, và phát triển này như sau:
struct node-- và nút là chỉ là một khoa học máy tính rất chung chung
hạn cho một cái gì đó trong một cấu trúc dữ liệu, một thùng chứa trong một cấu trúc dữ liệu.
Một nút tôi yêu cầu là sẽ có một int n, hoàn toàn đơn giản,
và sau đó một chút khó hiểu hơn, Dòng thứ hai này, cấu trúc nút * tiếp theo.
Nhưng về kỹ thuật ít hơn, dòng thứ hai là gì
mã bên trong dấu ngoặc nhọn?
Vâng?
>> TƯỢNG: [không nghe được]
DAVID J. Malan: Một con trỏ đến một nút khác.
Vì vậy, phải thừa nhận rằng, cú pháp một chút khó hiểu.
Nhưng nếu bạn đọc nó theo nghĩa đen, tiếp theo là tên của một biến.
Kiểu dữ liệu của nó là gì?
Đó là một chút dài dòng thời gian này, nhưng nó có cấu trúc kiểu nút *.
Bất cứ lúc nào chúng tôi đã nhìn thấy một cái gì đó sao, mà có nghĩa là nó là một con trỏ đến kiểu dữ liệu.
Vì vậy, tiếp theo rõ ràng là một con trỏ đến một nút cấu trúc.
>> Bây giờ, một nút cấu trúc là gì?
Vâng, chú ý bạn sẽ thấy những cùng một từ ở bên phải.
Và quả thực, bạn cũng thấy từ "Nút" xuống đây ở dưới cùng bên trái.
Và điều này thực sự chỉ là một tiện nghi.
Chú ý rằng trong định nghĩa sinh viên của chúng tôi có từ "sinh viên" chỉ một lần.
Và đó là bởi vì một sinh viên đối tượng không được tự tham chiếu.
Không có gì bên trong của một học sinh là cần để trỏ đến học sinh khác,
persay.
Đó sẽ là loại kỳ lạ trong thế giới thực.
>> Nhưng với một nút trong một liên kết danh sách, chúng tôi muốn có một nút
được tham chiếu đến một đối tượng tương tự.
Và vì thế nhận thấy sự thay đổi ở đây không phải là chỉ là những gì bên trong các dấu ngoặc nhọn.
Nhưng chúng ta thêm từ "nút" ở đầu cũng như
thêm nó vào phía dưới thay cho "học sinh."
Và đây chỉ là một chi tiết kỹ thuật do đó, một lần nữa, cấu trúc dữ liệu của bạn
có thể tự tham chiếu, do đó một nút có thể trỏ đến một nút khác như vậy.
>> Vì vậy, đây là những gì cuối cùng sẽ có ý nghĩa đối với chúng ta?
Vâng, một, công cụ này bên trong là nội dung của nút của chúng tôi.
Điều này lên đây, trên bên phải, chỉ là như vậy
rằng, một lần nữa, chúng ta có thể tham khảo cho mình.
Và sau đó những thứ ngoài cùng, mặc dù nút là một thuật ngữ mới,
có lẽ, nó vẫn còn giống như học sinh và những gì
là dưới mui xe trong SPL.
>> Vì vậy, nếu bây giờ chúng ta muốn bắt đầu thực hiện danh sách liên kết này,
làm thế nào chúng ta có thể dịch một cái gì đó như thế này để mã?
Vâng, chúng ta chỉ thấy một ví dụ về một chương trình
thực sự sử dụng một danh sách liên kết.
Trong số đang phân phối hiện nay là một chương trình được gọi là Danh sách Zero.
Và nếu tôi chạy này tôi tạo ra một siêu giao diện đơn giản, giao diện đồ họa người dùng,
nhưng nó thực sự chỉ là printf.
Và bây giờ tôi đã cho bản thân mình một vài đơn options-- Xóa, Chèn, tìm kiếm,
và Traverse.
Và Thoát.
Đây là những hoạt động phổ biến chỉ trên cấu trúc dữ liệu được biết đến như một danh sách liên kết.
>> Bây giờ, xóa sẽ xóa một số từ danh sách.
Chèn sẽ thêm một số vào danh sách.
Tìm kiếm được sẽ xem xét cho số lượng trong danh sách.
Và đi qua chỉ là một cách ưa thích nói, đi bộ qua danh sách,
in nó ra, nhưng đó là nó.
Không thay đổi nó bằng mọi cách.
>> Vì vậy, hãy cố gắng này.
Chúng ta hãy đi trước và loại 2.
Và sau đó tôi sẽ chèn số, nói 9.
Enter.
Và giờ đây, chương trình của tôi chỉ là lập trình để nói, bây giờ là danh sách 9.
Bây giờ, nếu tôi đi trước và làm Chèn một lần nữa, chúng ta hãy
tôi đi trước và thu nhỏ và gõ 17.
Bây giờ danh sách của tôi là 9, sau đó 17.
Nếu tôi làm chèn một lần nữa, chúng ta hãy bỏ qua một.
Thay vì 22, theo hình ảnh chúng tôi đã được xem xét ở đây, hãy để tôi nhảy trước
và chèn 26 tới.
Vì vậy, tôi sẽ gõ 26.
Danh sách này là như tôi mong đợi.
Nhưng bây giờ, chỉ để xem nếu mã này là có được linh hoạt, cho tôi bây giờ
22 loại, trong đó ít nhất khái niệm, nếu chúng ta
việc giữ này được sắp xếp, mà thực sự là sẽ là một mục tiêu ngay bây giờ,
nên đi ở giữa 17 và 26.
Vì vậy, tôi nhấn Enter.
Thật vậy, mà các công trình.
Và vì vậy bây giờ hãy để tôi chèn cuối cùng, mỗi hình ảnh, 34.
>> Tất cả các quyền.
Vì vậy, bây giờ hãy để tôi quy định rằng Xóa và Traverse và tìm kiếm làm,
trên thực tế, làm việc.
Trong thực tế, nếu tôi chạy tìm kiếm, chúng ta hãy tìm kiếm số 22, Enter.
Kết quả cho thấy 22.
Vì vậy, đó là những gì này Danh sách chương trình Zero, không.
>> Nhưng những gì đang thực sự xảy ra trên mà thực hiện điều này?
Vâng, đầu tiên tôi có thể có, và thực sự Tôi có một tập tin gọi là list0.h.
Và ở đâu đó trong có này dòng, typedef, cấu trúc nút,
Sau đó tôi có dấu ngoặc nhọn của tôi, int n, và sau đó struct-- là những gì định nghĩa?
Nút cấu trúc tiếp theo.
Vì vậy, chúng ta cần ngôi sao.
Bây giờ về mặt kỹ thuật, chúng tôi nhận được vào thói quen vẽ nó ở đây.
Bạn có thể thấy sách giáo khoa và tài liệu tham khảo trực tuyến làm nó ở đó.
Đó là chức năng tương đương.
Trong thực tế, đây là điển hình hơn một chút.
Nhưng tôi sẽ phù hợp với những gì chúng tôi đã làm thời gian qua và làm được điều này.
Và rồi cuối cùng, tôi sẽ làm điều này.
>> Vì vậy, trong một tập tin tiêu đề ở đâu đó, trong list0.h
hôm nay là định nghĩa cấu trúc này, và có thể một số nội dung khác.
Trong khi đó tại list0c có sẽ có một vài điều.
Nhưng chúng ta sẽ chỉ bắt đầu và không kết thúc này.
List0.h là một tập tin tôi muốn bao gồm trong tập tin C của tôi.
Và sau đó tại một số điểm tôi sẽ có int, chính, làm mất hiệu lực.
Và sau đó tôi sẽ có một số việc phải làm ở đây.
Tôi cũng sẽ có một nguyên mẫu, như bãi bỏ, tìm kiếm, int,
n, có mục đích trong cuộc sống là để tìm kiếm một phần tử.
Và sau đó xuống đây tôi yêu cầu bồi thường trong Mã ngày nay, bãi bỏ, tìm kiếm, int, n,
không có dấu chấm phẩy nhưng dấu ngoặc nhọn mở.
Và bây giờ tôi muốn bằng cách nào đó tìm kiếm cho một phần tử trong danh sách này.
Nhưng chúng ta không có đủ thông tin trên màn hình được nêu ra.
Tôi đã không thực sự đại diện trong danh sách riêng của mình.
Vì vậy, một trong những cách chúng ta có thể thực hiện một danh sách liên kết trong một chương trình
là tôi loại muốn làm điều gì đó như tuyên bố danh sách liên kết ở đây.
Để đơn giản, tôi sẽ làm cho toàn cầu này, mặc dù trong chúng ta nói chung
không nên làm điều này quá nhiều.
Nhưng nó sẽ đơn giản hóa ví dụ này.
Vì vậy, tôi muốn khai báo một danh sách liên kết ở đây.
Bây giờ, làm thế nào tôi có thể làm điều đó?
>> Dưới đây là hình ảnh của một danh sách liên kết.
Và tôi không thực sự biết tại thời điểm này như thế nào
Tôi sẽ đi về đại diện quá nhiều thứ chỉ với một
biến trong bộ nhớ.
Nhưng nghĩ lại một chút.
Tất cả thời gian này, chúng tôi đã có chuỗi, mà chúng tôi sau đó
tiết lộ là mảng nhân vật, mà chúng tôi sau đó
tiết lộ chỉ là một con trỏ để ký tự đầu tiên
trong một loạt các ký tự đó là null chấm dứt.
Vì vậy, theo logic, và với điều này hình ảnh loại hạt giống suy nghĩ của bạn,
những gì chúng tôi thực sự cần viết của chúng tôi mã để đại diện cho một danh sách liên kết?
Làm thế nào nhiều thông tin này chúng ta cần để nắm bắt trong mã C, bạn sẽ nói gì?
Vâng?
>> TƯỢNG: Chúng tôi cần một con trỏ đến một nút.
DAVID J. Malan: Một con trỏ tới một nút.
Đặc biệt, trong đó nút sẽ của bạn bản năng là giữ một con trỏ đến?
>> TƯỢNG: Nút đầu tiên.
>> DAVID J. Malan: Yeah, có lẽ chỉ là người đầu tiên.
Và hãy chú ý, lần đầu tiên nút là một hình dạng khác nhau.
Đó chỉ là một nửa kích thước của cấu trúc, bởi vì nó thực sự chỉ là một con trỏ.
Vì vậy, những gì bạn thực sự có thể làm là khai báo một danh sách liên kết là các loại nút *.
Và chúng ta hãy gọi nó là đầu tiên và khởi tạo nó thành vô giá trị.
Vì vậy, vô giá trị, một lần nữa, là tới vào hình ảnh ở đây.
Không chỉ được sử dụng như rỗng như một đặc biệt giá trị trả về cho những thứ như getString
và malloc, null cũng là số không con trỏ, thiếu một con trỏ,
nếu bạn sẽ.
Nó chỉ có nghĩa là không có gì là có ở đây.
Bây giờ đầu tiên, tôi có thể đã gọi là bất cứ điều gì này.
Tôi có thể gọi đó là "danh sách" hoặc bất kỳ số lượng những thứ khác.
Nhưng tôi gọi đó là "đầu tiên" để nó lên đường với hình ảnh này.
Vì vậy, giống như một chuỗi có thể được biểu với địa chỉ của byte đầu tiên của nó,
vì vậy có thể một danh sách liên kết.
Và chúng ta sẽ thấy các dữ liệu khác cấu trúc được đại diện
chỉ với một con trỏ, một mũi tên 32-bit, chỉ
tại nút đầu tiên trong cấu trúc.
>> Nhưng bây giờ chúng ta hãy dự đoán một vấn đề.
Nếu tôi chỉ nhớ trong chương trình của tôi địa chỉ
của nút đầu tiên, là người đầu tiên hình chữ nhật trong cấu trúc dữ liệu này,
những gì đã tốt hơn là trường hợp về thực hiện phần còn lại của danh sách của tôi?
Một chi tiết quan trọng đó là sẽ là những gì để đảm bảo điều này thực sự hoạt động?
Và bởi "thực sự hoạt động" Tôi có nghĩa là, giống như một chuỗi,
cho phép chúng tôi đi từ ký tự đầu tiên tên Davin để lần thứ hai,
đến thứ ba, cho thứ tư, cho đến cuối cùng,
làm thế nào để chúng ta biết khi nào chúng tôi ở cuối của một danh sách liên kết trông như thế này?
Khi đó là null.
Và tôi đã đại diện cho loại này là như một kỹ sư điện mạnh,
với nền tảng ít biểu tượng, các loại.
Nhưng điều đó chỉ có nghĩa là vô giá trị trong trường hợp này.
Bạn có thể vẽ nó bất kỳ số cách khác nhau, nhưng tác giả này
đã xảy ra để sử dụng biểu tượng này ở đây.
>> Vì vậy, miễn là chúng ta đang xâu chuỗi tất cả các nút với nhau,
chỉ nhớ nơi đầu tiên là, miễn
khi chúng ta đặt một biểu tượng đặc biệt tại nút cuối cùng trong danh sách,
và chúng tôi sẽ sử dụng vô giá trị, bởi vì đó là những gì chúng tôi có sẵn cho chúng tôi,
danh sách này hoàn tất.
Và ngay cả khi tôi chỉ cung cấp cho bạn một con trỏ đến các yếu tố đầu tiên, bạn, các lập trình viên,
chắc chắn có thể truy cập vào phần còn lại của nó.
Nhưng chúng ta hãy để cho tâm trí của bạn đi lang thang một chút,
nếu họ không đã khá wandered-- gì
sẽ là thời gian chạy của tìm kiếm bất cứ điều gì trong danh sách này?
Chết tiệt, đó là O lớn của n, đó không phải là xấu, công bằng.
Nhưng nó là tuyến tính.
Chúng tôi đã từ bỏ những gì tính năng các mảng bằng cách di chuyển hơn
đối với hình ảnh của động đan xen với nhau hoặc liên kết các nút?
Chúng tôi đã từ bỏ truy cập ngẫu nhiên.
Một mảng là tốt đẹp vì toán học tất cả mọi thứ
là trở lại trở lại để trở lại trở lại.
Mặc dù hình ảnh này vẻ đẹp, và thậm chí
mặc dù nó trông giống như các nút độc đáo được cách nhau, trong thực tế
họ có thể là bất cứ nơi nào.
OX1, Ox50, Ox123, Ox99, các các nút có thể là bất cứ nơi nào.
Bởi vì malloc không cấp phát bộ nhớ từ đống, nhưng bất cứ nơi nào trong đống.
Bạn không nhất thiết phải biết rằng nó sẽ trở lại trở lại trở lại.
Và như vậy hình này trong thực tế của không có được khá xinh đẹp này.
>> Vì vậy, nó sẽ mất một chút làm việc để thực hiện chức năng này.
Vì vậy, hãy thực hiện tìm kiếm ngay bây giờ.
Và chúng ta sẽ thấy loại một cách thông minh để làm điều này.
Vì vậy, nếu tôi là một chức năng tìm kiếm và Tôi cho một biến, số nguyên n
tìm kiếm, tôi cần phải biết cú pháp mới để tìm kiếm bên trong
của một cấu trúc đó là chỉ ra, để tìm n.
Vì vậy, hãy làm điều này.
>> Vì vậy, đầu tiên tôi sẽ đi trước và tuyên bố một nút *.
Và tôi sẽ gọi nó con trỏ, chỉ cần theo quy ước.
Và tôi sẽ khởi tạo nó đầu tiên.
Và bây giờ tôi có thể làm điều này trong một số cách.
Nhưng tôi sẽ có cách tiếp cận phổ biến.
Trong khi con trỏ không bằng null, và đó là cú pháp hợp lệ.
Và nó chỉ có nghĩa là làm như sau, vì vậy miễn là bạn không chỉ ở không có gì.
Tôi muốn làm gì?
>> Nếu con trỏ điểm n, hãy để tôi trở lại đó, equals-- bằng gì?
Giá trị những gì tôi đang tìm kiếm?
N thực tế đã được thông qua.
Vì vậy, đây là tính năng khác C và nhiều ngôn ngữ.
Mặc dù cấu trúc gọi là nút có n giá trị, hoàn toàn hợp pháp
cũng có một tham số địa phương hoặc biến được gọi là n.
Bởi vì ngay cả chúng tôi, với đôi mắt của con người, có thể phân biệt
rằng n này có lẽ là khác nhau từ n này.
Bởi vì cú pháp là khác nhau.
Bạn đã có một dấu chấm và một con trỏ, trong khi một này không có điều như vậy.
Vì vậy, đây là OK.
Đó là OK để gọi họ là những điều tương tự.
>> Nếu tôi để bạn tìm thấy điều này, tôi sẽ muốn làm điều gì đó
như thông báo rằng chúng tôi thấy n.
Và chúng tôi sẽ rời khỏi đó như là một bình luận hoặc mã giả.
Khác, và đây là Phần thú vị, những gì
Tôi muốn làm gì nếu nút hiện tại không chứa n mà tôi quan tâm?
Làm thế nào để đạt được những điều sau đây?
Nếu ngón tay của tôi tại thời điểm là PTR, và nó
chỉ tay vào bất cứ điều gì đầu tiên là chỉ vào,
làm thế nào để di chuyển ngón tay của tôi đến nút tiếp theo trong mã?
Vâng, mẩu bánh mì chúng tôi là những gì đi theo trong trường hợp này?
TƯỢNG: [không nghe được].
DAVID J. Malan: Vâng, vì vậy tiếp theo.
Vì vậy, nếu tôi quay trở lại của tôi mã ở đây, thực sự, tôi
sẽ đi trước và nói con trỏ, mà chỉ là một variable-- tạm thời nó
một tên lạ, ptr, nhưng nó chỉ giống như temp--
Tôi sẽ đặt con trỏ bằng bất cứ con trỏ is--
và một lần nữa, điều này là có được một lỗi nhỏ cho một dấu chấm moment-- tiếp theo.
Nói cách khác, tôi sẽ lấy của tôi ngón tay trỏ vào nút này
ở đây và tôi sẽ nói, bạn biết những gì, hãy nhìn vào lĩnh vực tiếp theo
và di chuyển ngón tay của bạn để bất cứ điều gì nó chỉ tay vào.
Và điều này sẽ lặp lại, lặp lại, lặp lại.
Nhưng khi nào ngón tay của tôi ngừng làm bất cứ điều gì ở tất cả?
Ngay sau khi những dòng mã trong đá?
TƯỢNG: [không nghe được]
DAVID J. Malan: Nếu điểm trong khi con trỏ không bằng null.
Tại một số điểm ngón tay của tôi sẽ được chỉ vào vô
và tôi sẽ thực hiện đó là kết thúc của danh sách này.
Bây giờ, đây là một chút lời nói dối trắng cho đơn giản.
Nó chỉ ra rằng mặc dù chúng ta chỉ biết ký hiệu dấu chấm này
cho các cấu trúc, con trỏ không phải là một cấu trúc.
ptr là gì?
Chỉ cần được nitpicky hơn.
Đó là một con trỏ đến một nút.
Nó không phải là một nút riêng của mình.
Nếu tôi không có ngôi sao ở đây, con trỏ absolutely-- đó là một nút.
Điều này giống như một tuần khai báo của một biến,
mặc dù từ "nút" là mới.
>> Nhưng ngay khi chúng tôi giới thiệu một sao, bây giờ là một con trỏ đến một nút.
Và thật không may, bạn không thể sử dụng các ký hiệu dấu chấm cho một con trỏ.
Bạn phải sử dụng mũi tên ký hiệu, trong đó, nổi bật,
là lần đầu tiên bất cứ mảnh cú pháp trông trực quan.
Điều này nghĩa đen trông giống như một mũi tên.
Và đó là một điều tốt.
Và ở đây theo nghĩa đen trông giống như một mũi tên.
Vì vậy, tôi nghĩ rằng đó là la-- tôi không nghĩ rằng tôi quá phạm here-- tôi
nghĩ đó là tác phẩm mới nhất cú pháp của chúng ta sẽ nhìn thấy.
Và may mắn thay, nó thực sự nhiều hơn một chút trực quan.
>> Bây giờ, đối với những người bạn của những người có thể thích theo cách cũ,
bạn vẫn có thể sử dụng các ký hiệu dấu chấm.
Tuy nhiên, theo thứ hai của cuộc trò chuyện, chúng tôi đầu tiên
cần phải đến đó, đi đến đó giải quyết, và sau đó truy cập vào lĩnh vực này.
Vì vậy, đây cũng là chính xác.
Và thẳng thắn mà nói, đây là một ít mô phạm hơn.
Bạn đang nói theo nghĩa đen, tới đích con trỏ và đi đến đó.
Sau đó lấy .n, lĩnh vực được gọi là n.
Nhưng thẳng thắn mà nói, không ai muốn gõ hoặc đọc này.
Và như vậy trên thế giới phát minh ra các ký hiệu mũi tên, mà
là tương đương, giống hệt nhau, nó chỉ là cú pháp đường.
Vì vậy, một cách nói này có vẻ tốt hơn, hoặc trông đơn giản hơn.
>> Vì vậy, bây giờ tôi sẽ làm một việc khác.
Tôi sẽ nói "phá vỡ" một khi tôi đã tìm thấy nó vì vậy tôi không tiếp tục tìm kiếm cho nó.
Nhưng đây là ý chính các chức năng tìm kiếm.
Nhưng nó dễ dàng hơn rất nhiều, trong kết thúc, không đi qua các mã.
Điều này thực sự là việc thực hiện chính thức tìm trong mã phân phối hiện nay.
Tôi dám nói chèn đó không phải là đặc biệt thú vị để đi bộ qua
trực quan, cũng không phải là xóa, thậm chí mặc dù vào cuối ngày
họ đun sôi xuống khá chẩn đoán đơn giản.
>> Vì vậy, hãy làm điều này.
Nếu bạn sẽ hài hước tôi ở đây, tôi đã làm mang lại một loạt các quả bóng căng thẳng.
Tôi mang một loạt các con số.
Và chúng tôi có thể nhận được chỉ là một vài tình nguyện viên để đại diện cho 9, 17, 20, 22, 29 và 34?
Vì vậy, về cơ bản tất cả mọi người người ở đây ngày hôm nay.
Đó là một, hai, ba, bốn, năm, sáu người.
Và tôi đã được yêu cầu go-- thấy, không có một ở phía sau nâng bàn tay của họ.
OK, một, hai, ba, bốn, five-- cho tôi tải balance-- sáu.
OK, bạn sáu đến ngày lên.
Chúng ta sẽ cần những người khác.
Chúng tôi đưa quả bóng căng thẳng thêm.
Và nếu bạn có thể, chỉ là một khoảnh khắc, dòng
hãy tự lập chỉ như hình ảnh này ở đây.
>> Tất cả các quyền.
Hãy xem, tên của bạn là gì?
>> TƯỢNG: Andrew.
>> DAVID J. Malan: Andrew, bạn là số 9.
Rất vui được gặp bạn.
Ở đây bạn đi.
TƯỢNG: Jen.
DAVID J. Malan: Jen.
David.
Số 17.
Có?
>> TƯỢNG: Tôi là Julia.
>> DAVID J. Malan: Julia, David.
Số 20.
TƯỢNG: Kitô giáo.
DAVID J. Malan: Kitô giáo, David.
Số 22.
Và?
>> TƯỢNG: JP.
DAVID J. Malan: JP.
Số 29.
Vì vậy, đi trước và nhận được in-- Uh oh.
Uh oh.
Chế độ chờ.
20.
Có ai có một dấu hiệu?
TƯỢNG: Tôi đã có một Sharpie.
DAVID J. Malan: Bạn có một Sharpie?
OK.
Và không ai có một mảnh giấy?
Lưu bài giảng.
Thôi nào.
TƯỢNG: Chúng tôi đã có nó.
DAVID J. Malan: Chúng tôi đã nhận nó?
Được rồi, cảm ơn bạn.
Ở đây chúng ta đi.
Được điều này từ bạn?
Bạn chỉ cần lưu lại trong ngày.
Vì vậy, 29.
Tất cả các quyền.
Tôi sai chính tả 29, nhưng OK.
Về phía trước.
Được rồi, tôi sẽ cung cấp cho bạn bút của bạn trở lại trong giây lát.
Vì vậy, chúng tôi có những người ở đây.
Hãy có một khác.
Gabe, bạn muốn chơi các yếu tố đầu tiên ở đây?
Chúng tôi cần bạn chỉ ở những người này tốt.
Vì vậy, 9, 17, 20, 22, sắp xếp 29, 34 và sau đó.
Chúng ta đã mất đi một người nào đó?
Tôi có một 34.
Trường hợp did-- OK, ai muốn trở thành 34?
OK, đến ngày lên, 34.
Được rồi, đây sẽ là cũng có giá trị cao trào.
Tên của bạn là gì?
>> TƯỢNG: Peter.
>> DAVID J. Malan: Peter, đi lên trên.
Được rồi, vì vậy đây là một bó toàn bộ các nút.
Mỗi của các bạn đại diện cho một trong những hình chữ nhật.
Và Gabe, hơi kỳ quặc con người ra, đại diện đầu tiên.
Vì vậy, con trỏ của mình là nhỏ hơn một chút trên màn hình hơn so với những người khác.
Và trong trường hợp này, mỗi bên trái của bạn tay sẽ hoặc chỉ xuống,
do đó đại diện cho null, vì vậy chỉ sự vắng mặt của một con trỏ,
hoặc nó sẽ được trỏ tại một nút bên cạnh bạn.
>> Vì vậy, ngay bây giờ nếu bạn tô điểm mình giống như hình ảnh
ở đây, đi trước và điểm nhau, với Gabe
trong trỏ đặc biệt là ở số 9 đại diện trong danh sách.
OK, và số 34, tay trái của bạn chỉ nên được trỏ xuống sàn nhà.
>> OK, vì vậy đây là danh sách liên kết.
Vì vậy, đây là kịch bản trong câu hỏi.
Và quả thực, đây là đại diện của một lớp học của các vấn đề
mà bạn có thể cố gắng giải quyết với mã.
Bạn muốn cuối cùng chèn một nguyên tố mới vào danh sách.
Trong trường hợp này, chúng ta sẽ thử chèn số 55.
Tuy nhiên, sẽ là trường hợp khác nhau để xem xét.
Và quả thực, điều này là có được một của hình ảnh lớn takeaways ở đây, là,
các trường hợp khác nhau là gì.
Điều gì là khác nhau nếu có điều kiện hoặc chi nhánh rằng chương trình của bạn có thể có?
>> Vâng, số lượng bạn đang cố gắng để chèn, mà chúng ta biết bây giờ là 55,
nhưng nếu bạn không biết trước, tôi dám chắc
rơi vào ít nhất ba tình huống có thể.
Trường hợp có một nguyên tố mới được?
TƯỢNG: Và cuối hoặc trung bình.
DAVID J. Malan: Cuối cùng, trong giữa, hoặc ngay từ đầu.
Vì vậy, tôi khẳng định có ít nhất ba vấn đề chúng ta cần phải giải quyết.
Hãy chọn những gì có thể cho là đơn giản nhất
một, nơi mà các nguyên tố mới thuộc ngay từ đầu.
Vì vậy, tôi sẽ có mã khá như tìm kiếm, mà tôi chỉ viết.
Và tôi sẽ phải ptr, mà Tôi sẽ đại diện ở đây với ngón tay của tôi,
như thường lệ.
>> Và hãy nhớ, những gì giá trị chúng tôi đã khởi tạo ptr?
Vì vậy, chúng tôi khởi tạo nó thành vô giá trị ban đầu.
Nhưng sau đó, những gì chúng ta đã làm một lần chúng tôi ở bên trong chức năng tìm kiếm của chúng tôi?
Chúng tôi thiết lập nó bằng đầu tiên, đó không có nghĩa là làm điều này.
Nếu tôi đặt ptr bằng đầu tiên, những gì nên bàn tay của tôi thực sự là chỉ tay vào?
Đúng.
Vì vậy, nếu Gabe và tôi sẽ có giá trị tương đương ở đây,
chúng ta cần cả hai điểm ở vị trí thứ 9.
>> Vì vậy, đây là sự khởi đầu của câu chuyện của chúng tôi.
Và bây giờ điều này chỉ đơn giản, mặc dù cú pháp là mới.
Khái niệm này chỉ là tìm kiếm tuyến tính.
55 bằng 9?
Hay đúng hơn, chúng ta hãy nói ít hơn 9.
Bởi vì tôi đang cố gắng để tìm ra nơi để đặt 55.
Chưa đầy 9, ít hơn 17 ít hơn, hơn 20, ít hơn 22, ít hơn 29,
ít hơn 34, không có.
Vì vậy, bây giờ chúng tôi đang ở trong trường hợp một trong ít nhất ba.
>> Nếu tôi muốn chèn 55 ​​trên đây, những gì dòng mã cần phải được thực thi?
Làm thế nào để hình ảnh này con người cần phải thay đổi?
Tôi phải làm gì với bàn tay trái của tôi không?
Điều này sẽ không có giá trị ban đầu, bởi vì tôi đang ở cuối danh sách.
Và những gì sẽ xảy ra ở đây với Peter, đúng không?
Anh ấy rõ ràng là sẽ chỉ cho tôi.
Vì vậy, tôi khẳng định có ít nhất hai dòng mã trong các mẫu mã từ hôm nay
đó là sẽ thực hiện điều này kịch bản thêm 55 ở đuôi.
Và tôi có thể có một người nào đó hop và chỉ đại diện cho 55?
Được rồi, bạn là người mới 55.
>> Vì vậy, bây giờ những gì nếu tiếp theo kịch bản đến cùng,
và chúng tôi muốn chèn vào bắt đầu hoặc người đứng đầu danh sách này?
Và tên, số 55 là gì?
>> TƯỢNG: Jack.
>> DAVID J. Malan: Jack?
OK, rất vui được gặp bạn.
Chào mừng bạn.
Vì vậy, bây giờ chúng ta sẽ chèn, nói rằng, số lượng 5.
Đây là trường hợp thứ hai của ba chúng tôi đã đưa ra trước đây.
Vì vậy, nếu 5 thuộc ngay từ đầu, chúng ta hãy xem làm thế nào chúng tôi thấy rằng ra ngoài.
Tôi khởi ptr của tôi con trỏ đến số 9 một lần nữa.
Và tôi nhận ra, oh, 5 là ít hơn 9.
Vì vậy, sửa chữa hình ảnh này cho chúng tôi.
Có bàn tay, Gabe hay David or-- tên số 9 của là gì?
>> TƯỢNG: Jen.
>> DAVID J. Malan: hands-- Jen mà bàn tay của chúng tôi cần phải thay đổi?
OK, vì vậy Gabe chỉ vào những gì bây giờ?
Tại tôi.
Tôi là nút mới.
Vì vậy, tôi sẽ chỉ loại di chuyển vào đây để xem nó trực quan.
Và khi đó tôi chỉ làm những gì mà?
Tuy nhiên, nơi tôi đang chỉ.
Vì vậy, đó là nó.
Vì vậy, chỉ thực sự một dòng mã sửa lỗi vấn đề này đặc biệt, nó sẽ có vẻ.
Được rồi, vậy thì tốt.
Và một người nào đó có thể là một giữ chỗ cho 5?
Nào lên.
Chúng tôi sẽ giúp bạn có được thời gian tới.
>> Được rồi, vậy now-- và như một sang một bên, tên
Tôi không làm cho rõ ràng đề cập đến quyền bây giờ, con trỏ pred, con trỏ trước
và con trỏ mới, đó là chỉ những cái tên được
trong mẫu mã để các con trỏ hoặc tay của tôi đó là loại chỉ xung quanh.
Tên của bạn là gì?
>> TƯỢNG: Christine.
>> DAVID J. Malan: Christine.
Chào mừng bạn.
Được rồi, vậy chúng ta hãy xem xét tại một kịch bản hơi khó chịu,
nhờ đó mà tôi muốn chèn cái gì đó như 26 thành này.
20?
Gì?
Những are-- điều tốt chúng tôi có cây bút này.
Được rồi, 20.
Nếu ai đó có thể nhận được một mảnh giấy đã sẵn sàng, chỉ trong case-- rồi.
Ồ, thú vị.
Vâng đây là một ví dụ một lỗi bài giảng.
OK vì vậy tên của bạn là gì nữa?
TƯỢNG: Julia.
DAVID J. Malan: Julia, bạn có thể bật ra và giả vờ như bạn không bao giờ có?
OK, điều này không bao giờ xảy ra.
Cảm ơn bạn.
Vì vậy, giả sử chúng ta muốn chèn Julia vào danh sách liên kết này.
Cô là số 20.
Và tất nhiên cô ấy sẽ thuộc về các
begin-- không chỉ vào bất cứ điều gì được nêu ra.
Vì vậy, bàn tay của bạn có thể loại xuống null hoặc một số giá trị rác.
Hãy kể câu chuyện nhanh chóng.
Tôi chỉ vào số 5 lần này.
Sau đó, tôi kiểm tra 9.
Sau đó, tôi kiểm tra 17.
Sau đó, tôi kiểm tra 22.
Và tôi nhận ra, ooh, Julia cần phải đi trước ngày 22.
Vì vậy, những gì cần phải xảy ra?
Có bàn tay cần phải thay đổi?
Julia, tôi, or-- Tên của bạn là gì nữa?
>> TƯỢNG: Kitô giáo.
>> DAVID J. Malan: Kitô giáo hay?
>> TƯỢNG: Andy.
>> DAVID J. Malan: Andy.
Kitô giáo hay Andy?
Andy cần để trỏ tại?
Julia.
Tất cả các quyền.
Vì vậy, Andy, bạn muốn chỉ ở mức Julia?
Nhưng chờ một phút.
Trong câu chuyện cho đến nay, Tôi là loại một
phụ trách, theo nghĩa là con trỏ là điều đó là
di chuyển qua danh sách.
Chúng ta có thể có một tên cho Andy, nhưng không có biến gọi là Andy.
Các chỉ biến khác mà chúng tôi có là đầu tiên, người đại diện của Gabe.
>> Vì vậy, đây thực sự là lý do tại sao như vậy, đến nay chúng tôi đã không cần thiết này.
Nhưng bây giờ trên màn hình có đề cập đến một lần nữa con trỏ pred.
Vì vậy, hãy để tôi được rõ ràng hơn.
Nếu đây là con trỏ, tôi đã tốt hơn nhận được nhiều hơn một chút thông minh
về sự lặp lại của tôi.
Nếu bạn không phiền nếu tôi qua đây một lần nữa, chỉ ở đây, chỉ ở đây.
Nhưng hãy để tôi có một con trỏ pred, con trỏ người tiền nhiệm, đó là
loại chỉ vào yếu tố tôi đã chỉ ở.
Vì vậy, khi tôi đi đây, bây giờ cập nhật tay trái của tôi.
Khi tôi đi đây cập nhật tay trái của tôi.
Và bây giờ tôi không chỉ có một con trỏ đến các yếu tố mà đi sau khi Julia,
Tôi vẫn còn có một con trỏ đến Andy, các yếu tố trước đây.
Vì vậy, bạn có thể truy cập, về cơ bản, vụn bánh mì, nếu bạn muốn,
cho tất cả các con trỏ cần thiết.
>> Vì vậy, nếu tôi chỉ vào Andy và tôi cũng chỉ
Christian, có bàn tay bây giờ sẽ được chỉ ở nơi khác?
Vì vậy, Andy bây giờ có thể chỉ vào Julia.
Julia bây giờ có thể chỉ vào Kitô giáo.
Bởi vì cô ấy có thể sao chép của tôi con trỏ tay phải của.
Và đó là một cách hiệu quả đặt bạn trở lại vào vị trí này ở đây.
Vì vậy, trong ngắn hạn, mặc dù đây chúng ta đang loại mãi mãi
để thực sự cập nhật danh sách liên kết, nhận ra
rằng các hoạt động là tương đối đơn giản.
Đó là một, hai, ba dòng mã cuối cùng.
Nhưng quấn quanh những dòng mã có lẽ
là một chút logic mà hiệu quả đặt câu hỏi, ở đâu chúng tôi?
Có phải chúng ta ngay từ đầu, giữa, hoặc cuối cùng?
>> Bây giờ, chắc chắn có một số khác hoạt động chúng ta có thể thực hiện.
Và những hình ảnh ở đây chỉ mô tả những gì chúng ta đã làm với con người.
Gì về việc loại bỏ?
Nếu tôi muốn, ví dụ, loại bỏ các số 34 hoặc 55,
Tôi có thể có cùng một loại mã, nhưng tôi sẽ cần một hoặc hai bước.
Bởi vì những gì mới?
Nếu tôi loại bỏ một người nào đó ở cuối, như số 55 và sau đó 34,
cái gì cũng có thay đổi khi tôi làm điều đó?
Tôi có phải không evict-- Tên của bạn là gì nữa?
>> TƯỢNG: Jack.
>> DAVID J. Malan: Jack.
Tôi có phải không chỉ evict-- Jack miễn phí, vậy nghĩa là Jack gọi miễn phí, hoặc ít nhất là
con trỏ có quá, nhưng bây giờ những gì cần phải thay đổi với Peter?
Bàn tay anh nên bắt đầu hướng xuống dưới.
Bởi vì ngay sau khi tôi gọi miễn phí trên Jack, nếu Peter vẫn chỉ tay vào Jack
và do đó tôi tiếp tục đi qua danh sách và con trỏ truy cập này,
đó là khi phân khúc người bạn cũ của chúng tôi lỗi thực sự có thể tiến hóa.
Bởi vì chúng tôi đã tạo bộ nhớ trở lại với Jack.
>> Bạn có thể ở lại đó lúng túng trong chỉ là một thời điểm.
Bởi vì chúng tôi chỉ có một cặp vợ chồng hoạt động cuối cùng để xem xét.
Loại bỏ người đứng đầu danh sách, hoặc beginning-- và một này
một chút khó chịu.
Bởi vì chúng ta phải biết rằng Gabe là loại đặc biệt trong chương trình này.
Vì quả thực, ông có con trỏ của mình.
Anh ấy không chỉ bị chỉ, như là gần như tất cả mọi người khác ở đây.
>> Vì vậy, khi người đứng đầu danh sách là loại bỏ, có bàn tay cần phải thay đổi bây giờ?
Tên của bạn là gì nữa?
>> TƯỢNG: Christine.
>> DAVID J. Malan: Tôi là khủng khiếp vào những cái tên, rõ ràng.
Vì vậy, Christine và Gabe, có bàn tay cần phải thay đổi
khi chúng tôi cố gắng để loại bỏ Christine, số 5, từ hình ảnh?
OK, vì vậy chúng ta hãy làm Gabe.
Gabe sẽ điểm, có lẽ, ở vị trí thứ 9.
Nhưng những gì tiếp theo sẽ xảy ra?
TƯỢNG: Christine nên là vô giá trị [không nghe được].
DAVID J. Malan: OK, chúng ta nên có thể make-- Tôi nghe nói "vô giá trị" ở đâu đó.
TƯỢNG: Null và miễn phí của mình.
DAVID J. Malan: null gì?
TƯỢNG: Null và miễn phí của mình.
DAVID J. Malan: Null và miễn phí của mình.
Vì vậy, đây là rất dễ dàng.
Và nó hoàn hảo mà bạn bây giờ loại đứng ở đó, không thuộc.
Bởi vì bạn đã tách rời khỏi danh sách.
Bạn đã có hiệu quả mồ côi từ danh sách.
Và vì vậy chúng tôi đã tốt hơn bây giờ gọi miễn phí Christine để cung cấp cho bộ nhớ trở lại.
Nếu không mỗi lần chúng tôi xóa một nút từ danh sách
chúng ta có thể làm cho danh sách ngắn hơn, nhưng không thực sự giảm
kích thước trong bộ nhớ.
Và như vậy, nếu chúng ta tiếp tục bổ sung và bổ sung thêm điều vào danh sách,
máy tính của tôi có thể nhận được chậm hơn và chậm hơn và chậm hơn,
bởi vì tôi đang chạy ra khỏi bộ nhớ, ngay cả khi tôi không thực sự
Christine sử dụng của byte bộ nhớ nữa.
>> Vì vậy, cuối cùng có khác kịch bản, loại bỏ course--
ở giữa, loại bỏ cuối cùng, như chúng ta đã thấy.
Nhưng thú vị hơn Thách thức hiện nay là
sẽ được xem xét một cách chính xác những gì thời gian chạy là.
Vì vậy, không chỉ bạn có thể giữ cho bạn mảnh giấy, nếu, Gabe,
bạn sẽ không nhớ cho tất cả mọi người một quả bóng căng thẳng.
Cảm ơn bạn rất nhiều danh sách liên kết của chúng tôi tình nguyện viên ở đây, nếu bạn có thể.
>> [Vỗ tay]
>> DAVID J. Malan: Được rồi.
Vì vậy, một vài phân tích câu hỏi sau đó, nếu tôi có thể.
Chúng tôi đã nhìn thấy ký hiệu này trước đây, O lớn và omega, cận trên
và giới hạn thấp hơn trên thời gian chạy của một số thuật toán.
Vì vậy, chúng ta hãy xem xét chỉ một vài câu hỏi.
>> Một, và chúng tôi đã nói nó trước đó, các hoạt động là những gì
thời gian tìm kiếm một danh sách về O lớn?
Có gì một trên ràng buộc về các hoạt động thời gian tìm kiếm một danh sách liên kết
thực hiện bởi các tình nguyện viên của chúng tôi ở đây?
Đó là O lớn của n, tuyến tính.
Bởi vì trong trường hợp xấu nhất, các yếu tố, như 55,
chúng ta có thể tìm kiếm có thể là nơi Jack là, tất cả các cách ở cuối.
Và thật không may, không giống như một mảng chúng ta không thể có được ưa thích thời gian này.
Mặc dù tất cả con người của chúng tôi đã sắp xếp từ yếu tố nhỏ, 5,
tất cả các cách để các phần tử lớn hơn, 55, đó thường là một điều tốt.
Nhưng những gì giả định rằng không còn cho phép chúng ta làm gì?
TƯỢNG: [không nghe được]
DAVID J. Malan: Nói một lần nữa?
TƯỢNG: Truy cập ngẫu nhiên.
DAVID J. Malan: Truy cập ngẫu nhiên.
Và lần lượt có nghĩa là chúng ta có thể không có còn sử dụng số không yếu, trực giác,
và hiển nhiên của việc sử dụng hệ nhị phân Tìm kiếm và phân chia và chinh phục.
Bởi vì mặc dù chúng ta con người có thể rõ ràng
thấy rằng Andy hoặc Kitô giáo khoảng ở giữa danh sách,
chúng tôi chỉ biết đó là một máy tính bằng cách lướt danh sách
ngay từ đầu.
Vì vậy, chúng tôi đã từ bỏ việc truy cập ngẫu nhiên.
>> O quá lớn của n bây giờ là trên ràng buộc về thời gian tìm kiếm của chúng tôi.
Những gì về omega tìm của chúng tôi?
Có gì thấp hơn bị ràng buộc vào tìm kiếm đối với một số số trong danh sách này?
TƯỢNG: [không nghe được]
DAVID J. Malan: Nói một lần nữa?
TƯỢNG: Một.
DAVID J. Malan: Một.
Vì vậy, thời gian liên tục.
Trong trường hợp tốt nhất, Christine là thực sự vào đầu danh sách.
Và chúng tôi đang tìm kiếm số 5, vì vậy chúng tôi tìm thấy cô.
Vì vậy, không có việc lớn.
Nhưng cô đã nhận được ở bắt đầu của danh sách trong trường hợp này.
Những gì về một cái gì đó giống như Xóa?
Điều gì nếu bạn muốn xóa một phần tử?
Có gì các ràng buộc trên và dưới về xóa một cái gì đó từ một liên kết
liệt kê?
TƯỢNG: [không nghe được]
DAVID J. Malan: Nói một lần nữa?
TƯỢNG: n.
DAVID J. Malan: n là thực sự là trên ràng buộc.
Bởi vì trong trường hợp xấu nhất chúng tôi cố gắng xóa Jack, như chúng ta chỉ cần làm.
Anh ấy là tất cả các cách ở cuối.
Đưa chúng ta mãi mãi, hoặc n bước để tìm thấy anh ta.
Vì vậy, đó là một ràng buộc trên.
Đó là tuyến tính, chắc chắn.
Và trường hợp tốt nhất thời gian chạy, hoặc giới hạn thấp hơn trong trường hợp tốt nhất
sẽ là thời gian liên tục.
Bởi vì có lẽ chúng ta cố gắng để xóa Christine, và chúng tôi chỉ nhận được may mắn
cô ấy lúc đầu.
Bây giờ chờ đợi một phút.
Gabe cũng là lúc đầu, và chúng tôi cũng đã phải cập nhật Gabe.
Vì vậy, đó không chỉ là một bước.
Vì vậy, nó thực sự không đổi thời gian, trong trường hợp tốt nhất,
để loại bỏ các phần tử nhỏ nhất?
Đó là, mặc dù nó có thể là hai, ba, hoặc thậm chí 100 dòng mã,
nếu đó là cùng một số dòng, không phải trong một số vòng lặp,
và độc lập với kích thước danh sách, hoàn toàn.
Xóa các phần tử ở đầu danh sách,
ngay cả khi chúng ta phải đối phó với Gabe, vẫn còn thời gian liên tục.
>> Vì vậy, đây có vẻ như một bước lớn về phía sau.
Và những gì một sự lãng phí thời gian nếu, trong tuần đầu tiên và tuần
bằng không chúng tôi đã không chỉ đang giả nhưng mã thực tế
để thực hiện một cái gì đó đăng nhập cơ sở n, hoặc đăng nhập, thay vào đó, n, cơ sở 2,
về thời gian của nó đang chạy.
Vì vậy, tại sao các heck chúng tôi muốn bắt đầu sử dụng một cái gì đó giống như một danh sách liên kết?
Yeah.
>> TƯỢNG: Vì vậy, bạn có thể thêm các yếu tố để các mảng.
DAVID J. Malan: Vì vậy, bạn có thể thêm các yếu tố để các mảng.
Và đây cũng là chủ đề.
Và chúng ta sẽ tiếp tục thấy này, này thương mại-off, nhiều
như chúng ta đã nhìn thấy một thương mại-off với sắp xếp hợp nhất.
Chúng tôi thực sự có thể tăng tốc độ tìm kiếm hoặc phân loại, thay vào đó,
nếu chúng ta dành nhiều không gian hơn chút và có một đoạn bổ sung của một bộ nhớ
hoặc một mảng để sắp xếp hợp nhất.
Nhưng chúng ta chi tiêu nhiều hơn không gian, nhưng chúng tôi tiết kiệm thời gian.
Trong trường hợp này, chúng tôi bỏ thời gian nhưng chúng tôi
tăng tính linh hoạt, năng động nếu bạn muốn,
mà được cho là một tính năng tích cực.
>> Chúng tôi cũng dành không gian.
Theo nghĩa là một liên kết danh sách đắt tiền hơn
về không gian là một mảng?
Đâu là không gian mở rộng đến từ đâu?
Vâng?
>> TƯỢNG: [không nghe được] con trỏ.
>> DAVID J. Malan: Vâng, chúng tôi cũng có con trỏ.
Vì vậy, đây là minorly gây phiền nhiễu trong đó không còn là
Tôi lưu trữ chỉ là một int để đại diện cho một int.
Tôi đang lưu trữ một int và một con trỏ, đó cũng là 32 bit.
Vì vậy, tôi nghĩa là tăng gấp đôi số lượng không gian liên quan.
Vì vậy, đó là một sự đánh đổi, nhưng đó là trong trường hợp của int.
Giả sử rằng bạn không lưu trữ int, nhưng giả sử mỗi một trong các hình chữ nhật
hoặc mỗi con người được đại diện một từ, một từ tiếng Anh mà
có thể là năm ký tự, 10 nhân vật, thậm chí có thể nhiều hơn nữa.
Sau đó thêm chỉ 32 bit hơn có thể là ít hơn của một vấn đề lớn.
>> Nếu những gì mỗi người trong số các sinh viên trong các cuộc biểu tình
có nghĩa là cấu trúc của sinh viên có tên và nhà ở và có thể
số điện thoại và Twitter xử lý và như thế nào.
Vì vậy, tất cả các trường chúng tôi bắt đầu nói về những ngày khác,
ít hơn nhiều của một việc lớn như các nút của chúng tôi trở nên thú vị hơn
và lớn để chi tiêu, eh, thêm con trỏ chỉ để liên kết chúng lại với nhau.
Nhưng thực sự, đó là một sự đánh đổi.
Và quả thực, các mã được phức tạp hơn, như bạn sẽ thấy
nhìn thấy bằng cách lướt qua mà ví dụ cụ thể.
Nhưng nếu có một số Chén thánh ở đây.
Nếu chúng ta không có một bước ngược nhưng là một bước lớn về phía trước
và thực hiện một dữ liệu cấu trúc thông qua đó chúng tôi
có thể tìm thấy các yếu tố như Jack hoặc Christine hay bất kỳ yếu tố khác
trong mảng này trong đúng thời gian cố định?
Tìm kiếm là hằng số.
Xóa là hằng số.
Chèn là hằng số.
Tất cả các hoạt động này là không đổi.
Đó sẽ là Chén thánh của chúng tôi.
Và đó là nơi chúng tôi sẽ nhận thời gian tới.
Hẹn gặp lại sau đó.