[Powered by Google Translate] [6]
[David J. Malan] [Đại học Harvard]
[Đây là CS50.] [CS50.TV]
>> Đây là CS50, và đây là sự bắt đầu của Tuần 6,
do đó, một vài công cụ mới đang có sẵn để bạn có thể tận dụng lợi thế,
là người đầu tiên trong số đó được gọi là CS50 (US).
Tỷ lệ cược là nếu bạn đang như tôi hoặc bất kỳ của những sinh viên giảng dạy,
bạn đã có thể nhìn thấy một chương trình có phong cách có vẻ một chút gì đó như thế này.
Có lẽ bạn bắt đầu cắt giảm một số góc muộn vào ban đêm, hoặc bạn sẽ đối phó với nó sau này,
và sau đó một TF hoặc CA đi qua trong giờ làm việc.
Sau đó, nó sẽ là khó khăn cho chúng tôi để đọc.
Vâng, mã này là đúng cú pháp, và nó sẽ biên dịch, và nó thực sự sẽ chạy.
Nhưng nó chắc chắn không phải là một 5 cho phong cách.
>> Nhưng bây giờ, nếu chúng ta đi vào thư mục này ở đây
và nhận thấy rằng tôi có conditions2.c-
và tôi chạy lệnh này, style50, này conditions2.c tập tin, Enter,
nhận thấy rằng nó thông báo với tôi rằng nó đã được cách điệu.
Gedit nhận thấy rằng tập tin đã được thay đổi trên đĩa,
và nếu tôi nhấp vào tải lại, tất cả các vấn đề của bạn tự động.
[Vỗ tay]
Đó là một trong những điều chúng tôi đã làm vào cuối tuần này.
Nhận ra rằng nó không hoàn hảo bởi vì có một số mã
mà nó chỉ đơn giản là không sẽ có thể phong cách hóa một cách hoàn hảo,
nhưng nhận ra điều này bây giờ là một công cụ mà bạn có thể tận dụng
nếu chỉ để dọn dẹp một số errantly đặt dấu ngoặc nhọn và muốn.
>> Nhưng hấp dẫn hơn tại là CS50 tra.
Với CS50 tra, bạn thực sự có thể thực hiện các bài kiểm tra tính chính xác tương tự
mã riêng của bạn rằng các nghiên cứu sinh giảng dạy có thể.
Đây là một dòng lệnh tiện ích mà đi kèm trong thiết bị
ngay sau khi bạn làm một update50 theo
pset 4 thông số kỹ thuật, và bạn sử dụng nó về cơ bản như thế này.
Bạn chạy check50 lệnh.
Sau đó, bạn vượt qua một đối số dòng lệnh, hay thường được gọi là một switch hoặc một lá cờ.
Nói chung, những thứ có dấu gạch ngang được gọi là một chuyển đổi
một chương trình dòng lệnh, vì vậy c quy định cụ thể
kiểm tra mà bạn muốn chạy.
>> Các bài kiểm tra mà bạn muốn chạy được xác định duy nhất bởi chuỗi này,
2012/pset4/resize.
Nói cách khác, đó chỉ là một chuỗi tùy ý, nhưng độc đáo
mà chúng tôi sử dụng để xác định các bài kiểm tra chính xác pset 4.
Và sau đó bạn chỉ định một danh sách không gian cách nhau của các tập tin mà bạn muốn tải lên
CS50 Kiểm tra phân tích.
Ví dụ, nếu tôi đi vào giải pháp của tôi đây cho resize.c-
hãy để tôi mở ra một thiết bị đầu cuối lớn hơn cửa sổ
và tôi đi trước và chạy chúng ta hãy nói check50-c 2012/pset4/resize,
và sau đó tôi đi trước và chỉ định tên của các tập tin,
resize.c, và sau đó nhấn Enter, nó nén,
nó cập nhật, nó sẽ kiểm tra, và tôi chỉ thất bại một bó toàn bộ các bài kiểm tra.
Một màu đỏ ở trên cùng bên trái nói rằng resize.c và bmp tồn tại.
Đó là thử nghiệm. Đó là câu hỏi chúng tôi hỏi.
Và nó không hài lòng vì câu trả lời là sai.
Các văn bản màu trắng dưới nó cho biết dự kiến ​​sẽ bmp.h tồn tại, và chỉ đơn giản đó là lỗi của tôi.
Tôi quên để tải nó lên, vì vậy tôi cần phải tải cả hai tập tin,
resize.c và bmp.h.
Nhưng bây giờ nhận thấy tất cả các xét nghiệm khác là màu vàng bởi vì họ đã không chạy,
và do đó, các khuôn mặt cười theo chiều dọc bởi vì anh ấy không vui cũng không buồn,
nhưng chúng tôi đã khắc phục vấn đề đó màu đỏ trước khi những người kiểm tra khác sẽ chạy.
>> Hãy để tôi sửa lỗi này.
Hãy để tôi thu nhỏ và chạy lại điều này, thời gian này với bmp.h cũng
trên dòng lệnh, Enter, và bây giờ nếu mọi việc suôn sẻ,
nó sẽ kiểm tra và sau đó trả về một kết quả của việc giữ hơi thở
tất cả các màu xanh lá cây, có nghĩa là tôi đang làm thực sự tốt trên pset 4 cho đến nay.
Bạn có thể xem và suy ra từ các văn bản mô tả ở đây
chính xác những gì chúng tôi thử nghiệm.
Chúng tôi đã thử nghiệm lần đầu tiên làm các tập tin tồn tại?
Sau đó chúng tôi đã thử nghiệm không biên dịch resize.c?
Sau đó, chúng tôi đã thử nghiệm nó không thay đổi kích thước một BMP 1x1-pixel khi n, các yếu tố thay đổi kích cỡ, là 1.
Bây giờ, nếu bạn không có ý tưởng những gì n là, bạn sẽ một khi bạn nhảy vào pset 4,
nhưng mà chỉ đơn giản là một kiểm tra sanity để đảm bảo rằng bạn không phải thay đổi kích thước
một hình ảnh ở tất cả nếu các yếu tố thay đổi kích cỡ 1.
Nếu, ngược lại, nó thay đổi kích thước một điểm ảnh 1x1 đến 1x1 điểm ảnh BMP 2x2 một cách chính xác
khi n là 2, sau đó tương tự như vậy, tôi tạo cho phù hợp.
>> Trong ngắn hạn, điều này có nghĩa là, một, đi qua ngón tay
trong số các phương trình ngay trước khi bạn gửi pset của bạn.
Bạn sẽ biết chính xác những gì TF của bạn sẽ sớm biết
khi bạn đi về gửi một số trong những bộ vấn đề,
và cũng là động lực sư phạm thực sự đặt
cơ hội ở phía trước của bạn để khi bạn biết một ưu tiên
rằng có lỗi trong mã của bạn và kiểm tra không được thông qua,
bạn có thể đặt trong thời gian hiệu quả hơn lên phía trước để giải quyết những vấn đề này
chứ không phải là bị mất điểm, nhận được phản hồi từ TF của bạn,
và sau đó đi, "Ahh," như tôi nên đã tìm ra điều đó.
Bây giờ ít nhất có một công cụ để giúp bạn tìm thấy điều đó.
Nó sẽ không chỉ ra lỗi này là, nhưng nó sẽ cho bạn biết
những gì là triệu chứng của nó.
>> Bây giờ nhận ra các bài kiểm tra không nhất thiết phải đầy đủ.
Chỉ vì bạn có được một màn hình đầy đủ của các khuôn mặt cười màu xanh lá cây
không có nghĩa là mã của bạn là hoàn hảo, nhưng nó có nghĩa là
đó đã vượt qua các xét nghiệm nhất định theo quy định của spec.
Đôi khi chúng ta sẽ không phát hành kiểm tra.
Ví dụ, whodunit, một trong những khía cạnh của pset 4,
là loại đáng thất vọng nếu chúng tôi cung cấp cho bạn
câu trả lời là những gì nó được, và có một số cách để tiết lộ
người đó là ai trong đó tiếng ồn màu đỏ.
Các spec sẽ luôn luôn xác định trong tương lai cho pset 5 trở đi
những gì kiểm tra tồn tại cho bạn.
Bạn sẽ nhận thấy có URL này màu trắng ở phía dưới.
Để bây giờ, điều này chỉ là chẩn đoán đầu ra.
Nếu bạn truy cập URL đó, bạn sẽ nhận được một bó toàn phát điên, thông điệp khó hiểu
bạn đang chào đón để xem xét thông qua, nhưng chủ yếu là cho nhân viên
để chúng tôi có thể chẩn đoán và debug lỗi trong check50 bản thân.
>> Nếu không có ado, hãy di chuyển đến nơi chúng tôi rời đi.
CS50 thư viện chúng tôi đã cho một vài tuần,
nhưng sau đó tuần trước, chúng tôi bắt đầu hé một trong các lớp của nó.
Chúng tôi bắt đầu gạt sang một bên chuỗi ủng hộ của những gì thay vì?
[Sinh viên] Char.
Char *, mà đã được một char * tất cả thời gian này,
nhưng bây giờ chúng tôi không phải giả vờ rằng đó là một chuỗi dữ liệu loại thực tế.
Thay vào đó, nó được một từ đồng nghĩa của các loại char *,
và một chuỗi là một chuỗi các ký tự,
vậy tại sao không làm cho tinh thần để đại diện cho chuỗi như là char * s?
Một char * đại diện cho điều gì trong bối cảnh này khái niệm của một chuỗi?
Vâng >> [Sinh viên] Các ký tự đầu tiên.
Tốt, ký tự đầu tiên, nhưng không hẳn là nhân vật đầu tiên.
[Sinh viên] Địa chỉ.
Tốt, địa chỉ của ký tự đầu tiên.
Tất cả đó là cần thiết để đại diện cho một chuỗi trong bộ nhớ của máy vi tính
chỉ là địa chỉ duy nhất của byte đầu tiên của nó.
Bạn thậm chí không có biết bao lâu nó
bởi vì làm thế nào bạn có thể tìm ra động?
[Sinh viên] chuỗi dài.
Bạn có thể gọi chiều dài chuỗi, tuyệt vời, nhưng làm thế nào không làm việc chiều dài chuỗi?
Làm gì? Yeah.
[Sinh viên] Tiếp tục đi cho đến khi bạn nhận được các ký tự null.
Yeah, chính xác, nó chỉ lặp đi lặp lại với một vòng lặp for, vòng lặp trong khi,
bất cứ điều gì từ * đến cùng, và cuối cùng là đại diện
\ 0, cái gọi là nhân vật nul, nul,
không nên nhầm lẫn với null, mà là một con trỏ,
sẽ đi lên trong cuộc trò chuyện ngày hôm nay.
>> Chúng tôi bóc vỏ lại một lớp getInt, và sau đó chúng tôi đã xem xét GetString,
và nhớ lại rằng cả hai những chức năng, hoặc thực sự,
GetString, bằng cách sử dụng một chức năng nhất định
thực sự phân tích, đó là, đọc hoặc phân tích, đầu vào của người dùng.
Và đó là chức năng mới là gì?
Scanf hoặc sscanf. Nó thực sự đến trong một vài hương vị khác nhau.
Có scanf, có sscanf, có fscanf.
Để bây giờ, mặc dù, chúng ta hãy tập trung vào một trong những cách dễ dàng nhất minh họa,
và cho tôi đi trước và mở ra trong thiết bị
một tập tin như thế này, scanf1.c.
Đây là một chương trình đơn giản siêu,
nhưng điều đó một cái gì đó mà chúng tôi đã không bao giờ thực hiện
mà không có sự giúp đỡ của các thư viện CS50.
Điều này được một int từ người sử dụng. Nó hoạt động như thế nào?
Vâng, trong dòng 16 đó,
nhận thấy rằng chúng ta khai báo một x được gọi là int, và vào thời điểm này trong câu chuyện,
giá trị của x là gì?
[Không nghe được sinh viên phản ứng]
[David M. phải, những người hiểu biết, một số giá trị rác có khả năng, vì vậy trong 17, chúng tôi chỉ nói cho người dùng
cung cấp cho tôi một số, xin vui lòng, và bước 18 là nơi nó được thú vị.
Scanf dường như mượn một ý tưởng từ printf trong đó nó sử dụng các mã định dạng trong dấu ngoặc kép.
% D tất nhiên là một số thập phân.
Nhưng tại sao tôi đi qua trong & x thay vì chỉ x?
Trước đây là chính xác. Yeah.
[Không nghe được sinh viên phản ứng]
Chính xác, nếu mục tiêu của chương trình này, như getInt chức năng chính nó,
là để có được một int từ người sử dụng, tôi có thể vượt qua chức năng
tất cả các biến tôi muốn, nhưng nếu tôi không vượt qua chúng bằng cách tham khảo
hoặc theo địa chỉ hay bằng con trỏ, tất cả đồng nghĩa cho các mục đích của ngày hôm nay,
sau đó chức năng mà không có khả năng thay đổi các nội dung của biến đó.
Điều này sẽ vượt qua trong một bản sao giống như các phiên bản lỗi của trao đổi
mà chúng tôi đã nói về một vài lần.
>> Nhưng thay vào đó, bằng cách làm & x, tôi theo nghĩa đen đi qua trong những gì?
[Sinh viên] địa chỉ. >> Địa chỉ của x.
Nó giống như vẽ một bản đồ cho các chức năng được gọi là scanf và nói ở đây,
đây là những hướng dẫn để một đoạn bộ nhớ trong máy tính
mà bạn có thể lưu trữ một số nguyên vào.
Để cho sscanf để làm điều đó
những nhà điều hành, phần của cú pháp là nó sẽ phải sử dụng
dù chúng ta không thể nhìn thấy nó bởi vì người khác đã viết chức năng này?
Nói cách khác - đó là những gì?
[Sinh viên] X đọc.
Có sẽ là một số đọc, nhưng chỉ đối với x ở đây.
Nếu scanf đang được thông qua địa chỉ của x,
cú pháp, những gì nhà điều hành là ràng buộc để tồn tại một nơi nào đó
bên trong thực hiện scanf để scanf
thực sự có thể viết một số 2 đến địa chỉ đó?
Yeah, do đó, các tập tin *.
Nhớ lại rằng * nhà điều hành của chúng tôi tới đích, mà về cơ bản có nghĩa là đi đến đó.
>> Một khi bạn đã được trao một địa chỉ, như là trường hợp ở đây,
scanf có thể nếu chúng ta thực sự nhìn xung quanh nguồn mã
đang làm * x hoặc tương đương để thực sự đi đến địa chỉ đó và đặt một số giá trị ở đó.
Bây giờ, như đối với scanf được đầu vào từ bàn phím,
chúng tôi sẽ vẫy tay của chúng tôi ngày hôm nay.
Chỉ cần giả định rằng hệ thống điều hành cho phép sscanf để nói chuyện
bàn phím của người sử dụng, nhưng vào thời điểm này trong dòng 19,
khi chúng tôi chỉ đơn giản là in ra x, nó có vẻ là trường hợp
scanf đã đặt một int trong x.
Đó là chính xác scanf hoạt động như thế nào, và nhớ lại tuần trước
đó chính là GetString và getInt và gia đình của các chức năng khác của nó
cuối cùng hoạt động, mặc dù với phương sai nhẹ như sscanf,
có nghĩa là quét một chuỗi thay vì bàn phím.
Nhưng chúng ta hãy xem xét một phương sai nhỏ này.
Năm scanf2, tôi thực sự hơi say lên.
Điều gì là sai và tôi sẽ ẩn các bình luận giải thích càng nhiều
những gì là sai với chương trình này, phiên bản 2?
Hãy là kỹ thuật có thể thời gian này.
Nó trông khá tốt.
Nó độc đáo thụt vào, nhưng
okay, làm thế nào về chúng ta hãy tỉa nó xuống cho các câu hỏi ngắn hơn?
Line 16. Dòng 16 làm bằng tiếng Anh chính xác nhưng kỹ thuật là gì?
Một chút vụng về. , Michael.
[Sinh viên] Nó chỉ vào chữ cái đầu tiên của một chuỗi.
>> Được rồi, gần gũi. Hãy để tôi tinh chỉnh đó một chút.
Chỉ vào chữ cái đầu tiên của một chuỗi, bạn đang khai báo một biến gọi là bộ đệm
sẽ trỏ đến địa chỉ đầu tiên của một chuỗi,
hay đúng hơn, mà sẽ chỉ cụ thể hơn đến một char.
Nhận thấy nó không thực sự chỉ bất cứ nơi nào bởi vì không có nhà điều hành phân công.
Không có dấu bằng, do đó, tất cả những gì chúng ta đang làm là phân bổ các bộ đệm được gọi là biến.
Nó sẽ xảy ra là 32 bit bởi vì nó là một con trỏ,
và các nội dung của bộ đệm có lẽ là cuối cùng
sẽ chứa một địa chỉ của một char, nhưng bây giờ, bộ đệm có chứa gì?
Chỉ cần một số những người hiểu biết, không có thật một số giá trị rác,
vì chúng ta đã không rõ ràng khởi tạo nó, vì vậy chúng ta không nên giả định bất cứ điều gì.
Được rồi, vì vậy bây giờ dòng 17-những gì dòng 17 này làm gì?
Có lẽ đó sẽ ấm lên này.
Nó in một chuỗi, phải không?
Nó in chuỗi xin vui lòng.
>> Dòng 18 là loại quen thuộc mà chúng ta chỉ thấy một phương sai của
nhưng với một mã định dạng khác nhau, do đó, ở dòng 18,
chúng ta đang nói với scanf ở đây là địa chỉ của một đoạn bộ nhớ.
Tôi muốn bạn để gọi trong một chuỗi, như ngụ ý của% s,
nhưng vấn đề là chúng tôi đã không được thực hiện một vài điều ở đây.
Một trong những vấn đề là gì?
[Sinh viên] Đó là cố gắng dereference một con trỏ null.
Tốt, con trỏ null hoặc nếu không thì chưa biết.
Bạn đang giao scanf một địa chỉ, nhưng bạn chỉ cần nói một chút thời gian trước đây
địa chỉ đó là một số giá trị rác bởi vì chúng tôi đã không thực sự gán nó cho bất cứ điều gì,
và do đó bạn đang nói với scanf hiệu quả đặt một chuỗi ở đây,
nhưng chúng tôi không biết nơi nào là,
vì vậy chúng tôi đã không thực sự cấp phát bộ nhớ cho bộ đệm.
Hơn nữa, bạn là gì cũng không phải nói cho các scanf?
Giả sử đây là một đoạn bộ nhớ, và đó không phải là một giá trị rác,
nhưng bạn vẫn không nói cho scanf một cái gì đó quan trọng.
[Sinh viên Trường hợp thực sự là, các ký hiệu.
Ký hiệu, do đó, trong trường hợp này, đó là okay.
Bởi vì bộ đệm đã được khai báo như một con trỏ
với các mảnh * cú pháp, chúng ta không cần phải sử dụng ký hiệu "
bởi vì nó đã được một địa chỉ, nhưng tôi nghĩ rằng tôi nghe thấy nó ở đây.
[Sinh viên] Làm thế nào lớn là nó?
Tốt, chúng ta không nói cho scanf lớn như thế nào bộ đệm này,
có nghĩa là ngay cả khi bộ đệm là một con trỏ,
chúng tôi đang nói scanf, đặt một chuỗi ở đây,
nhưng ở đây có thể là 2 byte, nó có thể là 10 byte, nó có thể là một megabyte.
Scanf không có ý tưởng, và bởi vì đây là một đoạn bộ nhớ
có lẽ, nó không phải là một chuỗi nào.
Nó chỉ là một chuỗi khi bạn viết các ký tự và 0 \ rằng đoạn bộ nhớ.
Bây giờ nó chỉ là một số đoạn bộ nhớ.
Scanf sẽ không biết khi nào dừng lại bằng văn bản đến địa chỉ đó.
>> Nếu bạn nhớ lại một số ví dụ trong quá khứ mà tôi ngẫu nhiên gõ trên bàn phím
cố gắng tràn bộ đệm, và chúng tôi nói chuyện hôm thứ Sáu về chính xác điều đó.
Nếu một kẻ thù nào đó tiêm vào chương trình của bạn một từ lớn hơn nhiều
hoặc câu hoặc cụm từ sau đó bạn đã hy vọng bạn có thể bị tàn phá
một đoạn bộ nhớ, có thể có hậu quả xấu,
giống như chiếm toàn bộ chương trình của chính nó.
Chúng ta cần để sửa lỗi này bằng cách nào đó.
Hãy để tôi thu nhỏ và đi vào phiên bản 3 của chương trình này.
Đó là một chút tốt hơn.
Trong phiên bản này, nhận thấy sự khác biệt.
Trong dòng 16, tôi đang một lần nữa tuyên bố một bộ đệm được gọi là biến,
nhưng nó là gì bây giờ?
Nó là một mảng của 16 ký tự.
Điều này là tốt bởi vì điều này có nghĩa là bây giờ tôi có thể nói với scanf
đây là một đoạn thực tế của bộ nhớ.
Bạn gần như có thể suy nghĩ của mảng là con trỏ tại,
mặc dù chúng không thực sự tương đương.
Họ sẽ hành xử khác nhau trong các ngữ cảnh khác nhau.
Nhưng nó chắc chắn là trường hợp mà bộ đệm là tham khảo
16 ký tự tiếp giáp bởi vì đó là một mảng
và đã được cho một vài tuần.
>> Ở đây, tôi đang nói với scanf đây là một đoạn bộ nhớ.
Thời gian này, nó thực sự là một đoạn bộ nhớ,
nhưng tại sao chương trình này vẫn khai thác?
Có gì sai vẫn còn?
Tôi đã nói cho tôi 16 byte nhưng-
[Sinh viên] nếu họ gõ trong hơn 16?
Chính xác, điều gì sẽ xảy ra nếu người sử dụng các loại trong 17 ký tự hoặc ký tự 1700?
Trong thực tế, chúng ta hãy xem nếu chúng ta có thể không đi qua sai lầm này.
Nó là tốt hơn nhưng không hoàn hảo.
Hãy để tôi đi trước và chạy làm cho scanf3 để biên dịch chương trình này.
Hãy để tôi chạy scanf3, String xin vui lòng: hello, và chúng tôi dường như sẽ ổn.
Hãy để tôi thử một hơi dài, chào anh.
Được rồi, chúng ta hãy làm hello there làm thế nào bạn có ngày hôm nay, Enter.
Bắt loại may mắn ở đây, chúng ta hãy nói rằng hello there thế nào là bạn.
Chết tiệt.
Được rồi, vì vậy chúng tôi đã may mắn. Hãy xem nếu chúng ta không có thể sửa lỗi này.
Không, nó sẽ không để cho tôi sao chép.
Hãy thử điều này một lần nữa.
Được rồi, stand by.
Chúng ta sẽ thấy bao lâu tôi có thể giả vờ tập trung trong khi vẫn làm điều này.
Chết tiệt. Đó là khá thích hợp, thực sự.
Hiện chúng tôi đi.
Điểm thực hiện.
>> Này, xấu hổ mặc dù nó cũng là, nó cũng là một trong những nguồn của sự nhầm lẫn rất lớn
khi viết các chương trình có lỗi bởi vì họ tự biểu hiện
chỉ một lần trong một thời gian đôi khi.
Thực tế là ngay cả khi mã của bạn là hoàn toàn bị phá vỡ,
nó chỉ có thể được hoàn toàn bị phá vỡ một lần trong một thời gian
bởi vì đôi khi, về cơ bản những gì xảy ra là hệ thống điều hành giao
thêm một ít bộ nhớ hơn bạn thực sự cần thiết vì lý do gì,
và do đó không ai khác là sử dụng bộ nhớ ngay sau khi đoạn 16 ký tự,
vì vậy nếu bạn đi đến 17, 18, 19, bất cứ điều gì, nó không phải là một thỏa thuận lớn như vậy.
Bây giờ, máy tính, ngay cả khi nó không sụp đổ tại thời điểm đó,
cuối cùng có thể sử dụng 17 hoặc 18 hoặc 19 số byte cho cái gì khác,
điểm mà tại đó dữ liệu của bạn mà bạn đặt ở đó, mặc dù quá dài,
sẽ có khả năng bị ghi đè bởi một số chức năng khác.
Nó không nhất thiết sẽ vẫn còn nguyên vẹn,
nhưng nó sẽ không nhất thiết phải gây ra một lỗi seg.
Tuy nhiên, trong trường hợp này, cuối cùng tôi cung cấp đủ ký tự
Tôi chủ yếu vượt quá phân đoạn bộ nhớ, và bam,
hệ điều hành nói: "Xin lỗi, đó là không có lỗi phân khúc tốt."
>> Và chúng ta thấy bây giờ những gì còn lại trong thư mục-
nhận thấy rằng tôi có tập tin này ở đây, cốt lõi.
Chú ý rằng điều này một lần nữa được gọi là một bãi chứa lõi.
Đó là bản chất là một tập tin có chứa các nội dung của bộ nhớ chương trình của bạn
tại điểm mà tại đó nó đã bị rơi,
và chỉ cần thử một ví dụ nhỏ ở đây cho tôi đi ở đây
và chạy gdb ngày scanf3 và sau đó xác định một đối số thứ ba được gọi là cốt lõi,
và chú ý ở đây là nếu tôi liệt kê các mã,
chúng ta sẽ có thể như bình thường với gdb để bắt đầu đi bộ thông qua chương trình này,
và tôi có thể chạy nó và ngay sau khi tôi nhấn như với các lệnh bước trong gdb
ngay sau khi tôi nhấn hàng có khả năng lỗi sau khi gõ vào một chuỗi rất lớn,
Tôi sẽ có thể thực sự xác định nó ở đây.
Thêm về điều này, tuy nhiên, trong phần về bãi lõi
và như thế để bạn thực sự có thể poke xung quanh bên trong của các bãi chứa lõi
và nhìn thấy trên những dòng chương trình không thành công bạn.
Bất kỳ câu hỏi sau đó trên con trỏ và trên các địa chỉ?
Bởi vì ngày hôm nay trên, chúng ta sẽ bắt đầu dùng cho rằng những điều này tồn tại
và chúng ta biết chính xác những gì họ đang.
Vâng.
>> [Sinh viên] Làm thế nào đến bạn không có để đặt một dấu "và" bên cạnh phần
Tốt câu hỏi.
Làm thế nào đến tôi đã không cần phải đặt một dấu "và" bên cạnh các mảng ký tự như tôi đã làm trước đây
với hầu hết các ví dụ của chúng tôi?
Câu trả lời ngắn gọn là mảng là một chút đặc biệt.
Bạn gần như có thể nghĩ rằng một bộ đệm là thực sự là một địa chỉ,
và nó chỉ như vậy sẽ xảy ra là trường hợp các ký hiệu khung hình vuông
là một sự thuận tiện để chúng ta có thể đi vào 0 khung, khung 1,
2 khung, mà không cần phải sử dụng các ký hiệu *.
Đó là một chút của một lời nói dối bởi vì mảng và con trỏ
, trên thực tế, một chút khác nhau, nhưng họ có thể thường xuyên nhưng không luôn luôn được sử dụng thay thế cho nhau.
Trong ngắn hạn, khi một chức năng được mong đợi một con trỏ đến một đoạn bộ nhớ,
bạn có thể vượt qua nó một địa chỉ đã được trả lại bởi malloc,
và chúng tôi sẽ xem malloc một lần nữa trước khi dài, hoặc bạn có thể vượt qua nó tên của một mảng.
Bạn không phải để làm ký hiệu với mảng bởi vì họ đã
cơ bản như địa chỉ.
Đó là một ngoại lệ.
Các dấu ngoặc vuông làm cho họ đặc biệt.
>> Bạn có thể đặt một dấu "và" bên cạnh các bộ đệm?
Không phải trong trường hợp này.
Điều đó sẽ không làm việc vì, một lần nữa, trong trường hợp này góc
nơi mà mảng là không hoàn toàn thực tế địa chỉ.
Nhưng chúng ta có lẽ sẽ trở lại mà chẳng bao lâu với các ví dụ khác.
Hãy cố gắng giải quyết một vấn đề ở đây.
Chúng tôi có một cấu trúc dữ liệu mà chúng tôi đã được sử dụng cho một thời gian được biết đến như là một mảng.
Trường hợp tại điểm, đó là những gì chúng tôi chỉ có.
Tuy nhiên, các mảng có một số mặt tích cực và nhược điểm.
Mảng là lý do tại sao tốt đẹp?
Một điều mà bạn thích đến mức bạn thích mảng về mảng là gì?
Có gì thuận lợi về họ? Có gì hấp dẫn?
Tại sao chúng tôi giới thiệu chúng ở nơi đầu tiên?
Yeah.
[Sinh viên] Họ có thể lưu trữ rất nhiều dữ liệu, và bạn không cần phải sử dụng một điều toàn bộ.
Bạn có thể sử dụng một phần.
Tốt, với một mảng, bạn có thể lưu trữ rất nhiều dữ liệu,
và bạn không nhất thiết phải sử dụng tất cả của nó, vì vậy bạn có thể overallocate,
mà có thể là thuận tiện nếu bạn không biết trước bao nhiêu một cái gì đó để mong đợi.
>> GetString là một ví dụ hoàn hảo.
GetString, bằng văn bản của chúng tôi, không có ý tưởng bao nhiêu ký tự mong,
do đó, thực tế là chúng ta có thể phân bổ khối bộ nhớ tiếp giáp là tốt.
Mảng còn giải quyết một vấn đề chúng ta đã thấy một vài tuần trước đây bây giờ
nơi mã của bạn bắt đầu phân cấp thành một cái gì đó rất được thiết kế kém.
Nhớ lại mà tôi tạo ra một cấu trúc sinh viên gọi là David,
và sau đó là thực sự là một thay thế, mặc dù,
để có một tên gọi là biến và biến khác được gọi là, tôi nghĩ rằng, nhà ở,
và một biến khác được gọi là ID bởi vì trong câu chuyện mà tôi muốn giới thiệu một cái gì đó khác
như Rob vào chương trình, do đó, sau đó tôi quyết định chờ một phút,
Tôi cần phải đổi tên các biến này.
Hãy gọi tôi name1, ID1, house1.
Hãy gọi của Rob name2, house2, ID2.
Nhưng sau đó chờ một phút, những gì về Tommy?
Sau đó, chúng tôi đã có thêm ba biến.
Chúng tôi giới thiệu một người khác, bốn bộ của các biến.
Thế giới bắt đầu nhận được lộn xộn rất nhanh chóng,
vì vậy chúng tôi giới thiệu cấu trúc, và những gì hấp dẫn về một cấu trúc?
Một cấu trúc C không cho bạn làm gì?
Nó thực sự khó xử hôm nay.
Gì >> [không nghe được sinh viên phản ứng]
Yeah, cụ thể, typedef cho phép bạn tạo ra một kiểu dữ liệu mới,
và cấu trúc, từ khoá struct, cho phép bạn đóng gói
khái niệm liên quan mẩu dữ liệu với nhau
và sau đó gọi cho họ một cái gì đó giống như một học sinh.
>> Đó là bởi vì bây giờ chúng ta có thể mô hình
nhiều loại khái niệm nhất quán các khái niệm của một học sinh trong một biến
chứ không phải là tùy tiện có một cho một chuỗi, một cho một ID, và vv.
Mảng là tốt đẹp bởi vì chúng cho phép chúng tôi bắt đầu làm sạch mã của chúng tôi.
Tuy nhiên, một nhược điểm là những gì của một mảng?
Bạn có thể làm gì? Yeah.
[Sinh viên] Bạn phải biết nó là lớn như thế nào.
Bạn phải biết nó là lớn như thế nào, do đó, nó là loại đau đớn.
Những người bạn có kinh nghiệm lập trình trước khi biết rằng trong rất nhiều ngôn ngữ,
như Java, bạn có thể yêu cầu một đoạn bộ nhớ, đặc biệt là một mảng,
lớn như thế nào, với chiều dài, tài sản, do đó, để nói chuyện, và đó là thực sự thuận tiện.
Trong C, bạn có thể không thậm chí gọi strlen trên một mảng chung
bởi vì strlen, như từ nó, chỉ là cho các chuỗi,
và bạn có thể tìm ra chiều dài của một chuỗi vì quy ước của con người
có 0 \, nhưng một mảng, tổng quát hơn, chỉ là một đoạn bộ nhớ.
Nếu nó là một mảng ints, sẽ không có một số ký tự đặc biệt
ở cuối đang chờ bạn.
Bạn phải nhớ chiều dài của một mảng.
Một nhược điểm của một mảng nuôi đầu của nó trong getString chính nó.
Nhược điểm khác của một mảng là gì?
Sir, chỉ có bạn và tôi hôm nay.
[Phản ứng sinh viên không nghe được] >> Đó là những gì?
Đó là tuyên bố trên stack.
Được rồi, tuyên bố trên stack. Tại sao bạn không như thế?
[Sinh viên] Bởi vì nó được tái sử dụng.
Nó được tái sử dụng.
Được rồi, nếu bạn sử dụng một mảng để cấp phát bộ nhớ,
bạn không thể, ví dụ, trả lại nó vì nó trên stack.
Được rồi, đó là một bất lợi.
Và làm thế nào về một với một mảng?
Một khi bạn phân bổ nó, bạn đang loại hơi say nếu bạn cần nhiều không gian hơn
hơn mảng đó.
>> Sau đó, chúng tôi giới thiệu, thu hồi, malloc, trong đó đã cho chúng ta khả năng để tự động cấp phát bộ nhớ.
Nhưng điều gì sẽ xảy ra nếu chúng ta đã cố gắng một thế giới khác hoàn toàn?
Điều gì sẽ xảy ra nếu chúng tôi muốn giải quyết một trong những vấn đề
do đó, chúng tôi thay vì bút của tôi đã ngủ ở đây
điều gì sẽ xảy ra nếu chúng ta thay vì muốn để cơ bản tạo ra một thế giới không còn như thế này?
Đây là một mảng, và, tất nhiên, loại hủy một khi chúng ta kết thúc của mảng,
và bây giờ tôi không còn có không gian cho một số nguyên hoặc một nhân vật khác.
Điều gì sẽ xảy ra nếu chúng ta loại preemptively nói tại sao chúng ta không thư giãn
yêu cầu này rằng tất cả những phần bộ nhớ được tiếp giáp trở lại trở lại,
và tại sao không, khi tôi cần một int hoặc một char,
chỉ cho tôi không gian cho một trong số họ?
Và khi tôi cần một, cung cấp cho tôi một không gian khác,
và khi tôi cần một, cung cấp cho tôi một không gian khác.
Lợi thế trong đó là nếu người khác
có bộ nhớ ở đây, không có việc lớn.
Tôi sẽ đưa đoạn bổ sung bộ nhớ ở đây và sau đó một trong những điều này.
>> Bây giờ, nắm bắt duy nhất ở đây là điều này gần như cảm thấy như tôi có
một bó toàn bộ các biến khác nhau.
Điều này cảm thấy giống như năm biến khác nhau có khả năng.
Nhưng nếu chúng ta ăn cắp ý tưởng từ chuỗi
nhờ đó chúng ta bằng cách nào đó liên kết những điều này với nhau khái niệm, và những gì nếu tôi đã làm điều này?
Đây là mũi tên của tôi rất kém rút ra.
Nhưng giả sử rằng mỗi người trong số các phần bộ nhớ
chỉ khác, và anh chàng này, không có anh, chị, em ruột phải của mình,
không có mũi tên như vậy.
Điều này là trong thực tế, những gì được gọi là một danh sách liên kết.
Đây là một cấu trúc dữ liệu mới cho phép chúng ta cấp phát một đoạn bộ nhớ,
khác, sau đó một, sau đó một, bất cứ lúc nào chúng ta muốn
trong một chương trình, và chúng ta nhớ rằng tất cả chúng bằng cách nào đó có liên quan
bằng cách xâu chuỗi chúng lại với nhau, và chúng tôi đã làm điều đó những bức tranh ở đây với một mũi tên.
Nhưng trong mã, những gì sẽ là cơ chế thông qua đó bạn bằng cách nào đó có thể kết nối,
gần giống như Scratch, một thành phần đoạn khác?
Chúng ta có thể sử dụng một con trỏ, phải không?
Bởi vì thực sự là mũi tên đi từ quảng trường phía trên bên trái,
anh chàng này ở đây một trong những điều này, có thể chứa bên trong của hình vuông này
không chỉ là một số ints, không chỉ một số char, nhưng những gì nếu tôi thực sự phân bổ
thêm một chút không gian để bây giờ,
mỗi khối bộ nhớ của tôi, mặc dù điều này sẽ chi phí cho tôi,
bây giờ trông nhiều hơn một chút hình chữ nhật có một trong những phần bộ nhớ
được sử dụng cho một số, như số 1,
và sau đó nếu anh chàng này lưu trữ số 2,
đoạn khác của bộ nhớ này được sử dụng cho một mũi tên,
hay cụ thể hơn, một con trỏ.
Và giả sử tôi lưu trữ các số 3 ở đây trong khi tôi sử dụng điều này để chỉ vào anh chàng đó,
và bây giờ anh chàng này, chúng ta hãy giả sử tôi chỉ muốn ba khối của bộ nhớ.
Tôi sẽ vẽ một đường thông qua đó, cho thấy vô giá trị.
Không có ký tự bổ sung.
>> Thật vậy, đây là làm thế nào chúng ta có thể đi về việc thực hiện
một cái gì đó được gọi là một danh sách liên kết.
Một danh sách liên kết là một cấu trúc dữ liệu mới, và đó là một bước hướng tới
fancier nhiều dữ liệu cấu trúc bắt đầu giải quyết vấn đề
dọc theo dòng của các vấn đề về Facebook và Google vấn đề loại
nơi bạn có dữ liệu khổng lồ, và nó không còn cắt nó
để lưu trữ tất cả mọi thứ liên tục kế nhau và sử dụng một cái gì đó giống như tìm kiếm tuyến tính
hoặc thậm chí một cái gì đó như tìm kiếm nhị phân.
Bạn muốn tốt hơn lần chạy.
Trong thực tế, một trong những Grails Thánh chúng ta sẽ nói về vào cuối tuần này hoặc bên cạnh
là một thuật toán có thời gian chạy là không đổi.
Nói cách khác, nó luôn luôn có cùng một lượng thời gian không có vấn đề
đầu vào là lớn như thế nào, và đó thực sự sẽ là rất thuyết phục,
thậm chí nhiều hơn so với một cái gì đó logarit.
Đây là những gì trên màn hình ở đây?
Mỗi hình chữ nhật là chính xác những gì tôi vừa vẽ bằng tay.
Nhưng điều tất cả các cách trên bên trái là một biến đặc biệt.
Nó sẽ là một con trỏ duy nhất bởi vì các Gotcha
với một danh sách liên kết, những điều này được gọi là,
là bạn phải để treo vào một đầu của danh sách liên kết.
>> Cũng giống như với một chuỗi, bạn cần phải biết địa chỉ của char đầu tiên.
Tương tự đối phó cho danh sách liên kết.
Bạn có biết địa chỉ của đoạn đầu tiên của bộ nhớ
bởi vì từ đó, bạn có thể đạt mỗi khác.
Nhược điểm.
Giá cả những gì chúng tôi trả tiền cho tính linh hoạt của việc có một động
cấu trúc dữ liệu khá lớn mà nếu chúng tôi cần nhiều bộ nhớ hơn, tiền phạt,
chỉ cần phân bổ thêm một thành phần và vẽ một con trỏ từ
cũ đuôi mới của danh sách?
Yeah.
[Sinh viên] Nó có không gian gấp hai lần.
Nó có không gian gấp đôi, vì vậy đó là một nhược điểm, và chúng tôi đã nhìn thấy điều này
sự cân bằng trước khi giữa thời gian và không gian linh hoạt và
bây giờ, chúng ta cần không phải là 32 bit cho mỗi của những con số.
Chúng tôi thực sự cần 64, 32 cho số lượng và 32 cho con trỏ.
Nhưng hey, tôi có 2 GB RAM.
Thêm 32 bit khác ở đây và ở đây không có vẻ là lớn của một thỏa thuận.
Nhưng đối với các tập dữ liệu lớn, nó chắc chắn thêm lên nghĩa là gấp đôi.
Một nhược điểm khác là bây giờ, hoặc những tính năng nào chúng ta từ bỏ,
nếu chúng tôi đại diện cho danh sách những thứ với một danh sách liên kết và không phải là một mảng?
[Sinh viên] Bạn không thể đi ngược trở lại.
Bạn không thể đi qua nó ngược trở lại, do đó, bạn đang loại hơi say nếu bạn đang đi bộ
từ trái sang phải bằng cách sử dụng một vòng lặp hoặc một vòng lặp trong khi
và sau đó bạn nhận ra rằng, "Ồ, tôi muốn quay trở lại đầu của danh sách."
Bạn có thể không phải vì các con trỏ chỉ đi từ trái sang phải như các mũi tên chỉ ra.
>> Bây giờ, bạn có thể nhớ các đầu danh sách với biến khác,
nhưng đó là một phức tạp để giữ trong tâm trí.
Một mảng, không có vấn đề như thế nào đến nay bạn đi, bạn luôn có thể làm trừ, trừ, trừ, trừ đi
và quay trở lại từ đâu bạn đến.
Nhược điểm khác ở đây là gì? Yeah.
[Câu hỏi sinh viên không nghe được]
Bạn có thể, do đó, bạn đã thực sự chỉ đề xuất một cấu trúc dữ liệu gọi là một danh sách liên kết kép,
và quả thật, bạn sẽ thêm một con trỏ cho mỗi của các hình chữ nhật
mà đi theo một hướng khác, xu hướng tăng giá trong đó
bây giờ là bạn có thể đi qua lại,
Nhược điểm trong số đó là bây giờ bạn đang sử dụng ba lần như là bộ nhớ nhiều như chúng tôi được sử dụng để
và cũng có thể thêm phức tạp trong điều khoản của mã này bạn phải viết để có được nó đúng.
Nhưng đây là tất cả có lẽ sự cân bằng rất hợp lý, nếu đảo ngược là quan trọng hơn.
Yeah.
[Sinh viên] Bạn cũng không thể có một danh sách liên kết 2D.
Tốt, bạn có thể không thực sự có một danh sách liên kết 2D.
Bạn có thể. Nó không đơn giản như một mảng.
Giống như một mảng, bạn làm khung mở, đóng khung, khung mở, đóng khung,
và bạn nhận được một số cấu trúc 2-chiều.
Bạn có thể thực hiện một danh sách 2-chiều liên kết
nếu bạn làm tiện ích như bạn đề xuất một con trỏ thứ ba cho mỗi của những việc này,
và nếu bạn nghĩ về danh sách khác đến lúc bạn phong cách 3D
từ màn hình cho tất cả chúng ta, mà chỉ là một chuỗi của một số loại.
Chúng tôi có thể làm điều đó, nhưng nó không phải đơn giản như gõ khung mở, khung vuông. Yeah.
[Câu hỏi sinh viên không nghe được]
Tốt, vì vậy đây là một kicker thực.
>> Các thuật toán này mà chúng tôi đã pined, giống như oh, tìm kiếm nhị phân,
bạn có thể tìm kiếm một mảng các số trên bảng
hoặc một cuốn sách điện thoại nhiều hơn nữa một cách nhanh chóng nếu bạn sử dụng phân chia và chinh phục
và một thuật toán tìm kiếm nhị phân, nhưng tìm kiếm nhị phân yêu cầu hai giả định.
Một, rằng các dữ liệu được sắp xếp.
Bây giờ, chúng ta có lẽ có thể sắp xếp này,
như vậy có lẽ không phải là một mối quan tâm, nhưng tìm kiếm nhị phân cũng giả định
mà bạn đã truy cập ngẫu nhiên danh sách các số,
và một mảng cho phép bạn có quyền truy cập ngẫu nhiên, và bằng cách truy cập ngẫu nhiên,
Tôi có nghĩa là nếu bạn đang đưa ra một mảng, bao nhiêu thời gian hiện nó đi bạn
để có được với khung 0?
Một hoạt động, bạn chỉ cần sử dụng [0] và bạn đang ở.
Có bao nhiêu bước đi để có được vị trí 10?
Một bước này, bạn chỉ cần đi đến [10] và bạn đang có.
Ngược lại, làm thế nào để bạn có được số nguyên thứ 10 trong danh sách liên kết?
Bạn phải bắt đầu ngay từ đầu bởi vì bạn đang chỉ nhớ
sự khởi đầu của một danh sách liên kết, giống như một chuỗi được ghi nhớ
địa chỉ của char đầu tiên của mình, và để tìm mà int thứ 10
hoặc rằng nhân vật thứ 10 trong một chuỗi, bạn phải tìm kiếm toàn bộ điều chết tiệt.
>> Một lần nữa, chúng tôi không giải quyết tất cả các vấn đề của chúng ta.
Chúng tôi đang giới thiệu những cái mới, nhưng nó thực sự phụ thuộc vào những gì bạn đang cố gắng để thiết kế cho.
Trong điều kiện thực hiện điều này, chúng ta có thể mượn một ý tưởng từ cấu trúc của học sinh.
Cú pháp là rất giống nhau, ngoại trừ bây giờ, ý tưởng là một chút trừu tượng hơn
hơn nhà, tên và ID.
Nhưng tôi đề nghị chúng ta có thể có một cấu trúc dữ liệu trong C
đó được gọi là nút, như lời cuối cùng về slide cho thấy,
bên trong của một nút, và một nút là chỉ là một container chung chung trong khoa học máy tính.
Nó thường được vẽ như một vòng tròn hoặc hình vuông hoặc hình chữ nhật như chúng tôi đã làm.
Và trong cấu trúc dữ liệu này, chúng tôi có một int, n,
vì vậy đó là số tôi muốn lưu trữ.
Tuy nhiên, dòng thứ hai, struct node * next là gì?
Tại sao điều này chính xác, hoặc vai trò thực hiện điều này chơi điều,
mặc dù nó là một chút khó hiểu ở cái nhìn đầu tiên?
Yeah.
[Không nghe được sinh viên phản ứng]
Chính xác, do đó, các loại * của chiến lợi phẩm mà nó là một con trỏ của một số loại.
Tên của con trỏ này là tự ý tiếp theo,
nhưng chúng ta có thể gọi nó là bất cứ điều gì chúng ta muốn, nhưng thời điểm này con trỏ làm những gì?
[Sinh Viên] Một nút >> Chính xác, nó chỉ đến một nút khác như vậy.
>> Bây giờ, đây là sắp xếp của một sự tò mò của C.
Nhớ lại rằng C được đọc bởi một trình biên dịch trên xuống dưới, từ trái sang phải,
có nghĩa là nếu đây là một chút khác nhau từ những gì chúng tôi đã làm với học sinh.
Khi chúng ta định nghĩa một sinh viên, chúng tôi thực sự đã không đặt một từ đó.
Nó chỉ nói typedef.
Sau đó, chúng tôi đã có tên id string, int, chuỗi nhà,
và sau đó sinh viên ở dưới cùng của cấu trúc.
Tuyên bố này là một chút khác nhau bởi vì,
một lần nữa, các trình biên dịch C là một chút câm.
Nó chỉ để đọc trên xuống dưới,
vì vậy nếu nó đạt đến dòng thứ 2 ở đây
tiếp theo là khai báo và nó thấy, oh, đây là một biến gọi là tiếp theo.
Đó là một con trỏ đến một nút struct.
Trình biên dịch sẽ nhận ra một nút struct là những gì?
Tôi chưa bao giờ nghe nói về điều này trước khi,
bởi vì từ nút có thể không xuất hiện
cho đến khi phía dưới, do đó, có dư thừa này.
Bạn phải nói nút struct ở đây, mà sau đó bạn có thể rút ngắn sau đó
nhờ typedef xuống đây, nhưng điều này là do
chúng tôi đang tham khảo cấu trúc bên trong của cấu trúc.
Đó là Gotcha ai ở đó.
>> Một số vấn đề thú vị sẽ nảy sinh.
Chúng tôi đã có một danh sách các số. Làm thế nào để chúng ta chèn vào nó?
Làm thế nào để chúng ta tìm kiếm nó? Làm thế nào để chúng tôi xóa từ nó?
Đặc biệt hiện nay là chúng ta phải quản lý tất cả các con trỏ.
Bạn nghĩ rằng con trỏ là loại tâm-uốn
khi bạn đã có một trong số họ chỉ cần cố gắng để đọc một int nó.
Bây giờ chúng ta phải thao tác trị giá toàn bộ danh sách.
Sao chúng ta không có giải lao 5 phút của chúng tôi ở đây, và sau đó chúng tôi sẽ mang lại cho
một số người lên sân khấu để làm chính xác điều đó.
>> C là thú vị hơn nhiều khi nó hành động ra.
Nghĩa là muốn là người đầu tiên?
Được rồi, đến lên. Bạn đang đầu tiên.
Ai muốn là 9? Được rồi, 9.
Làm thế nào khoảng 9? 17?
Bè lũ nhỏ ở đây. 22 và 26 trong đó hàng ghế đầu.
Và sau đó làm thế nào về một người nào đó trên có được chỉ vào.
Bạn đang 34. Được rồi, 34 tuổi, đi lên trên.
Đầu tiên là ở đó. Được rồi, tất cả bốn của các bạn.
Và chúng tôi đã nói trong 9?
9 của chúng tôi là ai?
Ai thực sự muốn là 9? Được rồi, thôi nào, là 9.
Ở đây chúng tôi đi.
34, chúng tôi sẽ gặp các bạn ở đó.
Phần đầu tiên là làm cho mình trông như thế.
26, 22, 17, tốt.
Nếu bạn có thể đứng sang một bên, bởi vì chúng ta sẽ malloc bạn trong một thời điểm.
>> Tốt, tốt.
Được rồi, tuyệt vời, do đó, hãy hỏi một vài câu hỏi ở đây.
Và trên thực tế, tên của bạn là những gì? >> Anita.
Anita, okay, đi qua đây.
Anita sẽ để giúp chúng tôi loại giải quyết một câu hỏi khá đơn giản trong lần đầu tiên,
đó là làm thế nào để bạn tìm thấy hay không một giá trị trong danh sách?
Bây giờ, chú ý đầu tiên, đại diện ở đây bởi Lucas,
là một chút khác nhau, và do đó, tác phẩm của mình giấy là cố tình đi ngang
bởi vì nó không phải là khá cao và không mất nhiều như các bit,
mặc dù về mặt kỹ thuật có cùng kích thước giấy chỉ xoay.
Nhưng anh ấy là một chút khác nhau trong đó ông chỉ có 32 bit cho một con trỏ,
và tất cả những kẻ là 64 bit, một nửa trong số đó là số lượng, một nửa trong số đó là một con trỏ.
Tuy nhiên, con trỏ được không mô tả, do đó, nếu các bạn có thể phần nào lúng túng
sử dụng tay trái của bạn chỉ vào người bên cạnh bạn.
Và bạn là số 34. Tên của bạn là gì?
Ari.
Ari, do đó, thực sự, giữ giấy trong tay phải của bạn, và tay trái đi thẳng xuống.
Bạn đại diện null trên bên trái.
>> Bây giờ hình ảnh con người của chúng tôi là rất nhất quán.
Điều này thực sự là con trỏ làm việc như thế nào.
Và nếu bạn có thể nhai một chút theo cách này vì vậy tôi không theo cách của bạn.
Anita ở đây, tìm thấy tôi số 22,
nhưng giả sử một hạn chế của không phải con người nắm giữ lên mảnh giấy,
nhưng đây là một danh sách, và bạn chỉ có Lucas để bắt đầu với
bởi vì anh ta có nghĩa là con trỏ đầu tiên.
Giả sử bạn mình là một con trỏ, và do đó, bạn cũng có khả năng chỉ vào một cái gì đó.
Tại sao bạn không bắt đầu bằng cách chỉ tay vào chính xác những gì Lucas chỉ vào?
Tốt, và hãy để tôi ban hành này ra ở đây.
Chỉ vì lợi ích của cuộc thảo luận, hãy để tôi kéo lên một trang trắng ở đây.
Làm thế nào để bạn đánh vần tên của bạn >> Anita.
Được rồi, Anita.
Hãy nói rằng node * anita = Lucas.
Vâng, chúng ta không nên gọi bạn là Lucas. Chúng tôi nên gọi bạn đầu tiên.
Tại sao điều này trong thực tế, phù hợp với thực tế ở đây?
Một, lần đầu tiên đã tồn tại.
Đầu tiên đã được phân bổ có lẽ là một nơi nào đó ở đây.
Node * Đầu tiên, và nó được phân bổ một danh sách bằng cách nào đó.
Tôi không biết làm thế nào điều đó xảy ra. Điều đó xảy ra trước khi lớp học bắt đầu.
Này danh sách liên kết của con người đã được tạo.
Và tại thời điểm này trong câu chuyện này là tất cả trên Facebook dường như sau
vào thời điểm này trong câu chuyện, Anita đã được khởi tạo bằng đầu tiên,
mà không có nghĩa là Anita điểm tại Lucas.
Thay vào đó, cô chỉ vào những gì ông chỉ vào
bởi vì cùng một địa chỉ bên trong của Lucas 32 bit - 1, 2, 3 -
bây giờ là bên trong của Anita của 32 bit - 1, 2, 3.
>> Bây giờ tìm thấy 22. Làm thế nào bạn sẽ đi về việc này?
Mà điểm? >> Để bất cứ điều gì là những gì.
Trỏ đến bất cứ điều gì, nên đi trước và hành động nó ra là tốt nhất bạn có thể ở đây.
Tốt, tốt, và bây giờ bạn đang chỉ vào tên của bạn với 22?
Ramon. >> Ramon, do đó, Ramon đang nắm giữ tăng 22.
Bây giờ bạn đã thực hiện một kiểm tra.
Có Ramon == 22, và nếu như vậy, ví dụ, chúng ta có thể trở lại đúng sự thật.
Hãy cho tôi trong khi những kẻ đứng đây phần nào lúng túng-
hãy để tôi làm một cái gì đó một cách nhanh chóng như bool.
Tôi sẽ đi trước và nói (node ​​* danh sách, int n).
Tôi sẽ quay lại ngay với bạn guys. Tôi chỉ cần có để viết một số mã.
Và bây giờ tôi sẽ đi trước và làm điều này, node * anita = danh sách.
Và tôi sẽ đi trước và nói trong khi (anita = NULL).
>> Ẩn dụ ở đây là nhận được một chút kéo dài, nhưng trong khi (anita = NULL!), Tôi làm những gì muốn làm?
Tôi cần một số cách để tham khảo
số nguyên có Anita chỉ vào.
Trong quá khứ, khi chúng tôi có các cấu trúc, một nút là,
chúng tôi sử dụng các ký hiệu dấu chấm, và chúng tôi sẽ nói một cái gì đó như
anita.n, nhưng vấn đề ở đây là Anita không phải là một cấu trúc cho mỗi gia nhập.
Cô ấy là gì?
Cô ấy là một con trỏ, như vậy thực sự, nếu chúng ta muốn sử dụng dấu chấm ký hiệu
và điều này được nhìn cố ý một chút khó hiểu
chúng ta phải làm một cái gì đó giống như đi đến bàn tay trái của bất cứ điều gì Anita chỉ
và sau đó nhận được lĩnh vực được gọi là n.
Anita là một con trỏ, nhưng * anita là những gì?
Những gì bạn thấy khi bạn đi đến những gì Anita được chỉ vào?
Một cấu trúc, một nút, và nút thu hồi, có một lĩnh vực được gọi là n
bởi vì nó đã, thu hồi, 2 lĩnh vực này, tiếp theo và n,
mà chúng ta thấy một chút thời gian trước đây ngay tại đây.
>> Để thực sự bắt chước trong mã,
chúng ta có thể làm điều này và nói rằng nếu ((* anita) n == n), n mà tôi đang tìm kiếm.
Chú ý rằng chức năng này đã được thông qua trong số tôi quan tâm.
Sau đó, tôi có thể đi trước và làm một cái gì đó giống như return true.
Khác, nếu đó không phải là trường hợp, tôi làm những gì muốn làm?
Làm thế nào để dịch mã Anita đã làm như vậy trực giác bằng cách đi bộ qua danh sách?
Tôi nên làm gì đây để mô phỏng Anita rằng bước sang trái, bước sang bên trái?
[Sinh viên phản ứng không nghe được] >> đó là gì?
[Không nghe được sinh viên phản ứng]
Tốt, không phải là một ý tưởng tồi, nhưng trong quá khứ, khi chúng tôi đã làm điều này, chúng tôi đã thực hiện anita + +
vì đó sẽ thêm số 1 Anita,
mà thường sẽ chỉ vào những người kế tiếp, như Ramon,
hoặc người bên cạnh anh ta, hoặc bên cạnh anh người xuống dòng.
Nhưng đó không phải là khá tốt ở đây bởi vì điều này trông giống như những gì trong bộ nhớ?
Không phải là. Chúng tôi đã vô hiệu hóa điều đó.
Nó trông như thế này trong bộ nhớ, và mặc dù tôi đã rút ra 1 và 2 và gần 3 với nhau,
nếu chúng ta thực sự mô phỏng này có thể bạn guys, trong khi vẫn chỉ vào cùng một số người,
có thể một số bạn lấy lại bước ngẫu nhiên, một số bạn một bước ngẫu nhiên về phía trước?
>> Mess này vẫn còn là một danh sách liên kết,
nhưng những kẻ có thể là bất cứ nơi nào trong bộ nhớ,
để anita + + không làm việc tại sao?
Những gì ở vị trí anita + +?
Ai biết được.
Đó là một số giá trị khác mà chỉ như vậy xảy ra được xen
trong số tất cả các nút này một cách tình cờ bởi vì chúng tôi không sử dụng một mảng.
Chúng tôi phân bổ mỗi một nút riêng lẻ.
Được rồi, nếu các bạn có thể làm sạch mình trở lại.
Chúng tôi đề xuất rằng thay vì anita + +, chúng ta thay vì làm anita được
tốt, tại sao chúng ta không đi đến bất cứ điều gì Anita được chỉ vào và sau đó làm tiếp theo?
Nói cách khác, chúng tôi đi đến Ramon, người đang nắm giữ số 22,
và sau đó tiếp theo là như Anita sẽ được sao chép con trỏ bàn tay trái của mình.
Nhưng cô sẽ không đi xa hơn so với Ramon bởi vì chúng tôi phát hiện 22.
Nhưng đó sẽ là ý tưởng. Bây giờ, đây là một mớ hỗn độn thần khủng khiếp.
Thành thật mà nói, không ai sẽ nhớ cú pháp này, và rất may mắn,
nó thực sự là một mưu-oh chút, bạn đã không thực sự nhìn thấy những gì tôi đã viết.
Điều này sẽ hấp dẫn hơn nếu bạn có thể. Thì đấy!
>> Đằng sau hậu trường, tôi đã giải quyết vấn đề theo cách này.
Anita, phải mất rằng bước sang bên trái,
đầu tiên, chúng tôi đi đến địa chỉ mà Anita chỉ
và nơi cô sẽ tìm thấy không chỉ n, mà chúng ta chỉ cần kiểm tra vì lợi ích so sánh,
nhưng bạn cũng sẽ tìm thấy tiếp theo trong trường hợp này,
Tay trái của Ramon trỏ đến nút tiếp theo trong danh sách.
Nhưng đây là sự hỗn loạn thần khủng khiếp mà tôi đã đề cập trước đó,
nhưng nó quay ra C cho phép chúng ta đơn giản hóa này.
Thay vì viết (* anita), chúng ta có thể thay vì chỉ viết anita-> n,
và đó là điều tương tự chính xác chức năng, nhưng nó rất trực quan hơn,
và nó rất phù hợp với hình ảnh mà chúng tôi đã được vẽ
tất cả thời gian này bằng cách sử dụng mũi tên.
>> Cuối cùng, chúng ta cần gì để làm ở phần cuối của chương trình này?
Có một dòng mã còn lại.
Trả lại những gì?
False, bởi vì nếu chúng tôi nhận được thông qua toàn bộ vòng lặp trong khi
và Anita, trên thực tế, null, điều đó có nghĩa là cô ấy đã đi tất cả các cách để cuối danh sách
nơi cô chỉ vào tên của bạn là gì nữa không?
Ari >> Ari tay trái, đó là null.
Anita bây giờ là null, và tôi nhận ra bạn chỉ cần đứng ở đây lúng túng trong tình trạng lấp lửng
bởi vì tôi sẽ ra trên một độc thoại ở đây,
nhưng chúng tôi sẽ liên quan đến bạn một lần nữa trong thời điểm này chỉ là một.
Anita là null tại thời điểm đó trong câu chuyện, do đó, vòng lặp trong khi chấm dứt,
và chúng ta phải quay trở lại sai bởi vì nếu cô ấy có tất cả các cách để con trỏ null của Ari
sau đó không có số mà cô đã tìm kiếm trong danh sách.
Chúng tôi có thể làm sạch này lên quá, nhưng điều này là một thực hiện khá tốt sau đó
một chức năng traversal, một chức năng cho một danh sách liên kết.
Nó vẫn còn tuyến tính tìm kiếm, nhưng nó không phải đơn giản như + + một con trỏ
hoặc + + một biến i bởi vì bây giờ chúng ta không thể đoán
nơi mà mỗi một nút đó trong bộ nhớ.
Nghĩa là chúng ta phải thực hiện theo các dấu vết của breadcrumbs, hoặc cụ thể hơn,
con trỏ, để có được từ một nút khác.
>> Bây giờ chúng ta hãy thử một số khác. Anita, bạn có muốn quay lại đây?
Tại sao chúng ta không đi trước và phân bổ một người khác từ phía khán giả?
Malloc Tên bạn là gì? >> Rebecca.
Rebecca. Rebecca đã được malloced từ khán giả,
và cô ấy là lưu trữ số 55.
Và mục tiêu trong tầm tay tại là Anita để chèn
Rebecca vào danh sách liên kết ở vị trí thích hợp của nó.
Thôi nào ở đây một lúc.
Tôi đã làm một cái gì đó như thế này.
Tôi đã làm * nút. Và tên của bạn là những gì một lần nữa?
Rebecca. >> Rebecca, okay.
Rebecca được malloc (sizeof (node)).
Cũng giống như chúng tôi đã phân bổ những thứ như học sinh và whatnot trong quá khứ,
chúng ta cần kích thước của nút, vì vậy bây giờ Rebecca
chỉ vào những gì?
Rebecca có hai lĩnh vực bên trong của cô, một trong số đó là 55.
Hãy làm những gì, rebecca-> = 55.
Nhưng sau đó rebecca-> tiếp theo nên được như bây giờ, bàn tay của cô là loại người hiểu biết?
Nó chỉ vào một số giá trị rác, vậy tại sao không phải là phương pháp tốt
ít nhất chúng ta làm điều này để tay trái bây giờ là ở bên cô.
Bây giờ Anita, đưa nó từ đây.
Bạn có Rebecca đã được phân bổ.
Đi trước và tìm thấy nơi chúng ta nên đặt Rebecca.
Tốt, rất tốt.
Được rồi, tốt, và bây giờ chúng tôi cần bạn cung cấp một chút hướng,
vì vậy bạn đã đạt đến Ari.
Bàn tay trái của anh là vô giá trị, nhưng Rebecca rõ ràng thuộc về bên phải,
vậy làm thế nào chúng ta phải thay đổi danh sách liên kết này
để chèn Rebecca vào nơi thích hợp?
Nếu bạn thật sự có thể di chuyển bàn tay trái của người dân xung quanh khi cần thiết,
chúng tôi sẽ khắc phục vấn đề theo cách đó.
Được rồi, tốt, và khi đó, tay trái của Rebecca bây giờ là bên cạnh cô.
>> Đó là quá dễ dàng.
Chúng ta hãy thử phân bổ chúng ta gần như đã hoàn tất, 20.
Được rồi, đến lên.
20 đã được giao, do đó hãy để tôi đi trước và nói một lần nữa ở đây
chúng tôi đã chỉ làm Saad * nút.
Chúng tôi có malloc (sizeof (node)).
Chúng tôi sau đó làm cú pháp chính xác giống như chúng tôi đã làm trước khi cho 20,
và tôi sẽ làm gì tiếp theo = NULL, và bây giờ nó lên để Anita
để chèn vào danh sách liên kết, nếu bạn có thể đóng vai trò đó chính xác cùng.
Thực thi.
Được rồi, tốt.
Bây giờ suy nghĩ cẩn thận trước khi bạn bắt đầu di chuyển tay trái xung quanh.
Bạn đến nay có vai trò vụng về nhất.
Bé bàn tay nên chuyển đầu tiên?
Được rồi, chờ đợi, tôi nghe một số không.
Nếu một số người lịch sự muốn giúp đỡ giải quyết một tình huống khó xử ở đây.
Tay trái mà nên được cập nhật đầu tiên có lẽ? Yeah.
[Sinh viên] Saad.
Được rồi, Saad, tại sao, mặc dù?
[Không nghe được sinh viên phản ứng]
Tốt, bởi vì nếu chúng tôi di chuyển tên của bạn là gì? >> Marshall.
Marshall, nếu chúng ta di chuyển bàn tay của mình đầu tiên xuống thành vô giá trị,
bây giờ chúng tôi có nghĩa là mồ côi bốn người trong danh sách này
bởi vì anh là điều duy nhất chỉ vào Ramon và tất cả mọi người bên trái,
để cập nhật con trỏ đầu tiên là xấu.
Hãy lùi lại mà.
Tốt, và bây giờ đi trước và di chuyển tay trái thích hợp chỉ vào Ramon.
Điều này cảm thấy dư thừa ít.
Bây giờ có hai người chỉ vào Ramon, nhưng đó là tiền phạt
bởi vì bây giờ làm thế nào khác để chúng tôi cập nhật danh sách?
Mặt khác để di chuyển?
Tuyệt vời, bây giờ chúng tôi bị mất bất kỳ bộ nhớ?
Không, tốt như vậy, chúng ta hãy xem nếu chúng ta không có thể phá vỡ một lần nữa.
>> Mallocing một lần cuối, số 5.
Tất cả các con đường trong trở lại, trên xuống.
Nó rất thú vị.
[Vỗ tay]
Tên bạn là gì? >> Ron.
Ron, okay, bạn đang malloced là số 5.
Chúng tôi đã chỉ thực hiện mã đó là gần như giống hệt với những
chỉ với một cái tên khác nhau.
Excellent.
Bây giờ, Anita, chúc may mắn chèn số 5 vào danh sách.
Tốt, và
Tuyệt vời, do đó, đây thực sự là con thứ ba trong tổng số ba trường hợp.
Chúng tôi lần đầu tiên có một người nào đó ở cuối, Rebecca.
Sau đó chúng tôi đã có một người nào đó ở giữa.
Bây giờ chúng ta có một người nào đó ngay từ đầu, và trong ví dụ này,
bây giờ chúng ta phải cập nhật Lucas lần đầu tiên
bởi vì phần tử đầu tiên trong danh sách đã chỉ vào một nút mới,
, lần lượt, chỉ số nút 9.
>> Đây là một cuộc biểu tình cực kỳ khó xử, tôi chắc chắn,
do đó, người lớn vòng tràng pháo tay cho những kẻ nếu bạn có thể.
Độc đáo làm.
Đó là tất cả. Bạn có thể giữ mảnh giấy như là một ít bộ nhớ.
Nó chỉ ra rằng làm điều này trong mã
không phải là khá đơn giản như chỉ cần di chuyển tay
và chỉ con trỏ vào những thứ khác nhau.
Nhưng nhận ra rằng khi nói đến thời gian để thực hiện một cái gì đó như
một danh sách liên kết hoặc biến thể của nó nếu bạn tập trung vào thực sự
những nguyên tắc cơ bản cơ bản, những vấn đề bite-size tôi phải tìm ra,
là bàn tay hoặc bàn tay này, nhận ra rằng những gì nếu không là một chương trình khá phức tạp
, trên thực tế, có thể được giảm đến khối xây dựng khá đơn giản như thế này.
>> Hãy lấy những thứ trong một hướng phức tạp hơn vẫn còn.
Bây giờ chúng ta có khái niệm về danh sách liên kết.
Chúng tôi cũng có những gợi ý lại có một danh sách liên kết kép,
trông gần như giống nhau, nhưng bây giờ chúng tôi có hai con trỏ bên trong các cấu trúc
thay vì một, và chúng tôi có thể có thể gọi các con trỏ trước và sau
hoặc sang trái hoặc phải, nhưng chúng tôi, trên thực tế, cần hai người trong số họ.
Mã sẽ được tham gia nhiều hơn một chút.
Anita sẽ phải làm thêm công việc ở đây trên sân khấu.
Nhưng chúng tôi chắc chắn có thể thực hiện điều đó loại cấu trúc.
Về thời gian chạy, mặc dù, những gì sẽ là thời gian chạy
Anita của việc tìm kiếm một số n trong một danh sách liên kết?
Vẫn còn lớn O của n, vì vậy nó không có gì tốt hơn so với tìm kiếm tuyến tính.
Chúng ta không thể làm tìm kiếm nhị phân, mặc dù, một lần nữa.
Tại sao như vậy không? Bạn không thể nhảy xung quanh.
Mặc dù chúng tôi rõ ràng nhìn thấy tất cả những con người trên sân khấu,
và Anita có thể đã nghiệm nó và nói: "Đây là giữa của danh sách,"
cô sẽ không biết rằng nếu cô ấy là những chương trình máy tính
bởi vì điều duy nhất cô phải bám vào lúc bắt đầu của kịch bản
là Lucas, con trỏ đầu tiên.
Cô ấy nhất thiết sẽ phải thực hiện theo các liên kết này,
tính cách của mình cho đến khi cô tìm thấy khoảng giữa,
và thậm chí sau đó, cô ấy sẽ không biết khi nào nó tới giữa
trừ khi cô ấy đi tất cả các cách để kết thúc để tìm ra có bao nhiêu,
sau đó backtracks, và đó cũng sẽ là khó trừ khi bạn có
một danh sách liên kết kép của một số loại.
>> Giải quyết một số vấn đề ngày hôm nay, nhưng giới thiệu những người khác.
Điều gì về một cấu trúc dữ liệu khác nhau hoàn toàn?
Đây là một bức ảnh của các khay trong Mather House,
và trong trường hợp này, chúng tôi có một cấu trúc dữ liệu chúng tôi cũng đã loại được nói về.
Chúng tôi nói về một chồng trong bối cảnh của bộ nhớ,
và đó là loại cố tình đặt tên bởi vì một cây rơm trong các điều khoản của bộ nhớ
là có hiệu quả một cấu trúc dữ liệu có nhiều thứ hơn và nhiều hơn nữa lớp trên đầu trang của nó.
Nhưng điều thú vị về một chồng, như là trường hợp trong thực tế,
rằng đó là một loại đặc biệt của cấu trúc dữ liệu.
Đó là một cấu trúc dữ liệu, theo đó các yếu tố đầu tiên trong
là yếu tố cuối cùng.
Nếu bạn là khay đầu tiên được đưa vào stack,
bạn sẽ là không may khay cuối cùng được đưa ra khỏi ngăn xếp,
và đó là không nhất thiết phải là một điều tốt.
Ngược lại, bạn có thể nghĩ về nó theo cách khác xung quanh,
người cuối cùng trong là sản phẩm đầu tiên.
>> Bây giờ, bất kỳ kịch bản đến với tâm trí, nơi có một chồng
cấu trúc dữ liệu, nơi bạn có tài sản đó
cuối cùng, ra đầu tiên, thực sự là hấp dẫn?
Đó có phải là một điều tốt? Đó có phải là một điều xấu?
Đó chắc chắn là một điều xấu nếu các khay không phải tất cả các giống hệt nhau
và họ đã được tất cả các màu sắc khác nhau đặc biệt hoặc whatnot,
và màu sắc mà bạn muốn là tất cả các con đường ở phía dưới.
Tất nhiên, bạn không thể nhận được rằng nếu không có nỗ lực rất lớn.
Bạn phải bắt đầu từ đầu và làm việc theo cách của bạn xuống.
Tương tự như vậy, điều gì sẽ xảy ra nếu bạn là một trong những chàng trai hâm mộ
người chờ đợi cả đêm cố gắng để có được một chiếc iPhone và dòng lên
tại một nơi như thế này?
Nó sẽ không được tốt đẹp nếu các cửa hàng Apple
là một cấu trúc dữ liệu ngăn xếp?
Yay? Nay?
Nó chỉ tốt cho những người đến ở phút cuối cùng
và sau đó nhận được ngắt hàng đợi.
Và trên thực tế, thực tế là tôi đã nghiêng như vậy để nói rằng hàng đợi
là thực sự phù hợp với những gì chúng tôi gọi đây là loại cấu trúc dữ liệu,
trong thực tế thứ tự không thành vấn đề,
và bạn muốn là người đầu tiên là một trong những người đầu tiên
nếu chỉ vì lợi ích công bằng của con người.
Chúng tôi thường sẽ gọi đó là một cấu trúc dữ liệu hàng đợi.
>> Nó chỉ ra ngoài danh sách liên kết, chúng ta có thể bắt đầu bằng cách sử dụng những ý tưởng cơ bản giống nhau
và bắt đầu tạo ra các loại mới và khác nhau của các giải pháp cho các vấn đề.
Ví dụ, trong trường hợp của một chồng, chúng ta có thể đại diện cho một chồng
bằng cách sử dụng một cấu trúc dữ liệu như thế này, tôi sẽ đề xuất.
Trong trường hợp này, tôi đã tuyên bố một cấu trúc, và tôi đã nói bên trong của cấu trúc này
là một loạt các con số và sau đó biến một kích thước được gọi là,
và tôi sẽ gọi điều này một chồng.
Bây giờ, tại sao điều này thực sự làm việc?
Trong trường hợp của một chồng, tôi có thể vẽ này có hiệu quả trên màn hình như là một mảng.
Dưới đây là chồng của tôi. Đó là những con số của tôi.
Và chúng tôi sẽ vẽ chúng như thế này, này, này, này, này.
Và sau đó tôi có một số thành viên dữ liệu khác ở đây,
được gọi là kích thước, do đó, đây là kích thước, và đây là con số,
và tập thể, cả iPad ở đây đại diện cho một cấu trúc ngăn xếp.
Bây giờ, theo mặc định, kích thước đã có lẽ đã được khởi tạo là 0,
và những gì bên trong các mảng của các con số ban đầu
khi tôi lần đầu tiên cấp phát một mảng?
Rác thải. Ai biết được? Và nó không thực sự quan trọng.
Nó không quan trọng nếu điều này là 1, 2, 3, 4, 5, hoàn toàn ngẫu nhiên
may mắn được lưu trữ trong cơ cấu của tôi bởi vì như tôi biết rằng kích thước của ngăn xếp
là 0, sau đó tôi biết lập trình, không nhìn vào bất kỳ phần tử trong mảng.
Nó không quan trọng những gì đang có.
Đừng nhìn vào họ, như sẽ là ý nghĩa của một kích thước từ 0.
>> Nhưng giả sử bây giờ tôi đi trước và chèn một cái gì đó vào ngăn xếp.
Tôi muốn chèn số 5, vì vậy tôi đặt số 5 ở đây,
và sau đó tôi làm những gì đặt xuống ở đây?
Bây giờ tôi thực sự sẽ đặt xuống 1 với kích thước,
và bây giờ stack là có kích thước 1.
Điều gì sẽ xảy ra nếu tôi đi trước và chèn số, chúng ta hãy nói rằng, 7 tiếp theo?
Điều này sau đó được cập nhật đến 2, và sau đó chúng tôi sẽ làm 9,
và sau đó được cập nhật đến 3.
Tuy nhiên, tính năng thú vị của ngăn xếp này là
Tôi là nghĩa vụ để loại bỏ phần tử nếu tôi muốn để bật
một cái gì đó của ngăn xếp, vậy để nói chuyện?
9 sẽ là điều đầu tiên để đi.
Làm thế nào hình ảnh cũng thay đổi nếu tôi muốn bật một phần tử ra khỏi stack,
giống như một khay trong Mather?
Vâng >> [Sinh viên] Set kích thước 2.
Chính xác, tất cả những gì tôi làm là thiết lập kích thước đến 2, và tôi phải làm gì với mảng?
Tôi không phải làm bất cứ điều gì.
, Chỉ cần tôi có thể là hậu môn, có đặt một 0 hoặc -1 hoặc một cái gì đó để biểu
điều này không phải là một giá trị VN, nhưng nó không quan trọng bởi vì
Tôi có thể ghi bên ngoài của các mảng chính nó bao lâu nó
vì vậy mà tôi biết chỉ nhìn vào hai yếu tố đầu tiên trong mảng này.
Bây giờ, nếu tôi đi và thêm số 8 vào mảng này, làm thế nào để hình ảnh thay đổi tiếp theo?
Điều này sẽ trở thành 8, và điều này trở thành 3.
Tôi cắt một góc ở đây.
Bây giờ chúng tôi có 5, 7, 8, và chúng tôi trở lại kích thước của 3.
Điều này là khá đơn giản để thực hiện,
nhưng khi chúng ta sẽ phải hối tiếc quyết định thiết kế này?
Khi nào mọi thứ bắt đầu đi rất, rất sai trái? Yeah.
[Không nghe được sinh viên phản ứng]
Khi bạn muốn quay trở lại và được những yếu tố đầu tiên bạn đặt in
>> Hóa ra ở đây mặc dù một chồng là một mảng bên dưới mui xe,
các cấu trúc dữ liệu này chúng tôi đã bắt đầu nói về cũng thường được gọi là
trừu tượng cấu trúc dữ liệu nhờ đó mà họ đang thực hiện như thế nào
là hoàn toàn bên cạnh điểm.
Một cấu trúc dữ liệu như một chồng là nghĩa vụ phải hỗ trợ thêm
các hoạt động như đẩy, đẩy một khay vào ngăn xếp,
và pop, mà loại bỏ một phần tử từ ngăn xếp, và đó là nó.
Nếu bạn đã tải về mã của người khác đã thực hiện
điều này được gọi là một chồng, người đó sẽ có văn bản
chỉ có hai chức năng cho bạn, đẩy và pop, mục đích duy nhất trong cuộc sống
sẽ làm chính xác điều đó.
Bạn hoặc anh ta hoặc cô thực hiện chương trình đó
sẽ có được hoàn toàn là một trong những quyết định làm thế nào để thực hiện
ngữ nghĩa của đẩy và popping bên dưới mui xe
hoặc các chức năng của đẩy và popping.
Và tôi đã thực hiện một quyết định hơi thiển cận ở đây
bằng cách thực hiện ngăn xếp của tôi với cấu trúc dữ liệu đơn giản tại sao?
Khi thực hiện điều này phá vỡ cấu trúc dữ liệu?
Tại điểm nào tôi phải trả lại một lỗi khi người dùng gọi đẩy, ví dụ?
[Sinh viên] Nếu không có nhiều không gian hơn.
Chính xác, nếu có không có nhiều không gian hơn, nếu tôi đã vượt quá khả năng,
đó là tất cả các mũ vì nó cho rằng đó là một số loại hằng số toàn cầu.
Vâng, sau đó tôi chỉ cần đi có nói, "Xin lỗi, tôi không thể đẩy giá trị khác
vào stack ", giống như ở Mather.
>> Tại một số điểm, họ đang đi để đạt phần trên đó tủ nhỏ.
Không có nhiều không gian hơn hoặc năng lực trong stack, lúc này có một số loại lỗi.
Họ phải đặt các phần tử ở một nơi khác, khay ở một nơi khác,
hoặc hư không ở tất cả.
Bây giờ, với một hàng đợi, chúng ta có thể thực hiện nó một chút khác nhau.
Hàng đợi là một chút khác nhau trong đó bên dưới mui xe, nó có thể được thực hiện
như là một mảng, nhưng lý do tại sao, trong trường hợp này, tôi đề nghị
cũng có một yếu tố đứng đầu đại diện người đứng đầu danh sách,
mặt trước của danh sách, là người đầu tiên xếp hàng tại các cửa hàng Apple, ngoài kích thước?
Tại sao tôi cần thêm một mảnh dữ liệu ở đây?
Hãy suy nghĩ lại những gì con số là
nếu tôi đã rút ra như sau.
Giả sử điều này bây giờ là một hàng đợi thay vì một chồng,
sự khác biệt là giống như hàng đợi cửa hàng của Apple là công bằng.
Người đầu tiên trong đường dây tại đầu danh sách, số 5 trong trường hợp này,
họ sẽ được cho phép vào cửa hàng đầu tiên.
Hãy làm điều đó.
Giả sử rằng đây là trạng thái của hàng đợi của tôi tại thời điểm này trong thời gian, và bây giờ các cửa hàng Apple
sẽ mở ra và là người đầu tiên, số 5, được dẫn vào cửa hàng.
Làm thế nào để thay đổi hình ảnh bây giờ mà tôi đã de-xếp hàng đợi người đầu tiên
ở phía trước của các dòng?
Đó là những gì >> [Sinh viên] Thay đổi hàng đợi.
Thay đổi người đứng đầu, như vậy 5 biến mất.
Trong thực tế, nó như thế nào tốt nhất để làm điều này?
Trong thực tế, nó như là mặc dù anh chàng này biến mất.
Số 7 sẽ làm gì trong một cửa hàng thực tế?
Họ sẽ có được một bước tiến lớn về phía trước.
>> Nhưng những gì chúng tôi đã phải đánh giá cao khi nói đến mảng
và di chuyển những thứ xung quanh?
Đó là loại một sự lãng phí thời gian của bạn, phải không?
Tại sao bạn có được như vậy hậu môn như có người đầu tiên
ở đầu dòng thể chất lúc bắt đầu của đoạn bộ nhớ?
Đó là hoàn toàn không cần thiết. Tại sao?
Tôi có thể chỉ cần nhớ thay vì >> [không nghe được sinh viên phản ứng]
Chính xác, tôi chỉ có thể nhớ với đầu thành viên bổ sung dữ liệu
mà bây giờ người đứng đầu danh sách là không còn 0, mà nó là một thời điểm trước đây.
Bây giờ nó thực sự là số 1. Bằng cách này, tôi nhận được một tối ưu hóa nhẹ.
Chỉ vì tôi đã huỷ bỏ xếp hàng đợi một người nào đó từ dòng ở đầu dòng tại các cửa hàng Apple
không có nghĩa là tất cả mọi người đã thay đổi, đó là thu hồi một hoạt động tuyến tính.
Tôi thay vào đó có thể dành thời gian liên tục chỉ
và đạt được một phản ứng nhanh hơn nhiều.
Tuy nhiên, giá tôi phải trả là những gì để đạt được hiệu suất bổ sung
và không có thay đổi tất cả mọi người?
Vâng >> [không nghe được sinh viên phản ứng].
Có thể thêm nhiều người hơn, tốt, vấn đề đó là trực giao
thực tế rằng chúng tôi không thay đổi những người xung quanh.
Nó vẫn là một mảng, do đó, có hay không chúng ta thay đổi tất cả mọi người hay không
oh, tôi thấy những gì bạn có nghĩa là, okay.
Thực ra, tôi đồng ý với những gì bạn đang nói ở chỗ nó gần như là mặc dù
chúng tôi bây giờ sẽ không bao giờ sử dụng bắt đầu của mảng này nữa
bởi vì nếu tôi loại bỏ 5, sau đó tôi loại bỏ 7.
Nhưng tôi chỉ đưa con người về bên phải.
>> Nó cảm thấy như tôi là lãng phí không gian, và cuối cùng hàng đợi của tôi tan rã vào không có gì cả,
vì vậy chúng tôi chỉ có thể có người wraparound,
và chúng ta có thể suy nghĩ của mảng này thực sự là một số loại cấu trúc tròn,
nhưng chúng tôi sử dụng những gì nhà điều hành trong C để làm điều đó loại wraparound?
[Không nghe được sinh viên phản ứng] >> Các nhà điều hành modulo.
Nó sẽ là một chút phiền phức để suy nghĩ làm thế nào để bạn làm wraparound,
nhưng chúng ta có thể làm điều đó, và chúng ta có thể bắt đầu đặt con người vào những gì được sử dụng là mặt trước của dòng,
nhưng chúng ta chỉ cần nhớ với biến này đầu người thực tế của người đứng đầu dòng thực sự là.
Điều gì sẽ xảy ra nếu, thay vào đó, mục tiêu của chúng tôi cuối cùng, mặc dù,
là để tìm số, như chúng tôi đã ở đây trên sân khấu với Anita,
nhưng chúng tôi thực sự muốn tốt nhất của tất cả các thế giới?
Chúng tôi muốn tinh tế hơn so với mảng cho phép
bởi vì chúng tôi muốn có khả năng tự động phát triển các cấu trúc dữ liệu.
Nhưng chúng tôi không muốn có một cái gì đó mà chúng tôi đã chỉ ra
trong bài giảng đầu tiên không phải là một thuật toán tối ưu,
đó là tìm kiếm tuyến tính.
Nó chỉ ra rằng bạn có thể, trên thực tế, đạt được
hoặc ít nhất là gần với thời gian liên tục, trong đó một người như Anita,
nếu cô ấy cấu hình cấu trúc dữ liệu của mình không phải là một danh sách liên kết,
không phải là một chồng, không phải là một hàng đợi, có thể, trong thực tế,
đi lên với một cấu trúc dữ liệu, cho phép cô nhìn mọi thứ,
thậm chí từ, chứ không phải chỉ là những con số, những gì chúng tôi sẽ gọi cho thời gian liên tục.
>> Và trên thực tế, nhìn về phía trước, một trong những các psets trong lớp học này là hầu như luôn luôn
một thực hiện một kiểm tra chính tả, theo đó
chúng tôi cung cấp cho bạn một lần nữa một số từ tiếng Anh 150.000 đến mục tiêu là để
load vào bộ nhớ và nhanh chóng có thể trả lời các câu hỏi của mẫu đơn
Từ này được viết chính xác?
Và nó thực sự sẽ suck nếu bạn đã có để lặp qua tất cả 150.000 từ để trả lời.
Tuy nhiên, trên thực tế, chúng ta sẽ thấy rằng chúng tôi có thể làm điều đó trong thời gian rất, rất nhanh chóng.
Và nó sẽ liên quan đến việc thực hiện một cái gì đó được gọi là một bảng băm,
và mặc dù ở cái nhìn đầu tiên điều này được gọi là một bảng băm sẽ
cho phép chúng tôi đạt được những thời gian nhanh chóng phản ứng siêu,
nó chỉ ra rằng có trong thực tế một vấn đề.
Khi nói đến thời gian để thực hiện điều này được gọi là một lần nữa, tôi đang làm nó một lần nữa.
Tôi là người duy nhất ở đây.
Khi nói đến thời gian để thực hiện điều này được gọi là một bảng băm,
chúng ta sẽ phải đưa ra quyết định.
Làm thế nào lớn nên điều này thực sự là gì?
Và khi chúng tôi bắt đầu số chèn vào bảng băm này,
làm thế nào chúng ta sẽ để lưu trữ chúng theo cách như vậy
rằng chúng ta có thể nhận được chúng trở lại một cách nhanh chóng như chúng tôi đã nhận chúng trong?
Nhưng chúng ta sẽ thấy lâu, câu hỏi này của
khi ngày sinh nhật của tất cả mọi người trong lớp sẽ được khá Gecman.
Nó chỉ ra rằng trong phòng này, chúng tôi đã có vài trăm người,
do đó, các tỷ lệ cược rằng hai chúng tôi có cùng một ngày sinh nhật có lẽ là khá cao.
Điều gì sẽ xảy ra nếu chỉ có 40 của chúng tôi trong căn phòng này?
Tỷ lệ cược của hai người có cùng ngày sinh là gì?
[Sinh viên] Hơn 50%.
Yeah, trên 50%. Trong thực tế, tôi thậm chí còn mang một biểu đồ.
Nó chỉ ra và điều này thực sự chỉ là một Sneak Preview
nếu chỉ có 58 của chúng tôi trong căn phòng này, xác suất của 2 của chúng tôi
có cùng ngày sinh là cực kỳ cao, gần như 100%,
và điều đó sẽ gây ra một bó toàn bộ bị tổn thương đối với chúng tôi hôm thứ Tư.
>> Với mà nói, chúng ta hãy hoãn ở đây. Chúng tôi sẽ gặp bạn vào thứ tư.
[Vỗ tay]
[CS50.TV]