[MUSIC CHƠI] [VIDEO PLAYBACK] -Anh ấy đang nói dối. -Về cái gì? -Tôi không biết. -Vậy Chúng ta biết gì? -đó Lúc 9:15, Ray Santoya là tại máy ATM. -Yeah. Vậy câu hỏi là, những gì Anh ta làm lúc 9:16? -Shooting 9 mm ở một cái gì đó. Có lẽ ông đã nhìn thấy những tay bắn tỉa. -Hoặc Được làm việc với anh ta. -Wait. Quay trở lại một. -Bạn nhìn thấy gì? -Bring Khuôn mặt của mình lên màn hình đầy đủ. Kính -His. -Có Một sự phản ánh. -Đó Là đội bóng chày Nuevitas. Đó là biểu tượng của họ. Và cậu ta đang nói chuyện với bất cứ ai mặc áo khoác đó. [END PLAYBACK] DAVID Malan: Tất cả các quyền. Đây là CS50 và điều này là nhiều hơn một chút của [Không nghe thấy] mà bạn dabbling với vấn đề thiết lập bốn. Hôm nay chúng ta bắt đầu nhìn nhiều hơn một chút sâu vào những điều được gọi là con trỏ, mà mặc dù nó một chủ đề khá phức tạp, nó chỉ ra rằng nó sẽ là phương tiện mà chúng tôi có thể bắt đầu xây dựng và lắp ráp các chương trình phức tạp hơn nhiều. Nhưng chúng tôi đã làm nó vào ngày thứ tư cuối cùng bằng cách của một số claymation đầu tiên. Vì vậy, đây, nhớ lại, là Binky và chúng tôi đã sử dụng ông để có một cái nhìn tại một chương trình không thực sự làm bất cứ điều gì thú vị, nhưng nó đã tiết lộ một vài vấn đề. Vì vậy, để bắt đầu ngày hôm nay, tại sao chúng ta không đi bộ một cách nhanh chóng thông qua một vài trong số các bước sau, cố gắng chắt lọc từ ngữ của con người chính xác những gì đang xảy ra ở đây và tại sao điều này là xấu, và sau đó di chuyển về và thực sự bắt đầu xây dựng cái gì với kỹ thuật này? Vì vậy, đây là những người đầu tiên hai dòng trong chương trình này và trong điều khoản của layman, những gì được hai dòng này đang làm gì? Một người nào đó là hợp lý thoải mái với những gì đã tuyên bố trên màn hình? Hai dòng này đang làm gì? Đó không phải là tất cả mà khác nhau từ tuần thứ nhất, nhưng có một số biểu tượng đặc biệt mới. Yeah? Trở lại ở đó. Đung Khai báo con trỏ? DAVID Malan: Nói một lần nữa? Đung Khai báo con trỏ? DAVID Malan: con trỏ Kê khai, chúng ta hãy tinh chỉnh nó nhiều hơn một chút. Đung [Không nghe thấy] địa chỉ x và sau đó y. DAVID Malan: Và sau đó giải quyết. Vì vậy, cụ thể những gì chúng tôi đang làm là chúng ta đang khai báo hai biến. Các biến này, mặc dù, đang đi là kiểu int sao, mà cụ thể hơn có nghĩa là họ sẽ lưu trữ địa chỉ của một int, tương ứng, x và y. Bây giờ đang có bất kỳ giá trị? Có bất kỳ địa chỉ thực tế trong những hai biến vào thời điểm này trong thời gian? Không. Nó chỉ là cái gọi là giá trị rác. Nếu bạn không thực sự chỉ định một biến, bất cứ điều gì là trong RAM trước đây là sẽ điền bằng số không và những người thân cả các biến. Nhưng chúng ta chưa biết những gì họ đang có và đó là sẽ là chìa khóa để lý do tại sao Binky mất đầu tuần trước. Vì vậy, đây là claymation hóa thân của này nhờ đó mà bạn có chỉ là hai biến, ít miếng tròn bằng đất sét, có thể lưu trữ các biến, nhưng như các mũi tên quấn lên đề nghị, họ đang không thực sự chỉ bất cứ nơi nào để biết mỗi se. Vì vậy, sau đó chúng tôi đã có dòng này, và điều này là mới tuần trước, malloc cho bộ nhớ phân bổ, mà chỉ là một cách ưa thích nói cho các hệ điều hành, Linux hoặc Mac OS hay Windows, hey, cho tôi một số bộ nhớ, và tất cả các bạn phải nói hệ điều hành là những gì khi yêu cầu nó cho bộ nhớ. Nó sẽ không quan tâm những gì bạn sẽ làm gì với nó, nhưng bạn cần phải cho các điều hành hệ thống những gì bằng cách malloc. Yeah? Đung bao nhiêu? DAVID Malan: bao nhiêu? Bao nhiêu trong byte, và như vậy, điều này, một lần nữa, một ví dụ giả tạo, chỉ là nói, cho tôi kích cỡ của một int. Bây giờ, kích thước của một int là bốn byte hoặc 32 bit. Vì vậy, đây chỉ là một cách nói, hey, hệ điều hành, cho tôi bốn byte của bộ nhớ mà tôi có thể sử dụng theo ý của tôi, và đặc biệt, những gì hiện malloc trả về với sự tôn trọng cho rằng đoạn bốn byte? Đung Address? DAVID Malan: Các địa chỉ. Địa chỉ rằng đoạn bốn byte. Chính xác. Và đó là những gì được lưu trữ cuối cùng trong x và đó là lý do tại sao chúng ta không thực sự quan tâm đến những số đó địa chỉ là, cho dù đó là ox1 hoặc ox2 hoặc một số địa chỉ hex khó hiểu. Chúng tôi chỉ quan tâm đến những bức tranh đó là biến x bây giờ là chỉ với đoạn bộ nhớ. Vì vậy, các mũi tên đại diện cho một con trỏ, hoặc Cụ thể hơn, một địa chỉ bộ nhớ. Nhưng một lần nữa, chúng ta thường không quan tâm những gì những địa chỉ thực tế là. Bây giờ, dòng này nói những gì trong điều khoản của layman? Sao x được 42 dấu chấm phẩy. Điều đó có nghĩa là gì? Bạn muốn đi đâu? Đừng gãi cổ của bạn. Đung Địa chỉ của x là số 42. DAVID Malan: Địa chỉ của x là 42. Không hẳn. Vì vậy, gần gũi, nhưng không hoàn toàn, bởi vì có ngôi sao đó là tiền tố x này. Vì vậy, chúng ta cần phải tinh chỉnh một chút. Yeah? Đung Các giá trị mà con trỏ x được trỏ đến là 42. DAVID Malan: OK. Giá trị mà con trỏ x là trỏ đến, chúng ta hãy nói, sẽ là 42, hay nói một cách khác, các ngôi sao x nói, đi đến bất cứ địa chỉ là x, cho dù đó là 1 Oxford Street hoặc 33 đường Oxford hoặc ox1 hoặc ox33, bất cứ điều gì địa chỉ số là, sao x là dereferencing của x. Vì vậy, đi đến địa chỉ đó và sau đó đưa số 42 đó. Vì vậy, đó sẽ là một cách tương đương với nói rằng. Vì vậy, đó là tất cả tiền phạt và sau đó chúng tôi sẽ đại diện cho hình ảnh như sau đó chúng tôi đã thêm 42 cho rằng đoạn bốn byte ở phía bên tay phải, nhưng dòng này là nơi mà mọi thứ đã không như mong đợi và đầu Binky của popped off vào thời điểm này, bởi vì những điều xấu xảy ra khi bạn tới đích của các giá trị rác hoặc bạn tới đích không hợp lệ con trỏ, và tôi nói không hợp lệ bởi vì tại thời điểm này trong câu chuyện, những gì là bên trong của y? Giá trị của y dựa là gì trên vài bước qua? Yeah? Cái gì thế? Đung Một địa chỉ. DAVID Malan: Một địa chỉ. Nó phải là một địa chỉ nhưng tôi khởi tạo nó? Vì vậy, tôi vẫn chưa được. Vì vậy, những gì được biết đến là trong đó không? Nó chỉ là một số giá trị rác. Nó có thể là bất kỳ địa chỉ từ số không đến 2 tỷ nếu bạn có hai hợp đồng biểu diễn của bộ nhớ RAM, hoặc không có đến 4 tỷ USD nếu bạn đã có bốn GB RAM. Đó là một số giá trị rác, nhưng vấn đề là rằng hệ điều hành, nếu nó đã không đưa cho bạn rằng đoạn bộ nhớ đặc biệt rằng bạn đang cố gắng để đi đến, nó thường sẽ gây ra những gì chúng tôi đã nhìn thấy như là một lỗi phân khúc. Vì vậy, trong thực tế, bất kỳ bạn của những người có đấu tranh tại vấn đề ở giờ văn phòng hoặc trong những vấn đề đó là nhiều nói chung với cố gắng tìm ra một lỗi phân khúc, đó thường có nghĩa là bạn đang chạm vào một phân đoạn của nhớ rằng bạn không nên. Bạn đang chạm vào bộ nhớ hệ điều hành có không cho phép bạn để liên lạc, cho dù đó là bằng cách đi quá xa trong mảng của bạn hoặc bắt đầu từ bây giờ, cho dù đó là bởi vì bạn đang chạm vào bộ nhớ mà chỉ là một số giá trị rác. Vì vậy, làm sao x ở đây là Loại hành vi không xác định. Bạn không bao giờ nên làm điều đó bởi vì tỷ lệ cược được, chương trình chỉ là đi đến sụp đổ, bởi vì bạn đang nói, đi đến địa chỉ này và bạn không có ý tưởng địa chỉ đó thực sự là. Vì vậy, các hệ điều hành có khả năng đi đến sụp đổ chương trình của bạn và kết quả là thực sự, đó là những gì xảy ra ở đó để Binky. Vì vậy, cuối cùng, Binky cố định vấn đề này với điều này. Vì vậy, chương trình riêng của mình đã hoàn thiện. Nhưng nếu bạn sắp xếp các giả mạo trước và thực hiện dòng này thay vào đó, y bằng x có nghĩa là bất cứ điều gì chỉ địa chỉ là một x, cũng đặt nó trong y. Và vì vậy những bức tranh, chúng tôi đã đại diện này với hai mũi tên từ x và y từ trỏ đến cùng một nơi. Vì vậy, về mặt ngữ nghĩa, x bằng để y vì cả của những người được lưu trữ cùng địa chỉ, ergo chỉ ở mức 42, và bây giờ, khi bạn nói sao y, đi đến địa chỉ trong y, này có hiệu quả thú vị. Vì vậy, các địa chỉ trong y là giống như là địa chỉ trong x. Vì vậy, nếu bạn nói đi đến địa chỉ trong y và thay đổi giá trị đến 13, người khác đang bị ảnh hưởng? X được, điểm D, có thể nói, nên cũng bị ảnh hưởng. Và quả thực, làm thế nào Nick vẽ bức tranh này trong claymation là chính xác đó. Mặc dù chúng tôi thực hiện theo các con trỏ y, chúng tôi đã kết thúc trong cùng một vị trí, và như vậy nếu chúng ta để in ra x hoặc y pointee của, sau đó chúng ta sẽ thấy giá trị của 13. Bây giờ, tôi nói pointee được phù hợp với các video. Các lập trình viên, để tôi kiến thức, không bao giờ thực sự nói pointee từ, rằng đó là nhọn tại, nhưng đối với sự nhất quán với video, nhận ra đó là tất cả những gì có nghĩa là trong tình huống đó. Vì vậy, bất kỳ câu hỏi về claymation hoặc con trỏ hoặc malloc chỉ chưa? Không có? Được rồi. Vì vậy mà không có thêm ado, chúng ta hãy có một cái nhìn tại nơi này có thực sự được sử dụng trong một thời gian. Vì vậy, chúng tôi đã có thư viện CS50 này đó là có tất cả các chức năng này. Chúng tôi đã sử dụng getInt rất nhiều, GetString, có lẽ GetLongLong trước trong PSet tôi một hoặc như vậy, nhưng những gì thực sự đã diễn ra? Vâng, chúng ta hãy có một cái nhìn nhanh chóng bên dưới mui xe tại một chương trình truyền cảm hứng tại sao chúng tôi cung cấp cho bạn các CS50 thư viện, và thực sự là của tuần trước, chúng tôi bắt đầu tham gia những bánh xe đào tạo ra. Vì vậy, điều này bây giờ được sắp xếp của một người sau khi chết của những gì có được đi vào bên trong các thư viện CS50, mặc dù bây giờ chúng ta sẽ bắt đầu di chuyển đi từ nó đối với hầu hết các chương trình. Vì vậy, đây là một chương trình được gọi là scanf 0. Đó là siêu ngắn. Nó chỉ có những dòng này, nhưng nó giới thiệu một chức năng gọi là scanf rằng chúng tôi đang thực sự sẽ thấy trong một thời điểm bên trong của thư viện CS50, mặc dù trong một hình thức hơi khác nhau. Vì vậy, chương trình này trên đường 16 được khai báo một biến x. Vì vậy, cho tôi bốn byte cho một int. Nó đã nói với người sử dụng, số lượng xin vui lòng, và sau đó đây là một dòng thú vị mà thực sự kết nối cùng với tuần trước và cái này. Scanf, và sau đó thông báo phải mất một định dạng chuỗi, giống như printf, % i có nghĩa là một int, và sau đó phải mất một số thứ hai mà trông hơi funky. Đó là ký hiệu x, và để nhớ lại, chúng ta chỉ nhìn thấy một lần vào tuần cuối cùng này. Không dấu và x đại diện cho những gì? Những gì hiện dấu và làm trong C? Yeah? Đung Các địa chỉ. DAVID Malan: Địa chỉ của. Vì vậy, nó là ngược lại của các nhà điều hành sao, trong khi các nhà điều hành sao cho biết, vào địa chỉ này, các nhà điều hành ký hiệu nói, tìm ra địa chỉ của biến này, và vì vậy điều này là quan trọng, bởi vì Mục đích của scanf trong cuộc sống là để quét sử dụng của nhập vào từ bàn phím, phụ thuộc vào bất cứ điều gì anh ta hoặc cô loại, và sau đó đọc đầu vào của người dùng vào một biến, nhưng chúng tôi đã thấy trong hai tuần qua đó là chức năng hoán đổi mà chúng ta cố gắng dễ dàng để thực hiện chỉ bị phá vỡ. Nhớ lại rằng với các chức năng trao đổi, nếu chúng ta chỉ tuyên bố A và B như ints, chúng tôi đã thành công hoán đổi hai biến bên trong của swap giống như với sữa và OJ, nhưng ngay sau khi hoán đổi trở lại, là những gì các kết quả liên quan cho x và y, các giá trị ban đầu? K có gì. Yeah. Không có gì xảy ra thời gian đó, vì giao dịch hoán đổi chỉ thay đổi bản sao địa phương của mình, mà là để nói, tất cả thời gian này, bất cứ khi nào chúng tôi đã được đi qua trong lập luận chức năng, chúng tôi chỉ cần đi qua các bản sao của các đối số. Bạn có thể làm với điều đó bất cứ điều gì bạn muốn với chúng, nhưng họ sẽ không có ảnh hưởng về giá trị ban đầu. Vì vậy, đây là vấn đề nếu bạn muốn có một chức năng như scanf trong cuộc sống, mà mục đích là để quét đầu vào của người dùng từ bàn phím và sau đó điền vào chỗ trống, do đó, để nói chuyện, đó là, cung cấp cho một biến như x một giá trị, bởi vì nếu tôi là để chỉ cần vượt qua x để scanf, nếu bạn xem xét logic của cuối cùng tuần, scanf có thể làm bất cứ điều gì nó muốn với một bản sao của x, nhưng nó có thể không vĩnh viễn thay đổi x trừ khi chúng tôi cung cấp scanf một bản đồ kho báu, có thể nói, trong đó x đánh dấu chỗ đó, chúng tôi vượt qua trong các địa chỉ của x để scanf thể đến đó và thực sự thay đổi giá trị của x. Và như vậy thực sự, tất cả rằng chương trình này không nếu tôi làm cho scanf 0, trong mã nguồn của tôi 5m thư mục, tạo scanf 0, dot giảm scanf, số xin 50, cảm ơn cho 50. Vì vậy, nó không phải là tất cả những gì thú vị, nhưng những gì đang thực sự xảy ra là ngay sau khi tôi gọi scanf đây, giá trị của x đang được thay đổi vĩnh viễn. Bây giờ, điều này có vẻ tốt đẹp và tốt, và trong thực tế, nó có vẻ như chúng ta không thực sự cần thư viện CS50 ở tất cả nữa. Ví dụ, chúng ta hãy chạy này một lần nữa ở đây. Hãy để tôi mở lại nó cho một thứ hai. Hãy thử một số xin vui lòng và thay vì nói 50 như trước đây, chúng ta hãy chỉ nói không. OK, đó là một chút lạ. ĐƯỢC. Và chỉ một số vô nghĩa ở đây. Vì vậy, nó dường như không xử lý các tình huống sai lầm. Vì vậy, chúng ta cần phải bắt đầu tối thiểu thêm một số kiểm tra lỗi để đảm bảo rằng người dùng có gõ vào một số thực tế như 50, vì những lời dường như gõ không được phát hiện là có vấn đề, nhưng có lẽ nó nên được. Chúng ta hãy nhìn vào phiên bản này bây giờ đó là cố gắng của tôi để reimplement GetString. Nếu scanf có tất cả điều này chức năng được xây dựng trong, tại sao chúng ta được dabbling với những bánh xe đào tạo như GetString? Vâng, ở đây có lẽ là của riêng tôi phiên bản đơn giản của GetString theo đó một tuần trước đây, tôi có thể nói, cho tôi một chuỗi và gọi nó là đệm. Hôm nay, tôi sẽ bắt đầu chỉ nói sao char, trong đó, thu hồi, nó chỉ là đồng nghĩa. Nó trông đáng sợ nhưng nó hiện tượng như vậy. Vì vậy, cho tôi một biến gọi là bộ đệm đó là sẽ lưu trữ một chuỗi, cho chuỗi sử dụng xin vui lòng, và sau đó, giống như trước đây, chúng ta hãy cố gắng vay mượn bài học này scanf % s thời gian này và sau đó vượt qua trong bộ đệm. Bây giờ, một kiểm tra sự tỉnh táo nhanh chóng. Tại sao tôi không nói dấu và đệm thời gian này? Suy ra từ ví dụ trước. Đung sao Char là một con trỏ. DAVID Malan: Chính xác, bởi vì thời gian này, char sao đã là một con trỏ, một địa chỉ, theo định nghĩa của ngôi sao đang ở đó. Và nếu scanf hy vọng một địa chỉ, nó cũng đủ chỉ để vượt qua trong bộ đệm. Tôi không cần phải nói dấu và đệm. Đối với những người tò mò, bạn có thể làm một cái gì đó như thế này. Nó sẽ có ý nghĩa khác nhau. Điều này sẽ cung cấp cho bạn một con trỏ cho một con trỏ, mà thực sự là một điều hợp lệ trong C, nhưng đối với bây giờ, chúng ta hãy giữ cho nó đơn giản và giữ những câu chuyện phù hợp. Tôi chỉ cần đi để vượt qua trong đệm và đó là chính xác. Vấn đề là mặc dù này. Hãy để tôi đi trước và chạy này chương trình sau khi biên dịch nó. Hãy scanf 1. Chết tiệt, trình biên dịch của tôi bắt lỗi của tôi. Hãy cho tôi một giây. Clang. Hãy nói rằng scanf-1.c. ĐƯỢC. Hiện chúng tôi đi. Tôi cân no. CS50 ID có hình thiết lập cấu hình bảo vệ bạn chống lại chính mình. Tôi cần thiết để vô hiệu hóa các bằng chạy kêu vang thủ thời gian này. Vì vậy, xin vui lòng chuỗi. Tôi sẽ đi trước và gõ trong thế giới hello yêu thích của tôi. OK, null. Đó không phải là những gì tôi đã gõ. Vì vậy, nó là biểu hiện của một cái gì đó là sai. Hãy để tôi đi trước và gõ trong một chuỗi rất dài. Thanks for null và tôi không biết nếu tôi sẽ để có thể sụp đổ nó. Hãy thử một bản sao nhỏ dán và xem nếu điều này sẽ giúp. Chỉ cần dán rất nhiều về điều này. Đó chắc chắn là một lớn hơn chuỗi hơn bình thường. Hãy chỉ thực sự viết nó. Không. Chết tiệt. Lệnh không tìm thấy. Vì vậy, đó là không liên quan. Đó là bởi vì tôi dán một số nhân vật xấu, nhưng điều này hóa ra không phải là đi để làm việc. Hãy thử một lần nữa, bởi vì nó là thú vị hơn nếu chúng ta thực sự sụp đổ nó. Hãy gõ này và bây giờ, tôi sẽ sao chép một chuỗi rất dài và bây giờ chúng ta hãy xem chúng tôi có thể sụp đổ điều này. Chú ý rằng tôi bỏ qua không gian và dòng mới và dấu chấm phẩy và tất cả các nhân vật sôi nổi. Nhập. Và bây giờ mạng chỉ là bị chậm. Tôi giữ phím Command-V quá dài, rõ ràng. Chết tiệt! Lệnh không tìm thấy. ĐƯỢC. Vâng, điểm là dù sao sau. Vì vậy, những gì đang thật sự diễn trên với tuyên bố này của char sao đệm trên đường dây 16? Vì vậy, những gì tôi nhận được khi tôi tuyên bố một con trỏ? Tất cả tôi nhận được là một giá trị bốn byte gọi là bộ đệm, nhưng những gì bên trong của nó tại thời điểm này? Nó chỉ là một số giá trị rác. Bởi vì bất cứ lúc nào bạn khai báo một biến trong C, nó chỉ là một số giá trị rác, và chúng ta bắt đầu chuyến đi trên thực tế này. Bây giờ, khi tôi nói với scanf, đi đến địa chỉ này và đặt bất cứ người dùng đánh vào. Nếu sử dụng các loại trong hello thế giới, tốt, nơi nào tôi đặt nó? Đệm là một giá trị rác. Vì vậy, đó là loại giống như một mũi tên đó là chỉ tận nơi đâu. Có lẽ nó trỏ ngay tại đây trong bộ nhớ của tôi. Và do đó, khi người sử dụng loại trong hello thế giới, chương trình cố gắng để đưa các chuỗi hello world backslash 0 trong đó đoạn bộ nhớ. Nhưng với xác suất cao, nhưng rõ ràng không phải là 100% xác suất, máy tính sẽ sụp đổ sau đó chương trình này vì đây không phải là nhớ tôi nên được phép chạm. Vì vậy, trong ngắn hạn, chương trình này là thiếu sót cho chính xác lý do đó. Tôi về cơ bản không làm những gì? Những bước có tôi bỏ qua, giống như chúng ta bỏ qua với ví dụ đầu tiên Binky của? Yeah? Đung cấp phát bộ nhớ? DAVID Malan: Cấp phát bộ nhớ. Tôi đã không thực sự phân bổ bất kỳ bộ nhớ cho chuỗi đó. Vì vậy, chúng tôi có thể sửa lỗi này trong một vài cách. Một, chúng ta có thể giữ cho nó đơn giản và trong thực tế, bây giờ bạn sẽ bắt đầu nhìn thấy một mờ của dòng giữa những gì một mảng là, những gì một chuỗi là gì, char sao là, những gì một mảng các ký tự là. Dưới đây là một ví dụ thứ hai liên quan đến các chuỗi và thông báo tất cả tôi đã thực hiện trên dòng 16 là, thay vì nói đệm đó là có được một char sao, một con trỏ đến một đoạn bộ nhớ, Tôi sẽ rất chủ động cung cấp cho bản thân mình một bộ đệm cho 16 nhân vật, và trong thực tế, nếu bạn đã quen thuộc với đệm hạn, có lẽ từ thế giới của video, nơi một video là đệm, đệm, đệm. Vâng, các kết nối ở đây là gì? Vâng, bên trong của YouTube và bên trong của người chơi video nói chung là một mảng đó là lớn hơn 16. Nó có thể là một mảng có kích thước một megabyte, có thể 10 MB, và vào mảng mà không trình duyệt của bạn tải về một bó toàn bộ các byte, một bó toàn bộ MB video, và các máy nghe nhạc video, Của YouTube hoặc bất cứ ai là, bắt đầu đọc các byte từ mảng đó, và bất cứ lúc nào bạn nhìn thấy từ đệm, đệm, đó có nghĩa là người chơi có nhận được đến cuối của mảng đó. Các mạng như vậy là chậm mà nó không có nạp lại mảng với byte nữa và do đó, bạn đang trên bit để hiển thị cho người dùng. Vì vậy, bộ đệm là một thuật ngữ apt đây trong đó nó chỉ là một mảng, một đoạn bộ nhớ. Và điều này sẽ sửa chữa nó vì thực ra mà bạn có thể điều trị các mảng như thể họ là những địa chỉ, mặc dù đệm chỉ là một biểu tượng, đó là một chuỗi các ký tự, đệm, đó là hữu ích cho tôi, các lập trình viên, bạn có thể vượt qua tên của nó xung quanh như thể đó là một con trỏ, như thể nó là địa chỉ của một đoạn bộ nhớ trong 16 ký tự. Vì vậy, đó là để nói, tôi có thể vượt qua scanf chính xác từ đó và vì vậy bây giờ, nếu tôi thực hiện chương trình này, làm cho scanf 2, dot slash scanf 2, và gõ hello thế giới, Nhập, time-- đó Hmm, những gì đã xảy ra? Chuỗi vui lòng. Tôi đã làm sai cái gì? Xin chào thế giới, đệm. Chào thế giới. Ah, tôi biết nó đang làm gì. ĐƯỢC. Vì vậy, nó đọc lên đến khi không gian đầu tiên. Vì vậy, hãy ăn gian cho chỉ là một khoảnh khắc và nói rằng tôi chỉ muốn gõ gì đó thực sự lâu dài như thế này là một câu dài đó là một, hai, ba, bốn, năm, sáu, bảy, tám, chín, 10, 11, 12, 13, 14, 15, 16. ĐƯỢC. Nó thực sự là một câu dài. Vì vậy, câu này là dài hơn 16 ký tự và do đó, khi tôi nhấn Enter, điều gì sẽ xảy ra? Vâng, trong trường hợp này của đệm câu chuyện, tôi đã tuyên bố để thực sự là một mảng với 16 ký tự sẵn sàng để đi. Vì vậy, một, hai, ba, bốn, năm, sáu, bảy, tám, chín, 10, 11, 12, 13, 14, 15, 16. Vì vậy, 16 ký tự, và bây giờ, khi tôi đọc trong một cái gì đó như thế này là một lâu câu, chuyện gì sẽ xảy ra là rằng tôi sẽ đọc trong này là một lâu S-E-N-T-E-N-C-E, câu. Vì vậy, đây là cố ý một điều xấu mà tôi giữ bằng văn bản ngoài ranh giới của mảng của tôi, vượt ra ngoài ranh giới của bộ đệm của tôi. Tôi có thể nhận được may mắn và chương trình sẽ tiếp tục chạy và không quan tâm, nhưng nói chung, điều này thực sự sẽ sụp đổ chương trình của tôi, và nó là một lỗi trong tôi mã thời điểm tôi bước vượt ra ngoài ranh giới của mảng đó, bởi vì tôi không biết nếu nó nhất thiết phải đi đến sụp đổ hoặc nếu tôi chỉ cần đi để có được may mắn. Vì vậy, đây là vấn đề bởi vì trong trường hợp này, nó có vẻ làm việc và chúng ta hãy cám dỗ số phận ở đây, mặc dù IDE có vẻ chịu đựng khá một chút of-- Hiện chúng tôi đi. Cuối cùng. Vì vậy, tôi là người duy nhất có thể thấy điều này. Vì vậy, tôi chỉ có rất nhiều cách gõ fun ra một cụm từ thực tế thực sự lâu dài rằng nó chắc chắn vượt quá 16 byte, vì tôi gõ vào điên dài nhiều đường này cụm từ, và sau đó thông báo những gì đã xảy ra. Chương trình thử in nó và sau đó có một lỗi phân khúc và lỗi segmentation là khi một cái gì đó như thế này xảy ra và các hệ điều hành nói Không, không thể chạm vào bộ nhớ. Chúng tôi đang đi để giết Chương trình hoàn toàn. Vì vậy, điều này có vẻ có vấn đề. Tôi đã cải thiện các chương trình, theo đó ít nhất có một số bộ nhớ, nhưng điều này có vẻ như để giới hạn hàm GetString để nhận được dây của một số chiều dài hữu hạn 16. Vì vậy, nếu bạn muốn hỗ trợ còn câu hơn 16 ký tự, Bạn làm gì thế? Vâng, bạn có thể tăng kích thước của bộ đệm này đến 32 hay mà dường như loại ngắn. Tại sao chúng ta không chỉ làm cho nó 1,000 nhưng đẩy lùi. Các phản ứng trực giác của những gì chỉ tránh vấn đề này bằng cách làm đệm của tôi lớn hơn, giống như 1000 ký tự? Bằng cách thực hiện GetString cách này. Những gì là tốt hay xấu đây? Yeah? Đung Nếu bạn ràng buộc lên rất nhiều không gian và bạn không sử dụng nó, sau đó bạn không thể tái phân bổ không gian đó. DAVID Malan: Tuyệt đối. Đó là lãng phí trong chừng mực nếu bạn không thực sự cần 900 của những byte nhưng bạn đang yêu cầu 1.000 trong tổng số anyway, bạn chỉ cần tốn nhiều bộ nhớ trên máy tính của người sử dụng hơn bạn cần, và sau khi tất cả, một số bạn đã gặp phải trong cuộc sống là khi bạn đang chạy rất nhiều chương trình và họ đang ăn lên rất nhiều bộ nhớ, điều này thực sự có thể ảnh hưởng đến tốc và kinh nghiệm của người sử dụng trên máy tính. Vì vậy, đó là loại của một giải pháp lười biếng, chắc chắn, và ngược lại, nó không chỉ lãng phí, những vấn đề vẫn còn, ngay cả khi tôi làm bộ đệm của tôi 1000? Yeah? Đung Các chuỗi có chiều dài 1.001. DAVID Malan: Chính xác. Nếu chuỗi của bạn là chiều dài 1.001, bạn có cùng một vấn đề chính xác, và bằng cách lập luận của tôi, tôi sẽ chỉ sau đó làm cho nó năm 2000, nhưng bạn không biết tiến lớn như thế nào cần, và nêu ra, tôi phải biên dịch chương trình của tôi trước khi cho phép người sử dụng và tải về nó. Vì vậy, đây là chính xác các loại thứ mà cố gắng thư viện CS50 để giúp chúng tôi và chúng tôi sẽ chỉ trong nháy mắt tại một số các thực hiện cơ bản ở đây, nhưng đây là CS50 dot C. là file đó là được vào CS50 IDE tất cả các tuần mà bạn đã sử dụng. Đó là tiền biên dịch và bạn đã được sử dụng nó tự động bởi bản chất của việc có các dash L CS50 cờ với kêu vang, nhưng nếu tôi di chuyển xuống qua tất cả các chức năng này, đây là GetString, và chỉ để cung cấp cho bạn một hương vị của những gì đang xảy ra, chúng ta hãy xem nhanh sự phức tạp tương đối. Nó không phải là một siêu dài chức năng, nhưng chúng tôi đã không phải suy nghĩ tất cả các khó khăn về làm thế nào để đi về nhận chuỗi. Vì vậy, đây là bộ đệm của tôi và tôi dường như khởi tạo nó thành vô giá trị. Điều này, tất nhiên, là giống như là char sao, nhưng tôi quyết định ở thực hiện các thư viện CS50 rằng nếu chúng ta sẽ là hoàn toàn năng động, Tôi không biết trước như thế nào lớn của một người sử dụng chuỗi sẽ muốn nhận được. Vì vậy, tôi sẽ bắt đầu chỉ với một chuỗi rỗng và tôi sẽ xây dựng lên càng nhiều bộ nhớ như tôi cần phải phù hợp với những chuỗi người dùng và nếu tôi không có đủ, tôi sẽ hỏi hệ điều hành cho nhiều bộ nhớ hơn. Tôi sẽ chuyển chuỗi của họ thành ra một phần lớn của bộ nhớ và tôi sẽ phát hành hoặc giải phóng chunk không đủ lớn bộ nhớ và chúng tôi chỉ đi để làm điều này lặp đi lặp lại. Vì vậy, một cái nhìn nhanh chóng, đây chỉ là một biến mà tôi sẽ theo dõi năng lực của các bộ đệm của tôi. Có bao nhiêu byte tôi có thể phù hợp? Dưới đây là một biến n với mà tôi sẽ giữ theo dõi bao nhiêu byte thực sự trong bộ đệm hay mà người dùng đã gõ. Nếu bạn đã không nhìn thấy điều này trước khi, bạn có thể xác định rằng một biến như một int là unsigned, mà như tên cho thấy, có nghĩa là nó không âm, và tại sao Tôi đã bao giờ muốn làm phiền nêu rõ rằng một int không chỉ là một int, nhưng nó là một int unsigned? Đó là một int không âm. Nào [Không nghe thấy] có nghĩa là gì? Đung Nó mô tả một số tiền bộ nhớ có thể được [không nghe được]. DAVID Malan: Yeah. Vì vậy, nếu tôi nói không dấu, điều này thực sự đem lại cho bạn một chút về bộ nhớ thêm và có vẻ như loại ngớ ngẩn, nhưng nếu bạn có một chút bộ nhớ bổ sung, mà có nghĩa là bạn có hai lần như nhiều giá trị mà bạn có thể đại diện, bởi vì nó có thể là 0 hoặc 1. Vì vậy, theo mặc định, một int có thể được tạm âm 2 tỷ tất cả các cách lên đến 2 tỷ dương. Đó là phạm vi lớn, nhưng nó vẫn còn loại lãng phí nếu bạn chỉ quan tâm kích thước, mà chỉ bằng trực giác nên không âm hoặc tích cực hoặc 0, cũng sau đó, tại sao bạn đang lãng phí 2 tỷ giá trị có thể cho số âm nếu bạn sẽ không bao giờ sử dụng chúng? Vì vậy, bằng cách nói unsigned, bây giờ tôi có thể int được giữa 0 và khoảng 4 tỷ USD. Vì vậy, đây chỉ là một int C vì lý do chúng tôi sẽ không nhận được vào ngay bây giờ là tại sao nó là một int thay vì của một char, nhưng ở đây là các ý chính của những gì đang xảy ra trên, và một số bạn có thể được sử dụng, ví dụ, Hàm fgetc ngay cả trong PSet bốn hoặc sau đó, chúng ta sẽ thấy nó một lần nữa trong vấn đề thiết lập năm, fgetc là tốt đẹp vì như tên loại, sắp xếp của arcanely cho thấy, đó là một chức năng mà được một nhân vật và vì vậy, những gì là cơ bản khác nhau về những gì chúng ta đang làm trong GetString là chúng ta không sử dụng scanf trong cùng một cách. Chúng tôi chỉ leo cùng bước-by-step hơn bất cứ điều gì người dùng gõ trong, bởi vì chúng tôi luôn luôn có thể phân bổ một char, và như vậy chúng ta có thể luôn luôn an toàn nhìn vào một char tại một thời điểm, và sự kỳ diệu bắt đầu xảy ra ở đây. Tôi sẽ di chuyển xuống giữa chức năng này chỉ để giới thiệu chức năng này một thời gian ngắn. Giống như có một Hàm malloc, có một hàm realloc nơi realloc cho phép bạn phân phối lại một đoạn bộ nhớ và làm cho nó lớn hơn hoặc nhỏ hơn. Vì vậy, câu chuyện dài ngắn và với một cái vẫy tay của tôi cho ngày hôm nay, biết rằng những gì GetString đang làm là nó loại của tăng trưởng kỳ diệu hay thu hẹp các bộ đệm như người sử dụng loại trong chuỗi của mình. Vì vậy, nếu người dùng gõ một chuỗi ngắn, mã này chỉ phân bổ đủ bộ nhớ để phù hợp với chuỗi. Nếu người sử dụng giữ đánh máy như tôi đã làm nó một lần nữa và một lần nữa và một lần nữa, tốt, nếu đệm của ban đầu lớn này và các chương trình nhận ra, để chờ một phút, tôi ra khỏi không gian, nó sẽ tăng gấp đôi kích thước của bộ đệm và sau đó tăng gấp đôi kích thước của bộ đệm và các mã nào tăng gấp đôi, nếu chúng ta nhìn vào nó ở đây, đó là chỉ thông minh một lớp lót này. Bạn có thể không nhìn thấy cú pháp này trước, nhưng nếu bạn nói sao bằng, đây là những điều tương tự như nói lần công suất 2. Vì vậy, nó chỉ giữ tăng gấp đôi năng lực của bộ đệm và sau đó nói với realloc để cung cấp cho bản thân nhiều bộ nhớ hơn. Bây giờ, như một sang một bên, có là các chức năng khác tại đây rằng chúng ta sẽ không nhìn vào chi tiết nào khác hơn là để hiển thị trong getInt, chúng tôi sử dụng GetString trong getInt. Chúng tôi kiểm tra xem nó không null, trong đó, thu hồi, là giá trị đặc biệt mà có nghĩa là một cái gì đó đã đi sai. Chúng tôi ra khỏi bộ nhớ. Tốt hơn kiểm tra cho điều đó. Và chúng ta trả lại một giá trị trọng điểm. Nhưng tôi sẽ làm theo ý kiến ​​như tại sao và sau đó chúng tôi sử dụng anh em họ này của scanf gọi sscanf và nó quay ra đó sscanf, hoặc chuỗi scanf, cho phép bạn có một cái nhìn tại các dòng người dùng đã gõ trong và cho bạn phân tích cơ bản nó và những gì tôi làm ở đây là tôi nói sscanf, phân tích bất cứ điều gì người dùng có gõ vào và chắc chắn% i, có một số nguyên trong nó, và chúng tôi sẽ không nhận được vào ngày hôm nay chính xác lý do tại sao cũng có a% c ở đây, nhưng điều đó một cách ngắn gọn cho phép chúng ta phát hiện nếu người dùng đã gõ trong một cái gì đó không có thật sau khi số lượng. Vì vậy, lý do mà getInt và GetString cho bạn biết để thử lại, thử lại, thử lại là vì tất cả các mã chúng tôi đã viết, nó loại nhìn vào đầu vào của người dùng trong việc bảo đảm nó hoàn toàn số hoặc đó là một thực tế nổi giá trị điểm hoặc tương tự, tùy thuộc vào những gì giá trị chức năng bạn đang sử dụng. Whew. ĐƯỢC. Đó là một mouthful nhưng ở đây là đó là lý do chúng tôi đã có những bánh xe đào tạo về là bởi vì ở mức thấp nhất, đó chỉ là rất nhiều điều mà có thể đi sai mà chúng ta muốn preemptively xử lý những điều chắc chắn trong tuần đầu tiên của lớp, nhưng bây giờ với PSet bốn PSet năm và ngoài bạn sẽ thấy rằng nó thêm lên cho đến bạn nhưng cũng có thể bạn đang có khả năng nhiều hơn giải quyết những loại vấn đề chính mình. Bất kỳ câu hỏi về GetString hoặc getInt? Yeah? Đung Tại sao bạn sẽ tăng gấp đôi năng lực của bộ đệm thay vì chỉ tăng nó bằng số tiền chính xác? DAVID Malan: Câu hỏi rất hay. Tại sao chúng ta sẽ tăng gấp đôi công suất của bộ đệm như trái ngược chỉ tăng nó bởi một số giá trị không đổi? Đó là một quyết định thiết kế. Chúng tôi chỉ quyết định rằng bởi vì nó có xu hướng là một ít tốn kém thời gian khôn ngoan để hỏi hệ điều hành cho bộ nhớ, chúng tôi đã không muốn kết thúc nhận vào một tình huống cho các chuỗi lớn rằng chúng tôi đã được yêu cầu hệ điều hành một lần nữa và một lần nữa và một lần nữa và một lần nữa trong kế nhanh chóng cho bộ nhớ. Vì vậy, chúng tôi chỉ quyết định, phần nào tùy tiện, nhưng chúng tôi hy vọng hợp lý, rằng, bạn biết không, chúng ta hãy cố gắng để có được trước của mình và chỉ cần giữ nó để tăng gấp đôi chúng ta giảm thiểu được số lần chúng tôi phải gọi malloc hoặc realloc, nhưng một bản án tổng cộng gọi trong trường hợp không biết những gì người dùng có thể muốn gõ. Cả hai cách có thể gây tranh cãi. Có thể cho rằng tốt. Vì vậy, chúng ta hãy xem xét một vài các tác dụng phụ khác của bộ nhớ, thứ có thể đi sai và các công cụ mà bạn có thể sử dụng để bắt các loại sai lầm. Hóa ra tất cả các bạn, mặc dù check50 đã không nói với bạn nhiều, đã được viết buggy Mã kể từ tuần thứ nhất, thậm chí nếu tất cả các bài kiểm tra check50 là trôi qua, và thậm chí nếu bạn và TF của bạn là siêu tự tin rằng mã của bạn hoạt động như dự định. Mã của bạn đã được buggy hay thiếu sót trong đó tất cả các bạn, trong việc sử dụng các thư viện CS50, đã được rò rỉ bộ nhớ. Bạn đã yêu cầu hệ điều hành cho bộ nhớ trong hầu hết các chương trình bạn đã viết, nhưng bạn đã không bao giờ thực sự được đưa nó trở lại. Bạn đã gọi GetString và getInt và GetFloat, nhưng với GetString, bạn đã không bao giờ được gọi là unGetString hoặc cho Chuỗi lại hay như thế, nhưng chúng tôi đã nhìn thấy rằng GetString không cấp phát bộ nhớ bằng cách này hay malloc Hàm realloc, mà chỉ là rất giống nhau trong tinh thần, tuy nhiên, chúng tôi đã yêu cầu hệ điều hành cho bộ nhớ và bộ nhớ một lần nữa và một lần nữa nhưng không bao giờ cho nó trở lại. Bây giờ, như một sang một bên, nó quay ra rằng khi một chương trình thoát, tất cả các bộ nhớ được tự động giải phóng. Vì vậy, nó không phải là một việc rất lớn. Nó sẽ không để phá vỡ IDE hoặc những thứ chậm lại, nhưng khi chương trình làm thường bị rò rỉ bộ nhớ và họ đang chạy trong một thời gian dài. Nếu bạn đã từng nhìn thấy chút ngu ngốc bãi biển bóng trong Mac OS hoặc đồng hồ cát trên Windows mà nó loại làm chậm lại hoặc suy nghĩ hay suy nghĩ hoặc chỉ thực sự bắt đầu chậm như rùa bò, nó rất có thể có thể được kết quả của một rò rỉ bộ nhớ. Những lập trình viên viết phần mềm bạn đang sử dụng yêu cầu hệ điều hành cho bộ nhớ mỗi vài phút, từng giờ. Nhưng nếu bạn đang chạy phần mềm, thậm chí nếu nó giảm thiểu trong máy tính của bạn giờ hoặc ngày kết thúc, bạn có thể được yêu cầu cho nhiều hơn và nhiều hơn bộ nhớ và không bao giờ thực sự sử dụng nó và do đó, mã của bạn có thể được, hoặc chương trình có thể bị rò rỉ bộ nhớ, và nếu bạn bắt đầu bị rò rỉ bộ nhớ, có ít bộ nhớ cho các chương trình khác, và hiệu quả là để làm chậm tất cả mọi thứ xuống. Bây giờ, điều này là bởi đến nay một trong các chương trình tồi tệ nhất bạn sẽ có cơ hội để chạy trong chừng mực CS50 như sản lượng của nó càng bí truyền hơn clang hoặc bù hoặc bất kỳ của các lệnh chương trình dòng chúng tôi đã chạy trước nhưng may mắn, nhúng vào trong đầu ra của nó là một số lời khuyên hữu ích mà siêu sẽ hữu ích, hoặc cho PSet bốn hoặc chắc chắn PSet năm. Vì vậy, valgrind là một công cụ mà có thể được sử dụng để tìm kiếm rò rỉ bộ nhớ trong chương trình của bạn. Đó là tương đối đơn giản để chạy. Bạn chạy valgrind và sau đó, thậm chí mặc dù nó là một chút dài dòng, dash dash rò rỉ séc bằng đầy đủ, và sau đó chấm giảm và tên của chương trình của bạn. Vì vậy, valgrind sau đó sẽ chạy chương trình của bạn và vào cuối của chương trình của bạn chạy trước khi nó tha và mang đến cho bạn một cửa sổ, nó sẽ phân tích của bạn chương trình trong khi nó được chạy và cho bạn biết bạn đã bị rò rỉ bất kỳ bộ nhớ và tốt hơn nữa, bạn đã chạm vào bộ nhớ không thuộc về bạn? Nó không thể bắt tất cả mọi thứ, nhưng nó khá tốt trong việc bắt hầu hết mọi thứ. Vì vậy, đây là một ví dụ của việc có chạy của tôi chương trình này, có chạy valgrind, trên một chương trình gọi là bộ nhớ, và tôi sẽ để làm nổi bật các đường thẳng cuối cùng là mối quan tâm của chúng tôi. Vì vậy, có nhiều hơn phiền nhiễu mà tôi đã bị xóa từ các slide. Nhưng chúng ta hãy xem những gì này Chương trình có khả năng nói với chúng tôi. Nó có khả năng nói với chúng ta điều như viết không hợp lệ kích thước 4. Nói cách khác, nếu bạn chạm vào bộ nhớ, đặc biệt 4 byte của bộ nhớ mà bạn không cần phải có, valgrind có thể nói với bạn rằng. Viết không hợp lệ kích thước 4. Bạn chạm vào bốn byte mà bạn không nên có. Trường hợp bạn đã làm điều đó? Đây là vẻ đẹp. Memory dot c dòng 21 là nơi bạn hơi say lên và đó là lý do tại sao nó có ích. Giống như GDB, nó có thể giúp chỉ cho bạn tại các lỗi thực tế. Bây giờ, con này nhiều hơn một chút tiết, nếu không khó hiểu. 40 byte trong 1 khối chắc chắn bị mất trong lỗ kỷ lục 1 của 1. Điều đó có nghĩa là gì? Vâng, nó chỉ có nghĩa là bạn yêu cầu 40 byte và bạn không bao giờ cho nó trở lại. Bạn gọi malloc hoặc bạn gọi GetString và các hệ điều hành đã cho bạn 40 byte, nhưng bạn không bao giờ trả tự do hoặc phát hành mà bộ nhớ, và công bằng, chúng tôi đã không bao giờ hiển thị bạn làm thế nào để trả lại bộ nhớ. Hóa ra có một siêu chức năng đơn giản được gọi là miễn phí. Nhận một đối, điều bạn muốn giải phóng hoặc trả lại, nhưng 40 byte, rõ ràng, trong chương trình này đã bị mất tại dòng 20 bộ nhớ chấm c. Vì vậy, chúng ta hãy xem chương trình này. Đó là siêu vô dụng. Nó chỉ thể hiện sự lỗi này cụ thể. Vì vậy, chúng ta hãy có một cái nhìn. Đây là chính và chính, thông báo, các cuộc gọi một chức năng gọi là f và sau đó trả về. Vì vậy, không phải tất cả những gì thú vị. F không làm những gì? Chú ý rằng tôi đã không bận tâm với một nguyên mẫu. Tôi muốn giữ mã càng ít càng tốt. Vì vậy, tôi đưa e trên chính và đó là tốt, chắc chắn, cho các chương trình ngắn như thế này. Vì vậy, e không trả lại bất cứ điều gì và làm không mất bất cứ điều gì, nhưng nó không làm điều này. Nó tuyên bố, giống như trong ví dụ Binky, một con trỏ được gọi là x đó là đi để lưu trữ các địa chỉ của một int. Vì vậy, đó là phía bên tay trái. Trong tiếng Anh, là những gì phía bên phải làm gì? Bất cứ ai? Những gì được này làm cho chúng ta? Yeah? Đung [Không nghe thấy] lần kích thước của một int mà là 10 lần [không nghe] DAVID Malan: Tốt và để tôi tóm tắt. Vì vậy, phân bổ không gian đủ cho 10 số nguyên hoặc 10, kích thước của một int là những gì, đó là bốn byte, vì vậy 10 lần 4 là 40, do đó phía bên tay phải tôi đã đánh dấu cho tôi là 40 byte và lưu trữ các địa chỉ của byte đầu tiên vào x. Và bây giờ cuối cùng, và đây là nơi Chương trình này là lỗi, những gì sai với dòng 21 dựa trên logic? Có gì sai với dòng 21? Yeah? Đung Bạn không thể chỉ số vào x [không nghe được]. DAVID Malan: Yeah. Tôi không nên chỉ vào x như thế. Vì vậy, cú pháp, đó là OK. Những gì tốt đẹp là, nhiều như bạn có thể đối xử với tên của một mảng như thể nó là một con trỏ, tương tự bạn có thể đối xử với một con trỏ như thể đó là một mảng, và vì vậy tôi có thể cú pháp nói x khung một cái gì đó, khung x i, nhưng 10 là có vấn đề. Tại sao? Đung Bởi vì nó không phải bên trong. DAVID Malan: Nó không trong đó đoạn bộ nhớ. Giá trị lớn nhất là những gì tôi cần được đặt trong những dấu ngoặc vuông? 9, 0 đến 9. Bởi vì không lập chỉ mục. Vì vậy, 0 đến 9 sẽ là tốt. Bracket 10 là không tốt và nhưng, nhớ lại, mặc dù mỗi lần Tôi dường như cố gắng làm cho CS50 IDE tai nạn bằng cách gõ vào giá trị không có thật, nó không luôn luôn hợp tác, và quả thật, bạn thường nhận được may mắn chỉ vì hệ điều hành không nhận thấy rằng bạn đã bao giờ nên hơi vượt qua một số đoạn bộ nhớ, bởi vì bạn đã ở trong kỹ thuật phân đoạn của mình, nhưng thêm vào đó trong một lớp hệ điều hành, và như vậy một cái gì đó như thế này có thể rất dễ dàng bị phát hiện. Chương trình của bạn sẽ không bao giờ sụp đổ nhất quán nhưng có lẽ một lần trong một thời gian. Và như vậy chúng ta hãy cố gắng valgrind về điều này, và đây là nơi chúng ta sẽ có được lấn át bởi đầu ra trong giây lát. Vì vậy, hãy nhớ kiểm tra rò rỉ valgrind bằng đầy đủ bộ nhớ dấu chấm dấu gạch chéo. Và đây là lý do tại sao tôi hứa điều này sẽ áp đảo. Đây là những gì valgrind, đây là những gì một lập trình, một số năm ago- đã quyết định nó sẽ là một ý tưởng tốt cho sản lượng để trông giống như. Vì vậy, chúng ta hãy làm cho cảm giác này. Vì vậy, tất cả các cách trên trái tay mặt không có lý do tốt là quá trình ID của chương trình chúng ta chỉ cần chạy, các định danh duy nhất cho các chương trình, chúng tôi chỉ cần chạy. Chúng tôi đã xóa mà từ slide, nhưng có là một số thông tin hữu ích ở đây. Hãy di chuyển lên phía trên rất. Đây là nơi chúng tôi bắt đầu. Vì vậy, nó không phải là tất cả mà nhiều đầu ra. Dưới đây là ghi không hợp lệ kích thước 4 trên dòng 21. Vâng, đó là gì dòng 21? Dòng 21 là chính xác này và nó có ý nghĩa rằng tôi đang ở trong một cách hợp lệ viết 4 byte bởi vì tôi cố gắng để đưa số nguyên này, mà có thể là bất cứ điều gì, nó chỉ xảy ra được bằng không, nhưng tôi đang cố gắng để đặt nó ở một vị trí điều đó không thuộc về tôi. Hơn nữa, xuống đây, 40 byte trong một khối chắc chắn bị mất trong kỷ lục 1. Đó là bởi vì khi tôi gọi malloc ở đây, tôi chưa bao giờ thực sự giải phóng bộ nhớ. Vậy làm thế nào chúng ta có thể khắc phục điều này? Hãy để tôi đi trước và có một chút an toàn hơn và làm 9 đó và để cho tôi ở đây miễn phí x. Đây là chức năng mới cho ngày hôm nay. Nếu bây giờ tôi chạy lại làm cho bộ nhớ dấu chấm dấu gạch chéo, chúng ta hãy chạy valgrind vào nó một lần nữa, tối đa hóa cửa sổ của tôi và nhấn Enter. Bây giờ, nó là tốt. Họ chôn những tin tức tốt trong tất cả các đầu ra này. Tất cả các khối đống là miễn phí. Chúng tôi sẽ trở lại với những gì các đống là, nhưng không có rò rỉ đều có thể. Vì vậy, đây chỉ là một công cụ cho bộ công cụ của bạn mà bạn có thể bắt đầu thấy bây giờ lỗi như thế. Nhưng chúng ta hãy xem những gì hơn có thể đi sai ở đây. Hãy chuyển đổi ngay bây giờ để thực sự giải quyết một vấn đề. Là một sang một bên, nếu điều này sẽ làm giảm một chút chút nhầm lẫn hoặc căng thẳng, này là bây giờ buồn cười. Yeah. Đó là khá tốt. Bởi vì con trỏ là địa chỉ và địa chỉ nói chung là theo quy ước bằng văn bản với hệ thập lục phân. Ha, ha, đây là vui bây giờ. Nhưng dù sao, vì vậy chúng ta hiện nay thực sự giải quyết một vấn đề. Điều này đã được siêu, siêu cấp thấp cho đến nay, và chúng tôi thực sự có thể làm hữu ích mọi thứ với những chi tiết ở mức độ thấp. Vì vậy, chúng tôi giới thiệu một vài tuần trước ý niệm về một mảng. Một mảng là tốt đẹp bởi vì thật khó để làm sạch mã của chúng tôi bởi vì nếu chúng ta muốn viết một Chương trình với nhiều sinh viên hoặc nhiều tên và nhà ở và ký túc xá và trường cao đẳng và tất cả điều đó, chúng ta có thể lưu trữ tất cả mọi thứ hơn sạch bên trong của một mảng. Nhưng đề xuất một nhược điểm của một mảng cho đến nay. Thậm chí nếu bạn đã không phải chịu đựng điều đó cho mình trong một chương trình, chỉ theo bản năng, một điều xấu là gì về một mảng, có lẽ? Tôi nghe một số tiếng thì thầm. Đung Thật khó để thay đổi kích thước. DAVID Malan: Thật khó để thay đổi kích thước. Bạn không thể thay đổi kích thước của một mảng, trên thực tế, mỗi gia nhập trong C. Bạn có thể phân bổ một mảng khác, di chuyển tất cả mọi thứ từ một tuổi vào mới, và bây giờ có một số không gian thêm, nhưng nó không giống như một ngôn ngữ như Java hay Python hoặc bất kỳ số khác ngôn ngữ mà một số bạn có thể là quen thuộc nơi bạn chỉ có thể tiếp tục thêm vào những điều nauseam quảng cáo vào cuối mảng. Khi bạn có một mảng của size 6, đó là kích thước của nó, và như vậy giống như ý tưởng trước đó có một bộ đệm của một kích thước nhất định, bạn phải đoán ra khỏi cổng những gì kích thước nào bạn muốn nó được? Nếu bạn đoán quá lớn, bạn đang lãng phí thời gian. Nếu bạn đoán quá nhỏ, bạn không thể lưu trữ dữ liệu đó, ít nhất không có rất nhiều công việc nhiều hơn. Vì vậy, ngày hôm nay, nhờ vào con trỏ, chúng ta có thể bắt đầu ghép nối các tùy chỉnh riêng của chúng tôi cấu trúc dữ liệu, và trong Thực tế, đây là một cái gì đó trông nhiều hơn một chút khó hiểu ở cái nhìn đầu tiên, nhưng đây là những gì chúng ta sẽ gọi một liên kết danh sách, và các loại tên của mình tổng kết nó. Đó là một danh sách các số, hoặc trong trường hợp này, một danh sách các số, nhưng nó có thể là một danh sách của bất cứ điều gì, nhưng nó liên kết với nhau bằng cách mũi tên, và chỉ mất một đoán với những gì kỹ thuật chúng ta sẽ có thể để khâu lại với nhau, loại giống như bỏng ngô với một chủ đề, một danh sách liên kết hình chữ nhật ở đây? Số của nó? Các tính năng ngôn ngữ cơ bản là gì? Đung Một con trỏ. DAVID Malan: Một con trỏ. Vì vậy, mỗi người trong các mũi tên ở đây đại diện một con trỏ hoặc chỉ là một địa chỉ. Vì vậy, nói cách khác, nếu tôi muốn để lưu trữ một danh sách các số, Tôi không thể chỉ lưu nó nếu tôi muốn khả năng phát triển và co cấu trúc dữ liệu của tôi trong một mảng. Vì vậy, tôi cần phải có một chút hơn sự tinh tế, nhưng thông báo rằng điều này picture loại cho thấy rằng nếu bạn đã chỉ cần có chút đề kết nối mọi thứ lại với nhau, có lẽ là không khó để làm cho không gian ở giữa hai trong số những hình chữ nhật hoặc hai trong số những nút, như chúng ta sẽ bắt đầu gọi điện cho họ, đưa vào một nút mới, và sau đó với một số chủ đề mới, chỉ mương ba nút với nhau, người đầu tiên, người cuối cùng, và một trong những mà bạn muốn chèn vào giữa. Và thực sự là một danh sách liên kết, không giống như một mảng, là năng động. Nó có thể phát triển và nó có thể co lại và bạn không phải biết hay quan tâm trước bao nhiều dữ liệu bạn sẽ được lưu trữ, nhưng hóa ra chúng ta có được một chút cẩn thận về cách để thực hiện điều này. Vì vậy, đầu tiên chúng ta hãy xem xét làm thế nào chúng ta thực hiện một trong những hình chữ nhật nhỏ. Thật dễ dàng để thực hiện một int. Bạn chỉ cần nói int n và sau đó bạn nhận được 4 byte cho một int, nhưng làm thế nào để tôi nhận được một int, gọi nó là n, và sau đó một con trỏ, chúng ta hãy gọi nó bên cạnh. Chúng ta có thể gọi đó là các điều bất cứ điều gì chúng ta muốn nhưng tôi cần một cấu trúc dữ liệu tùy chỉnh. Yeah? Đung ký hiệu [không nghe được]. DAVID Malan: Vậy dấu và chúng tôi sẽ sử dụng để lấy địa chỉ của một nút có khả năng. Nhưng chúng ta cần một tính năng của C theo thứ tự để cho tôi khả năng để tạo ra hình chữ nhật tùy chỉnh này, tùy chỉnh này biến nếu bạn sẽ, trong bộ nhớ. Đung A struct. DAVID Malan: Một struct. Nhớ lại từ tuần trước, chúng tôi giới thiệu cấu trúc, từ khóa tương đối đơn giản này cho phép chúng ta làm những điều như thế này. C đã không đến với một dữ liệu cấu trúc được gọi là học sinh. Nó đi kèm với int và float, char và như vậy, nhưng nó không đến với học sinh, nhưng chúng ta có thể tạo ra một kiểu dữ liệu học sinh, một cấu trúc sinh viên, với cú pháp này ở đây. Và bạn sẽ thấy điều này một lần nữa và một lần nữa. Vì vậy, đừng lo lắng về ghi nhớ các từ khóa, nhưng từ khóa mà quan trọng là chỉ thực tế mà chúng tôi đã nói struct và sau đó chúng ta gọi nó là sinh viên và bên trong của học sinh là một cái tên và một ngôi nhà hoặc một ký túc xá hoặc tương tự. Và vì vậy bây giờ ngày hôm nay, chúng ta hãy đề xuất này. Tôi đã thêm một vài từ, nhưng nếu tôi muốn để thực hiện các hình chữ nhật này đó là có cả một int và một con trỏ, bạn biết không, tôi muốn khai báo một cấu trúc được gọi là nút. Tôi cũng, bên trong của nó, sẽ nói rằng một nút, hình chữ nhật này, có một int và chúng tôi sẽ gọi nó là n và nó có một con trỏ tới. Và đây là một chút dài dòng, nhưng nếu bạn nghĩ về nó, các mũi tên đó là trong hình lúc trước là các loại dữ liệu? Nơi mỗi người trong những mũi tên trỏ để loại cấu trúc dữ liệu? Nó không chỉ chỉ để một int mỗi se. Nó chỉ đến toàn bộ điều hình chữ nhật và rằng điều hình chữ nhật, chúng tôi đã nói, được gọi là một nút. Và vì vậy chúng tôi có loại để đệ quy định này như rằng một nút, chúng ta sẽ nói, sẽ chứa một int n và một con trỏ được gọi tới và Loại cấu trúc dữ liệu mà mà con trỏ trỏ là rõ ràng sẽ là nút struct. Vì vậy, đây là annoyingly tiết và chỉ để được gàn dở, lý do tại sao chúng ta không thể chỉ nói điều này, mà thẳng thắn trông rất dễ đọc hơn, là vì nhớ lại rằng C đọc những điều trên xuống dưới, từ trái sang phải. Nó không phải cho đến khi chúng tôi nhận được dấu chấm phẩy mà nút từ khóa thực sự tồn tại. Vì vậy, nếu chúng ta muốn có loại này tài liệu tham khảo có tính chu kỳ trong các dữ liệu cấu trúc, chúng ta phải làm điều này, nơi chúng ta nói struct nút ở phía trên, mà cho chúng ta một con đường dài của mô tả này điều, sau đó bên trong chúng tôi nói struct node, và sau đó ở dòng cuối cùng chúng ta nói, tất cả các quyền, C, bằng cách này, chỉ cần gọi toàn bộ chết tiệt này điều một nút và dừng sử dụng các cấu trúc từ khóa hoàn toàn. Vì vậy, đây chỉ là sắp xếp của một cú pháp trick mà cuối cùng cho phép chúng tôi tạo ra một cái gì đó trông giống hệt như thế này. Vì vậy, nếu chúng ta giả sử bây giờ chúng tôi có thể thực hiện điều này trong C, làm thế nào để chúng tôi thực sự bắt đầu vượt qua điều này? Vâng, trên thực tế, tất cả chúng ta phải làm là lặp từ trái sang phải và chỉ loại chèn các nút hoặc xóa các nút hoặc tìm kiếm những điều bất cứ nơi nào chúng ta muốn, nhưng để làm được điều này, chúng ta hãy đi trước và thực hiện một ít những điều thực tế hơn vì đây đã được siêu cấp thấp cho đến nay. Bất cứ ai có nghĩa là muốn là người đầu tiên? ĐƯỢC. Nào lên. Tên bạn là gì? DAVID: David. DAVID Malan: David. Rất hân hạnh được biết bạn. Tôi cũng thế. Được rồi. Và chúng ta cần một số 9. Không tốt như lần đầu tiên, có lẽ. OK, số 9. Một số 17, xin vui lòng. Hãy để tôi đi lại xa hơn một chút. Số 22, xin vui lòng, và làm thế nào về xa trở lại nếu tôi có thể nhìn thấy bất kỳ tay với tất cả các ánh sáng hay không. Có người bị tình nguyện ngay tại đó. Bạn có muốn đi lên? Cẳng tay của bạn được dùng vũ lực đi lên. OK, 17. 22. 26 đang xuống. Bất cứ ai khác muốn forcefully-- Nào lên. Một tình nguyện viên thực tế. Vì vậy, rất nhanh chóng, nếu các bạn có thể sắp xếp mình chỉ thích các nút trên màn hình. Cam on. Và bạn sẽ có 26. Tất cả các quyền giới thiệu và nhanh chóng. Vì vậy, tôi David và bạn cũng được? DAVID: David. DAVID Malan: Và bạn? Jake: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID Malan: Taylor. Tuyệt vời. Vì vậy, đây là những tình nguyện viên của chúng tôi cho hôm nay và đi trước và thay đổi một chút theo cách đó, và chỉ cần đi trước và giữ giữ số của bạn như bạn đang hoặc của bạn Dấu hiệu đầu tiên và dùng tay trái của bạn, đi trước và chỉ cần thực hiện các mũi tên, chỉ để bàn tay trái của bạn là nghĩa đen chỉ tay vào bất cứ điều gì bạn cần chỉ tại, và cung cấp cho mình một số phòng để chúng tôi trực quan có thể nhìn thấy cánh tay của bạn thực sự trỏ, và bạn chỉ có thể trỏ loại ở mặt đất là tốt. Vì vậy, ở đây chúng tôi có một danh sách liên kết của một, hai, ba, bốn, năm nút ban đầu, và nhận thấy chúng tôi có điều này đặc biệt con trỏ vào đầu người là chính bởi vì chúng ta phải theo dõi của danh sách Toàn bộ chiều dài bằng cách nào đó. Những anh chàng này, mặc dù họ đang trái sang phải, trở lại trở lại trong bộ nhớ, họ thực sự có thể là bất cứ nơi nào trong bộ nhớ của máy tính. Vì vậy, những kẻ có thể là đứng bất cứ nơi nào trên sân khấu và đó là tốt, miễn là chúng thực sự chỉ tay vào nhau, nhưng để giữ cho mọi thứ sạch sẽ và đơn giản, chúng tôi sẽ chỉ vẽ cho họ trái sang phải như này, nhưng có thể có những khoảng trống lớn ở giữa các nút. Bây giờ, nếu tôi muốn thực sự chèn một số giá trị mới, chúng ta hãy đi trước và làm điều này. Chúng tôi có một cơ hội với doanh nghiệp để lựa chọn một nút khác. Nói chúng ta hãy bắt đầu với mallocing 55. Một ai đó sẽ nhớ được malloc? OK, đi lên trên. Tên bạn là gì? RAINBOW: Cầu vồng. DAVID Malan: Cầu vồng? Được rồi. Malloc Rainbow. Nào lên. Vì vậy, bây giờ chúng ta phải tự hỏi mình thuật toán mà chúng ta có thể đặt 55. Vì vậy, tất cả chúng ta biết, rõ ràng, nơi cô có thể thuộc nếu chúng ta đang cố gắng giữ này được sắp xếp và nếu các bạn có thể lấy một lùi lại vì vậy chúng tôi không rơi ra khỏi sân khấu, đó sẽ là tuyệt vời. Vì vậy, trên thực tế, Rainbow, bắt đầu lại ở đây với tôi, bởi vì chúng tôi là các máy tính hiện nay có thể chỉ thấy một biến tại một thời điểm. Vì vậy, nếu điều này là nút đầu tiên. Chú ý ông không phải là một nút, ông chỉ là một con trỏ, và đó là lý do tại sao anh ta rút ra được chỉ có kích thước của một con trỏ, không một trong những hình chữ nhật đầy đủ. Vì vậy, chúng ta sẽ kiểm tra tại mỗi lặp đi lặp lại là 55 ít hơn 9? Không. Là 55 ít hơn 17 tuổi? Không. Ít hơn 22? Ít hơn 26? Ít hơn 34? Và vì vậy bây giờ, rõ ràng Cầu vồng thuộc ở cuối. Vì vậy, để được rõ ràng, và những gì là tên của bạn, Taylor? TAYLOR: Taylor. DAVID Malan: Vậy giữa Taylor tay trái và tay của Rainbow ở đây, tay mà cần để trỏ vào những gì trong đặt hàng để chèn 55 ​​vào danh sách này? Những gì chúng ta cần phải làm gì? Yeah? Đung tay của Taylor cần để trỏ trái. DAVID Malan: Chính xác. Vì vậy, chèn một nút vào cuối danh sách là khá đơn giản bởi vì Taylor chỉ có tới điểm, thay vì ở mặt đất hoặc chúng tôi sẽ gọi nó là null, null là loại sự vắng mặt của một con trỏ hoặc một đặc biệt zero con trỏ, bạn sẽ chỉ có trái của bạn tay tại Rainbow và sau đó Rainbow, nơi nên trái của bạn Mặt lẽ điểm? Down. Nó không tốt nếu tay của cô là loại việc chỉ ra ở đây hoặc loại nào lối nào. Điều đó sẽ được xem xét một giá trị rác, nhưng nếu cô ấy chỉ vào một số giá trị đã biết, chúng tôi sẽ gọi nó là số không hoặc null, đó là OK bởi vì chúng ta có một thuật ngữ trong này và chúng ta biết danh sách các doanh nghiệp được hoàn tất. Vậy có điều gì khác trường hợp tương đối đơn giản? Chúng ta có thể malloc 5? Nào lên. Tên bạn là gì? TIFFANY: Tiffany. DAVID Malan: Tôi xin lỗi? TIFFANY: Tiffany. DAVID Malan: Tiffany. Được rồi. Tiffany đã được malloced với giá trị 5. Nào lên. Điều này là tương đối dễ dàng quá, nhưng chúng ta hãy xem xét thứ tự của hoạt động doanh nghiệp. Nó là khá dễ dàng với Taylor ở cuối. Số 5 là khóa học ít hơn 9, và vì vậy chúng tôi có David, chúng tôi có Tiffany, và tên của bạn là gì? Jake: Jake. DAVID Malan: Jake. Tiffany, Jake và David. Tay của ai cần được cập nhật đầu tiên? Làm những gì bạn muốn làm ở đây? Có một vài cách có thể, nhưng cũng có một hoặc một cách sai lầm hơn. ĐỐI TƯỢNG: Bắt đầu với tận cùng bên trái. DAVID Malan: Bắt đầu với tận cùng bên trái. Ai là người ngoài cùng bên trái ở đây sau đó? Đung tiên. DAVID Malan: OK. Vì vậy, bắt đầu với đầu và nơi làm bạn muốn cập nhật tay David cho được? Đung Hướng tới 5. DAVID Malan: OK. Vì vậy, David, điểm tại năm hoặc Tiffany ở đây, và bây giờ? Đung Tiffany chỉ vào 9? DAVID Malan: Perfect, trừ Binky của đầu chỉ là loại đã ngã xuống, phải không? Bởi vì những gì đang xảy ra với hình ảnh này theo nghĩa đen? Đung Không có gì là trỏ. DAVID Malan: Không có gì là trỏ đến Jake bây giờ. Chúng tôi đã theo nghĩa đen mồ côi 9 và 17, và chúng tôi đã theo nghĩa đen bị rò rỉ tất cả bộ nhớ này, bởi vì theo cập nhật tay David đầu tiên, đó là tốt trong chừng mực nó một cách chính xác chỉ vào Tiffany bây giờ, nhưng nếu không có ai có đủ tầm nhìn xa đến điểm tại Jake, sau đó chúng tôi đã bị mất toàn bộ danh sách đó. Vì vậy, hãy lùi lại. Vì vậy, đó là một điều tốt để vướng chân nhưng chúng ta hãy sửa bây giờ. Chúng ta nên làm gì đầu tiên để thay thế? Yeah? Đung Tiffany nên điểm tại 9? DAVID Malan: Tôi không thể nhận được rằng gần gũi với bạn. Ai nên điểm tại 9? Đung Tiffany. DAVID Malan: Tất cả các quyền. Vì vậy, Tiffany nên điểm đầu tiên tại 9. Vì vậy, Tiffany nên trên giá trị giống hệt nhau để David, trong đó có vẻ dự phòng cho một thời điểm, nhưng đó là tốt bởi vì bây giờ, thứ hai bước, chúng tôi có thể cập nhật tay của David điểm tại Tiffany, và sau đó nếu chúng ta chỉ cần loại sạch mọi thứ lên như thể đây là loại giống như mùa xuân, bây giờ đó là một chèn chính xác. Vì vậy, tuyệt vời. Vì vậy, bây giờ chúng tôi đang gần như ở đó. Hãy chèn một thức giá trị như giá trị 20. Nếu chúng ta có thể malloc một tình nguyện viên cuối cùng? Nào lên. Vì vậy, con này nhiều hơn một chút khéo léo. Nhưng thực sự, các mã chúng tôi viết, mặc dù bằng lời nói, là giống như có một bó nếu điều kiện của doanh nghiệp, phải không? Chúng tôi đã có một điều kiện kiểm tra nếu nó thuộc về ở cuối, có thể là khởi đầu. Chúng tôi cần một số loại vòng lặp để tìm vị trí ở giữa. Vì vậy, hãy làm điều đó với tên của bạn là gì? ERIC: Eric. DAVID Malan: Eric? Eric. Rất hân hạnh được biết bạn. Vì vậy, chúng tôi có 20. Ít hơn năm? Không. Ít hơn chín? Không. Ít hơn 17? Không. ĐƯỢC. Ông thuộc ở đây và Tên của bạn một lần nữa là? SUE: Sue. DAVID Malan: Sue. ALEX: Alex. DAVID Malan: Sue, Alex, và? ERIC: Eric. DAVID Malan: Eric. Có bàn tay cần phải được cập nhật đầu tiên? Đung Eric. ĐƯỢC. Vì vậy, Eric phải chỉ ở đâu? Ở tuổi 22. Tốt. Và bây giờ những gì tiếp theo? Sue sau đó có thể chỉ ở Eric và bây giờ, nếu các bạn chỉ làm cho một số phòng, mà là tốt trực quan, bây giờ chúng tôi đã thực hiện việc chèn. Vì vậy, bây giờ chúng ta hãy xem xét một câu hỏi, nhưng cảm ơn bạn rất nhiều cho các tình nguyện viên của chúng tôi. Thực hiện rất tốt. Bạn có thể giữ những người, nếu bạn muốn. Và chúng tôi có một món quà chia tay đáng yêu nếu mỗi bạn muốn lấy một quả bóng căng thẳng. Hãy để tôi chỉ cần vượt qua này xuống. Vì vậy, các takeaway của việc này là gì? Điều này có vẻ là tuyệt vời trong chừng mực chúng ta có bây giờ giới thiệu một thay thế cho một mảng đó không phải là quá giới hạn tới một mảng của một số kích thước cố định. Họ có thể phát triển năng động. Nhưng giống như chúng ta đã thấy trong tuần quá khứ, chúng ta không bao giờ có được bất cứ điều gì miễn phí, như chắc chắn có một thương mại-off ở đây. Vì vậy, với một bề nổi của một liên kết danh sách, là năng động này? Khả năng này để phát triển và thẳng thắn, chúng tôi đã có thể làm xóa và chúng tôi có thể co lại khi cần thiết. Giá những gì chúng ta đang trả tiền? Hai lần như nhiều không gian, đầu tiên của tất cả. Nếu bạn nhìn vào bức tranh, không còn Tôi lưu trữ một danh sách các số nguyên. Tôi đang lưu trữ một danh sách các số nguyên cộng với con trỏ. Vì vậy, tôi tăng gấp đôi số lượng của không gian. Bây giờ, có lẽ đó không phải là như vậy một việc lớn 4 byte, 8 byte, nhưng nó chắc chắn có thể thêm up cho các tập dữ liệu lớn. Nhược điểm khác là gì? Yeah? Đung Chúng ta phải đi qua chúng một-by-một. DAVID Malan: Yeah. Chúng tôi phải đi qua chúng một-by-một. Bạn biết đấy, chúng tôi đã từ bỏ siêu này tính năng thuận tiện của khung vuông ký hiệu, đúng hơn được gọi là truy cập ngẫu nhiên, đó chúng ta chỉ có thể nhảy đến một yếu tố cá nhân nhưng bây giờ nếu tôi vẫn còn tình nguyện viên của tôi ở đây, nếu tôi muốn tìm số 22, tôi không thể chỉ nhảy đến khung một cái gì đó một cái gì đó. Tôi có xem qua danh sách, nhiều ví dụ như tìm kiếm của chúng tôi một cách tuyến tính, để tìm số 22. Vì vậy, chúng tôi dường như đã phải trả giá đó. Nhưng dù sao chúng ta có thể giải quyết các vấn đề khác. Trong thực tế, để tôi giới thiệu chỉ là một vài hình ảnh. Vì vậy, nếu bạn đã được xuống để Nhà trường Mather mới đây, bạn sẽ nhớ lại rằng họ ngăn xếp của khay như thế này, chúng ta mượn những từ Annenberg trước khi đến lớp. Vì vậy, chồng này của khay, mặc dù, là đại diện thực sự của một cấu trúc dữ liệu khoa học máy tính. Có một cấu trúc dữ liệu khoa học máy tính được biết đến như một chồng mà rất độc đáo vay chính nó để chính xác này trực quan. Vì vậy, nếu mỗi người trong các khay không phải là một khay nhưng cũng giống như một số và tôi muốn để lưu trữ số, tôi có thể đặt một xuống đây, và tôi có thể đặt một xuống đây, và tiếp tục xếp số trên đầu trang của một người khác, và những gì có tiềm năng hữu ích về điều này là hàm ý là những gì cấu trúc dữ liệu này? Mà số tôi có thể kéo ra đầu tiên thuận tiện nhất? Gần đây nhất là một đặt trên đó. Vì vậy, đây là những gì chúng ta sẽ gọi trong khoa học máy tính là một cấu trúc dữ liệu LIFO. Kéo vào, ra đầu tiên. Và chúng ta sẽ thấy lý do tại sao trước khi dài có thể có ích nhưng bây giờ, chỉ xem xét tài sản. Và đó là loại ngu ngốc nếu bạn nghĩ về cách phòng ăn hiện nó. Mỗi lần họ khay sạch và đặt những cái tươi trên đầu trang, bạn có thể có một sạch sẽ trước nhưng cuối cùng rất bẩn và bụi bặm khay ở đáy nếu bạn không bao giờ thực sự được để dưới cùng của mà đống, bởi vì bạn chỉ giữ đặt mới và những người sạch trên đầu trang của nó. Điều tương tự cũng có thể xảy ra trong một siêu thị quá. Nếu bạn có một trường hợp màn hình hiển thị sữa và mỗi khi CVS hoặc bất cứ ai được nhiều sữa hơn, bạn chỉ cần đẩy các loại sữa Bạn đã có để trở lại và bạn đặt những cái mới lên phía trước, bạn sẽ có một số khá khó chịu sữa ở cuối của cấu trúc dữ liệu, bởi vì nó luôn luôn ở phía dưới hoặc tương đương nó luôn luôn ở phía sau. Nhưng có một cách khác để suy nghĩ về xếp dữ liệu và ví dụ, điều này. Nếu bạn là một trong những người thích xếp hàng bên ngoài cửa hàng Apple khi một sản phẩm mới xuất hiện ra, có lẽ bạn đang không sử dụng một ngăn xếp dữ liệu cấu trúc bởi vì bạn sẽ xa lánh mọi người khác là ai xếp hàng để mua một số món đồ chơi mới. Thay vào đó, có lẽ bạn đang sử dụng những loại cấu trúc dữ liệu hoặc những loại hệ thống trong thế giới thực? Hy vọng rằng nó là một đường, hoặc nhiều hơn đúng hay hơn Anh giống như một hàng đợi. Và nó chỉ ra một hàng đợi cũng là một cấu trúc dữ liệu trong khoa học máy tính, nhưng một hàng đợi có rất tài sản khác nhau. Nó không phải LIFO. Kéo vào, ra đầu tiên. Thiên Chúa cấm. Đó là thay vì FIFO. Vào trước ra trước. Và đó là một điều tốt cho công bằng 'sake chắc chắn khi bạn đang xếp hàng up siêu sáng sớm. Nếu bạn nhận được ở đó đầu tiên, bạn muốn nhận ra đầu tiên là tốt. Và vì vậy tất cả những dữ liệu này cấu trúc, hàng đợi và ngăn xếp và chùm của người khác, hóa ra bạn có thể suy nghĩ về điều này như chỉ là một mảng. Đây là một mảng, có thể một kích thước cố định 4, nhưng nó muốn là loại tốt đẹp nếu chúng ta chỉ có thể chồng chất khay gần như vô hạn cao nếu chúng ta có nhiều khay hoặc số. Vì vậy, có lẽ chúng ta muốn sử dụng một danh sách liên kết ở đây, nhưng thương mại-off là có được tiềm năng mà chúng ta cần nhiều bộ nhớ hơn, phải mất một ít thời gian hơn, nhưng chúng tôi không hạn chế chiều cao của ngăn xếp, giống như trường hợp màn hình hiển thị của Mather có thể giới hạn kích thước của ngăn xếp, và vì vậy đây là quyết định thiết kế hoặc tùy chọn có sẵn cho chúng tôi cuối cùng. Vì vậy, với những dữ liệu này cấu trúc, chúng tôi đã bắt đầu nhìn thấy cận trên mới có khả năng về những gì trước đây đã được siêu nhanh và chúng ta sẽ để lại off ngày hôm nay và nơi chúng tôi sẽ hy vọng để có được là vào thứ tư, chúng tôi sẽ bắt đầu nhìn vào một dữ liệu cấu trúc cho phép chúng ta tìm kiếm thông qua các dữ liệu trong thời gian cuối đăng nhập lại. Và chúng ta thấy rằng, nhớ lại, trong tuần zero và một với tìm kiếm nhị phân hoặc phân chia và chinh phục. Nó quay trở lại và tốt hơn nữa, Chén thánh cho trận này sẽ được để đến với các cấu trúc dữ liệu mà chạy thật sự hoặc về mặt lý thuyết trong thời gian liên tục, theo đó nó không quan trọng bao nhiêu hàng triệu hoặc hàng tỉ thứ chúng tôi có trong cấu trúc dữ liệu, nó sẽ đưa chúng ta thời gian liên tục, có thể một bước hoặc hai bước hoặc 10 bước, nhưng con số liên tục của bước để tìm kiếm thông qua cấu trúc dữ liệu. Điều đó thực sự sẽ là Chén thánh nhưng thêm vào đó hôm thứ Tư. Xem ya sau đó. [MUSIC CHƠI]