SPEAKER 1: Được rồi, vì vậy đây là CS50 Đây là phần cuối của tuần năm. Và nhớ rằng thời gian qua chúng tôi bắt đầu nhìn vào các dữ liệu fancier cấu trúc bắt đầu để giải quyết vấn đề, mà bắt đầu giới thiệu những vấn đề mới, nhưng phím này là loại luồng mà chúng ta bắt đầu làm từ nút tới nút. Vì vậy, điều này tất nhiên là một danh sách đơn lẻ liên kết. Và bằng cách đơn lẻ liên kết, Tôi có nghĩa là chỉ một sợi giữa mỗi người trong những nút. Thì ra bạn có thể làm fancier những thứ như danh sách liên kết kép nhờ đó mà bạn có một mũi tên đi theo cả hai hướng, mà có thể giúp đỡ hiệu quả nhất định. Nhưng điều này đã giải quyết được vấn đề? Những vấn đề đã giải quyết này? Tại sao chúng ta quan tâm vào thứ hai? Tại sao, trên lý thuyết, đã làm chúng tôi quan tâm vào thứ hai? Nó làm gì? 

Đung Chúng tôi có thể tự động thay đổi kích thước. 

SPEAKER 1: OK, vì vậy chúng tôi có thể tự động thay đổi kích thước. Thực hiện tốt cả hai bạn. Vì vậy, bạn có thể tự động thay đổi kích thước này cấu trúc dữ liệu, trong khi một mảng, thu hồi, bạn cần phải biết một priori bao nhiêu không gian bạn muốn và nếu bạn cần nhiều hơn một chút không gian, bạn đang loại ra khỏi may mắn. Bạn phải tạo một mảng hoàn toàn mới. Bạn phải di chuyển tất cả các bạn dữ liệu từ một đến khác, cuối cùng giải phóng mảng cũ nếu bạn có thể, và sau đó tiến hành. Mà chỉ cảm thấy rất tốn kém và rất không hiệu quả, và thực sự nó có thể được. Nhưng điều này là không hoàn toàn tốt. Chúng tôi phải trả giá, là một trong những gì của giá rõ ràng hơn chúng tôi thanh toán bằng cách sử dụng một danh sách liên kết? 

Đung Chúng ta phải sử dụng không gian gấp đôi cho mỗi một. SPEAKER 1: Yeah, vì vậy chúng tôi cần ít nhất là hai lần như nhiều không gian. Trong thực tế, tôi nhận ra của hình ảnh này thậm chí là một chút sai lệch, bởi vì trên CS50 IDE trong rất nhiều hiện đại máy vi tính, một con trỏ hoặc địa chỉ không có trong thực tế bốn byte. Nó rất thường những ngày tám byte, mà có nghĩa là phía dưới nhất hình chữ nhật có trong thực tế là loại gấp đôi lớn như những gì tôi đã rút ra, có nghĩa là bạn đang sử dụng ba lần không gian nhiều như chúng ta có thể có cách khác. Bây giờ cùng một lúc, chúng tôi vẫn nói byte, phải không? Chúng tôi không nhất thiết phải nói MB hoặc GB, trừ khi các cấu trúc dữ liệu nhận được lớn. 

Và vì vậy hôm nay chúng tôi bắt đầu xem xét làm thế nào chúng ta có thể khám phá dữ liệu hiệu quả hơn nếu trong thực tế dữ liệu được lớn hơn. Nhưng chúng ta hãy cố gắng canonicalize các hoạt động đầu tiên mà bạn có thể làm trên những các loại cấu trúc dữ liệu. Vì vậy, một cái gì đó giống như một liên kết danh sách thường hỗ trợ hoạt động như xóa, chèn, và tìm kiếm. Và những gì tôi có nghĩa là bằng cách đó? Điều đó chỉ có nghĩa là thường, nếu người đang sử dụng danh sách liên kết, họ hoặc người khác đã thực hiện các chức năng như xóa, chèn, và tìm kiếm, vì vậy bạn có thể thực sự làm một cái gì đó hữu ích với các cấu trúc dữ liệu. Vì vậy, chúng ta hãy có một cái nhìn nhanh chóng làm thế nào chúng ta có thể thực hiện một số mã cho một danh sách liên kết như sau. 

Vì vậy, đây chỉ là một số mã C, thậm chí không phải là một chương trình hoàn chỉnh mà tôi thực sự nhanh chóng đánh lên. Nó không trực tuyến trong việc phân phối mã, bởi vì nó sẽ không thực sự chạy. Nhưng nhận thấy tôi đã chỉ với một bình luận nói, dot dot dot, có điều gì đó có, chấm chấm chấm, một cái gì đó. Và chúng ta chỉ cần nhìn vào những gì các phần ngon ngọt đang có. Vì vậy, trên dòng ba, nhớ lại rằng đây là bây giờ chúng tôi đề xuất tuyên bố một nút cuối cùng thời gian, một trong những đối tượng hình chữ nhật. Nó có một int mà chúng ta sẽ gọi N, nhưng chúng ta có thể gọi nó là bất cứ điều gì, và sau đó một ngôi sao struct nút gọi tiếp theo. Và chỉ để được rõ ràng, thứ hai dòng, trên dòng sáu, đó là những gì? Nó đang làm gì cho chúng ta? Bởi vì chắc chắn nó trông khó hiểu hơn các biến thông thường của chúng tôi. 

Đung Nó làm cho nó di chuyển trên một. 

SPEAKER 1: Nó làm cho nó di chuyển trên một. Và để được chính xác hơn, nó sẽ lưu trữ địa chỉ của nút đó có nghĩa là phải ngữ nghĩa bên cạnh nó, phải không? Vì vậy, nó không phải đi làm nhất thiết phải di chuyển bất cứ điều gì. Nó chỉ đi lưu trữ một giá trị, đó là sẽ là địa chỉ của một số nút khác, và đó là lý do tại sao chúng tôi đã nói struct sao nút, ngôi sao biểu thị một con trỏ hoặc một địa chỉ. OK, vì vậy bây giờ nếu bạn cho rằng chúng ta có N này có sẵn cho chúng ta, và chúng ta hãy giả định rằng người nào khác có chèn một bó toàn bộ các số nguyên vào một danh sách liên kết. Và đó là danh sách liên kết trỏ đến bởi một số điểm một biến gọi là danh sách đó là thông qua tại đây như là một tham số, làm thế nào để tôi đi về dòng 14 thực hiện tìm kiếm? Nói cách khác, nếu tôi đang thực hiện chức năng, mục đích trong cuộc sống là để có một int và sau đó bắt đầu của một danh sách liên kết, đó là một con trỏ trỏ tới các danh sách liên kết. Giống như lần đầu tiên, những người tôi nghĩ David là tình nguyện viên của chúng tôi vào thứ hai, ông đã chỉ tay vào toàn bộ danh sách liên kết, nó như chúng ta đang đi qua David trong như là đối số của chúng tôi ở đây. Làm thế nào để chúng tôi đi về vượt qua danh sách này? Vâng, nó chỉ ra rằng mặc dù con trỏ là tương đối mới bây giờ cho chúng tôi, chúng ta có thể làm điều này tương đối thẳng thắn. 

Tôi sẽ đi trước và khai báo một biến tạm thời mà theo quy ước là chỉ cần đi để được gọi là con trỏ, hoặc PTR, nhưng bạn có thể gọi nó là bất cứ điều gì bạn muốn. Và tôi sẽ phải khởi tạo nó cho sự bắt đầu của danh sách. Vì vậy, bạn có thể loại nghĩ về điều này như tôi những giáo viên khác trong ngày, loại chỉ tay vào một người nào đó trong số người của chúng tôi là tình nguyện viên. Vì vậy, tôi là một biến tạm thời đó là chỉ chỉ tay vào điều tương tự mà chúng tôi tình cờ được đặt tên tình nguyện viên David cũng đã được chỉ ra. Bây giờ trong khi con trỏ là không null, vì thu hồi không cho rằng một số giá trị trọng điểm đặc biệt các demarcates cuối danh sách, như vậy trong khi tôi không chỉ vào mặt đất giống như tình nguyện viên của chúng tôi cuối cùng là, chúng ta hãy đi trước và làm như sau. Nếu pointer-- và bây giờ tôi loại muốn để làm những gì chúng ta đã làm với học sinh structure-- nếu con trỏ chấm tiếp theo equals-- thay, nếu con trỏ dot N bằng bằng các biến N, Lập luận đó là được thông qua tại, sau đó tôi muốn đi trước và nói trở thành sự thật. Tôi đã tìm thấy các số N bên trong một trong các nút của danh sách liên kết của tôi. Nhưng dấu chấm không còn hoạt động trong bối cảnh này, vì con trỏ, PTR, là thực sự là một con trỏ, một địa chỉ, chúng ta có thể thực sự tuyệt vời sử dụng cuối cùng là một mảnh của cú pháp loại đó làm cho cảm giác trực quan và thực tế sử dụng một mũi tên ở đây, có nghĩa là đi từ địa chỉ đó cho các số nguyên có trong. Vì vậy, nó rất giống trong tinh thần cho người điều khiển dot, nhưng vì con trỏ không phải là một con trỏ và không phải là một cấu trúc thực tế bản thân, chúng ta chỉ cần sử dụng các mũi tên. 

Vì vậy, nếu nút hiện tại mà tôi, các biến tạm thời, đang chỉ tay vào không tồn tại, những gì tôi muốn làm gì? Vâng, với những người tình nguyện của tôi mà chúng tôi đã ở đây trong ngày khác, nếu con người đầu tiên của tôi không phải là một trong tôi muốn, và có lẽ những con người thứ hai là không thứ mà mình muốn, và thứ ba, tôi cần phải giữ thể chất di chuyển. Cũng giống như làm thế nào để tôi bước qua một danh sách? Khi chúng tôi đã có một mảng, bạn chỉ cần làm như tôi cộng với cộng với. Nhưng trong trường hợp này, nó cũng đủ để làm con trỏ, được, con trỏ, tiếp theo. Nói cách khác, các trường tiếp theo cũng giống như tất cả các tay trái rằng những người tình nguyện của chúng tôi vào thứ hai đã sử dụng đến điểm tại một số nút khác. Đó là những người hàng xóm tiếp theo của họ. 

Vì vậy, nếu tôi muốn bước qua danh sách này, Tôi không thể chỉ làm tôi cộng với cộng nữa, Tôi thay vì phải nói Tôi, con trỏ, được đi để bằng bất cứ lĩnh vực kế tiếp là, các lĩnh vực tiếp theo là, lĩnh vực tiếp theo là, sau tất cả những bàn tay trái rằng chúng tôi đã có trên sân khấu trỏ để một số giá trị tiếp theo. Và nếu tôi có được thông qua rằng toàn bộ lặp, và cuối cùng, tôi nhấn vô không có N thấy chưa, tôi chỉ trả về false. Vì vậy, một lần nữa, tất cả những gì chúng tôi đang làm ở đây, theo hình ảnh một thời gian trước đây, được bắt đầu bằng cách chỉ vào bắt đầu của danh sách có lẽ. Và sau đó tôi kiểm tra, là giá trị Tôi đang tìm cho bằng chín? Nếu vậy, tôi trở thành sự thật và tôi đang làm. Nếu không, tôi cập nhật tay tôi, AKA con trỏ, trỏ tại vị trí mũi tên bên cạnh, và sau đó vị trí mũi tên tới, và tiếp theo. Tôi chỉ đơn giản là đi bộ qua mảng này. 

Vì vậy, một lần nữa, những người quan tâm? Như thế này là những gì một thành phần? Vâng, nhớ lại rằng chúng tôi giới thiệu khái niệm về một chồng, mà là gõ một dữ liệu trừu tượng trong chừng mực nó không phải là một điều C, nó không phải là một điều CS50, nó là một ý tưởng trừu tượng, ý tưởng này của xếp thứ trên đầu trang của nhau có thể được thực hiện trong chùm cách khác nhau. Và một trong những cách mà chúng tôi đề xuất là có một mảng, hoặc với một danh sách liên kết. Và nó chỉ ra rằng theo giáo luật, một stack hỗ trợ ít nhất hai hoạt động. Và những lời đồn là push, để đẩy một cái gì đó vào ngăn xếp, như một khay mới trong phòng ăn, hoặc pop, có nghĩa là để loại bỏ các topmost Khay từ stack trong ăn uống hội trường, và sau đó có thể một số các hoạt động khác. Vậy làm thế nào chúng ta có thể xác định cấu trúc mà bây giờ chúng tôi đang kêu gọi một chồng? 

Vâng, chúng tôi có tất cả các điều kiện tiên quyết của cú pháp mà chúng ta có trong C. Tôi nói, cho tôi một định nghĩa loại một cấu trúc bên trong của một chồng, Tôi sẽ nói là một mảng, một bó toàn bộ các con số và sau đó kích thước. Vì vậy, nói cách khác, nếu tôi muốn để thực hiện điều này trong mã, hãy để tôi đi và chỉ cần loại rút ra những gì này là nói. Vì vậy, đây là nói, cho tôi một cấu trúc đó là có một mảng, và tôi không biết khả năng là những gì, nó dường như một số hằng số mà tôi đã định nghĩa ở đâu, và đó là tốt. Nhưng giả sử nó chỉ là một, hai, ba, bốn, năm. Vì vậy, công suất là 5. Yếu tố này bên trong của tôi cấu trúc sẽ được gọi là con số. Và sau đó tôi cần một biến khác rõ ràng gọi là kích thước mà ban đầu tôi sẽ để quy định được khởi tạo bằng không. Nếu không có gì trong ngăn xếp, kích thước là số không, và nó là giá trị rác với số lượng. Tôi không có ý tưởng những gì trong đó chỉ được nêu ra. 

Vì vậy, nếu tôi muốn đẩy một cái gì đó vào ngăn xếp, giả sử tôi gọi hàm push, và Tôi nói đẩy 50, như số 50, nơi mà bạn sẽ đề xuất Tôi vẽ nó trong mảng này? Có năm câu trả lời khác nhau có thể. Nơi nào bạn muốn đẩy số 50? Nếu mục tiêu ở đây, một lần nữa, hãy gọi chức năng push, vượt qua trong một cuộc tranh cãi 50, nơi nào tôi đặt nó? Năm possible-- 20% cơ hội đoán một cách chính xác. Có? 

Đung Viễn đúng. 

SPEAKER 1: Far phải. Bây giờ có một cơ hội 25% đoán một cách chính xác. Vì vậy, đó thực sự sẽ được tốt. Theo quy ước, tôi sẽ nói với một mảng, chúng ta thường sẽ bắt đầu từ bên trái, nhưng chúng ta có thể chắc chắn bắt đầu ở bên phải. Vì vậy, các spoiler ở đây sẽ là tôi có lẽ sẽ vẽ nó trên bên trái, giống như trong một mảng bình thường mà Tôi bắt đầu đi từ trái sang phải. Nhưng nếu bạn có thể lật số học, tiền phạt. Nó chỉ là không thông thường. OK, tôi cần phải thực hiện một nhiều thay đổi mặc dù. Bây giờ tôi đã đẩy một cái gì đó vào ngăn xếp, những gì tiếp theo? 

Được rồi, tôi phải tăng kích thước. Vì vậy, hãy để tôi đi trước và chỉ cập nhật này, đó là số không. Và thay vì bây giờ, tôi sẽ để đưa vào một giá trị. Và bây giờ giả sử tôi đẩy khác số vào stack, như 51. Vâng, tôi phải thực hiện thêm một thay đổi, đó là lên đến kích thước hai. Và sau đó giả sử tôi đẩy thêm một số vào stack như 61, bây giờ tôi cần phải cập nhật kích thước thêm một thời gian, và có được giá trị 3 như kích thước. Và bây giờ giả sử tôi gọi pop. Bây giờ bật, theo quy ước, không mất một đối số. Với một chồng, toàn bộ điểm của các ẩn dụ khay là bạn không có quyền tự quyết đi lấy khay đó, tất cả các bạn có thể làm được bật một topmost từ ngăn xếp, chỉ vì. Đó là những gì cấu trúc dữ liệu này không. 

Vì vậy, bằng cách logic rằng nếu tôi nói pop, những gì đi off? Vì vậy, 61. Vì vậy, những gì thực sự là máy tính sẽ làm gì trong bộ nhớ? Những gì hiện mã của tôi phải làm gì? Những gì bạn sẽ đề xuất chúng ta thay đổi trên màn hình? Điều gì cần thay đổi? Xin lỗi? Vì vậy, chúng ta thoát khỏi 61. Vì vậy, tôi chắc chắn có thể làm điều đó. Và tôi có thể thoát khỏi 61. Và sau đó những gì khác thay đổi cần phải xảy ra? Kích thước có lẽ phải trở lại để hai. Và đó là tốt. Nhưng chờ một phút, kích thước một thời điểm cách đây ba tuổi. Hãy làm một kiểm tra sự tỉnh táo nhanh chóng. Làm sao chúng ta biết rằng chúng ta muốn thoát khỏi 61? Bởi vì chúng tôi đang popping. Và vì vậy tôi có kích thước tài sản thứ hai này. 

Chờ một phút, tôi nghĩ lại hai tuần khi chúng tôi bắt đầu nói chuyện về mảng, nơi này là địa điểm không, này là địa điểm duy nhất, đây là vị trí hai, đây là vị trí ba, bốn, nó trông giống như mối quan hệ giữa kích thước và các yếu tố mà tôi muốn loại bỏ từ mảng này dường như chỉ là những gì? Kích trừ đi một. Và đó là cách như con người chúng ta biết 61 đến trước. Làm thế nào của máy tính sẽ biết? Khi mã của bạn, nơi bạn có thể muốn làm kích thước trừ một, như vậy ba trừ đi một là hai, và rằng nghĩa là chúng ta muốn thoát khỏi 61. Và sau đó, chúng tôi thực sự có thể cập nhật kích thước quá cỡ mà bây giờ đi từ ba đến chỉ hai. Và chỉ để được gàn dở, tôi sẽ đề nghị mà tôi đang thực hiện, phải không? Bạn đề nghị trực giác đúng tôi nên thoát khỏi 61. Nhưng có phải tôi loại loại gạt bỏ 61? Tôi đã quên mất hiệu quả rằng nó thực sự ở đó. Và nghĩ lại PSET4, nếu bạn đã đọc các bài viết về pháp y, các PDF rằng chúng tôi đã có các bạn đọc, hoặc bạn sẽ đọc trong tuần này cho PSET4. Nhớ lại rằng đây thực sự Gecman để toàn bộ ý tưởng của pháp y máy tính. Những gì một máy tính thông thường, không có gì nó chỉ là một cái gì đó mà quên là, nhưng nó không đi vào và như cố gắng đầu nó ra hoặc ghi đè các bit với số không và những người thân hoặc một số mẫu ngẫu nhiên khác trừ khi bạn tự mình cố tình làm như vậy. Vì vậy, trực giác của bạn là phải, hãy thoát khỏi 61. Nhưng trong thực tế, chúng ta không cần phải bận tâm. Chúng ta chỉ cần quên rằng nó ở đó bằng cách thay đổi kích thước của chúng tôi. 

Bây giờ có một vấn đề với chồng này. Nếu tôi tiếp tục đẩy mạnh việc vào ngăn xếp, có gì rõ ràng là sẽ xảy ra chỉ trong một thời gian vài phút? Chúng tôi đang đi để chạy ra khỏi không gian. Và chúng ta làm gì? Chúng tôi đang loại hơi say. Việc thực hiện này không cho phép chúng tôi thay đổi kích thước mảng, bởi vì sử dụng cú pháp này, nếu bạn nghĩ lại hai tuần, một khi bạn đã khai báo kích thước của một mảng, chúng tôi đã không nhìn thấy một cơ chế nào đó bạn có thể thay đổi kích thước của mảng. Và thực sự C không có tính năng đó. Nếu bạn nói cho tôi năm Nths, gọi cho họ số, đó là tất cả các bạn đang đi để có được nó. Vì vậy, chúng tôi bây giờ là thứ Hai, có khả năng thể hiện một giải pháp Mặc dù vậy, chúng ta chỉ cần tinh chỉnh định nghĩa của ngăn xếp của chúng tôi để không có một số mảng cứng mã hóa, nhưng chỉ để lưu trữ một địa chỉ. 

Bây giờ tại sao điều này là? Bây giờ chúng ta chỉ cần có để được thoải mái với thực tế là khi chương trình của tôi chạy, Tôi có lẽ sẽ phải yêu cầu nhân lực, bao nhiêu số nào bạn muốn để lưu trữ? Vì vậy, các đầu vào đã đến từ một nơi nào đó. Nhưng một khi tôi biết rằng số lượng, sau đó tôi có thể chỉ sử dụng hàm nào để cung cấp cho tôi một đoạn bộ nhớ? Tôi có thể sử dụng malloc. Và tôi có thể nói bất kỳ số lượng byte tôi muốn trở lại cho những Nths. Và tất cả tôi có để lưu trữ trong các con số biến ở đây bên trong cấu trúc này nên được những gì? Điều gì thực sự đi vào số trong kịch bản này? Yeah, một con trỏ đến đầu tiên byte mà đoạn bộ nhớ, hay cụ thể hơn, địa chỉ của đầu tiên của những byte. Không quan trọng nếu nó là một byte hoặc một tỷ byte, Tôi chỉ cần phải quan tâm đầu tiên. Bởi vì những gì đảm bảo malloc và đảm bảo hệ thống điều hành của tôi, là các đoạn bộ nhớ tôi nhận được, nó sẽ được tiếp giáp. Có sẽ không có những khoảng trống. Vì vậy, nếu tôi đã yêu cầu 50 byte hoặc 1000 byte, họ đang tất cả sẽ được trở lại trở lại để trở lại. Và chừng nào tôi còn nhớ lớn như thế nào, làm thế nào nhiều tôi yêu cầu, tất cả tôi cần biết là địa chỉ đầu tiên như vậy. 

Vì vậy, bây giờ chúng tôi có khả năng trong mã. Mặc dù, nó sẽ đưa chúng ta nhiều thời gian hơn để viết này lên, bây giờ chúng ta có thể tái phân bổ bộ nhớ bởi chỉ lưu trữ một địa chỉ khác nhau ở đó nếu chúng ta muốn có một lớn hơn hoặc thậm chí một đoạn nhỏ hơn của bộ nhớ. Vì vậy, ở đây thành ra thương mại. Bây giờ chúng ta có được tính năng động. Chúng ta vẫn có contiguousness Tôi tuyên bố. Bởi vì malloc sẽ cho chúng ta một đoạn tiếp giáp của bộ nhớ. Nhưng điều này là có được một cơn đau ở cổ cho chúng tôi, các lập trình viên, để thực sự mã lên. Đó là công việc chỉ hơn. Chúng tôi cần có mã giống như những gì tôi đã đập ra chỉ một thời gian trước đây. Rất có thể làm được, nhưng nó thêm phức tạp. Và vì vậy thời gian phát triển, lập trình Hiện vẫn chưa tài nguyên khác rằng chúng ta có thể cần phải chi tiêu một thời gian để có được các tính năng mới. Và sau đó tất nhiên là có một hàng đợi. Chúng tôi sẽ không đi vào này một trong nhiều chi tiết. Nhưng nó rất tinh thần tương tự. Tôi có thể thực hiện một hàng đợi, và hoạt động tương ứng của nó, enqueue hoặc dequeue, như thêm hoặc loại bỏ, nó chỉ là một cách nói fancier của nó, enqueue hoặc dequeue, như sau. Tôi chỉ có thể cung cấp cho bản thân mình một cấu trúc mà lại có mảng của một số, mà lại có một kích thước, nhưng tại sao bây giờ tôi cần để theo dõi phía trước của một hàng đợi? Tôi không cần biết mặt trước của chồng tôi. Vâng, nếu tôi một lần nữa cho một queue-- hãy chỉ cứng mã nó như có như năm số nguyên ở đây có tiềm năng. Vì vậy, đây là số không, một, hai, ba, bốn. Điều này là có được gọi là số một lần nữa. Và điều này sẽ được gọi là kích thước. 

Tại sao nó không đủ để có chỉ là kích thước? Vâng, chúng ta hãy đẩy những con số tương tự trên. Vì vậy, tôi pushed-- tôi enqueued, hoặc bị đẩy. Bây giờ tôi sẽ enqueue 50, và sau đó 51, và sau đó là 61, và đánh dấu chấm chấm chấm. Vì vậy, đó là enqueue. Tôi enqueued 50, sau đó 51, sau đó 61. Và đó trông giống hệt nhau để một chồng cho đến nay, ngoại trừ tôi cần phải thực hiện một sự thay đổi. Tôi cần phải cập nhật kích thước này, vì vậy tôi đi từ số không đến một đến 2-3 giờ. Làm thế nào để dequeue? Điều gì xảy ra với dequeue? Ai nên đi ra khỏi danh sách này đầu tiên nếu đó là dòng tại các cửa hàng của Apple? Vì vậy, 50. Vì vậy, nó là loại phức tạp hơn thời gian này. Trong khi đó, thời gian qua nó đã được siêu dễ dàng chỉ cần làm kích thước trừ một, Tôi có được đến cuối của mảng của tôi có hiệu quả nơi những con số, nó loại bỏ 61. Nhưng tôi không muốn loại bỏ 61. Tôi muốn lấy 50 người đã có tại 05:00 xếp hàng cho iPhone mới hoặc có điều gì. Và do đó, để thoát khỏi 50, tôi không thể chỉ làm điều này, phải không? Tôi có thể vượt ra ngoài 50. Nhưng chúng ta chỉ nói chúng tôi không phải quá hậu môn như để xóa bỏ hoặc ẩn các dữ liệu. Chúng tôi chỉ có thể quên nó ở đâu. 

Nhưng nếu tôi thay đổi kích thước của tôi ngay bây giờ để hai, là đầy đủ thông tin này để biết những gì đang xảy ra trong hàng đợi của tôi? Không hẳn. Giống như kích thước của tôi là hai, nhưng nơi nào hàng đợi bắt đầu, đặc biệt là nếu tôi vẫn còn có những con số tương tự trong bộ nhớ. 50, 51, 61. Vì vậy, tôi cần phải nhớ bây giờ mà phía trước là. Và như vậy, tôi đã đề xuất lên ở đó, chúng ta sẽ vừa gọi Nth phía trước, mà ban đầu giá trị cần phải có được những gì? Zero, chỉ là khởi đầu của danh sách. Nhưng bây giờ ngoài việc giảm các chữ kích thước, chúng tôi chỉ tăng phía trước. Bây giờ đây là một vấn đề khác. Vì vậy, một khi tôi tiếp tục đi. Giả sử đây là số lượng như 121, 124, và sau đó, mẹ kiếp, Tôi ra khỏi không gian. Nhưng chờ một phút, tôi thì không. Vì vậy, tại thời điểm này trong những câu chuyện, giả sử rằng kích thước là một, hai, ba, bốn, vì vậy giả sử rằng kích thước là bốn, phía trước là một, vậy 51 là ở phía trước. Tôi muốn đặt một số khác ở đây, nhưng, mẹ kiếp, tôi ra khỏi không gian. Nhưng tôi không thực sự, phải không? Nơi mà tôi có thể đặt một số giá trị bổ sung, như 171? Chỉ Yeah, tôi có thể loại đi lại ở đó, phải không? Và sau đó gạch bỏ 50, hoặc chỉ ghi đè lên nó bằng 171. Và nếu bạn đang tự hỏi tại sao số của chúng tôi đã rất ngẫu nhiên, này thường được lấy máy tính các khóa học khoa học tại Harvard sau CS50. Nhưng đó là một tối ưu hóa tốt, bởi vì bây giờ tôi sẽ không lãng phí thời gian. Tôi vẫn phải nhớ lớn làm thế nào điều này là tổng số. Đó là tổng số năm. Bởi vì tôi không muốn bắt đầu ghi đè lên 51. Vì vậy, bây giờ tôi vẫn ra ngoài không gian, vì vậy vấn đề tương tự như trước. Nhưng bạn có thể nhìn thấy thế nào bây giờ trong mã của bạn, có thể bạn phải viết nhiều hơn một chút phức tạp để làm cho điều đó xảy ra. Và trên thực tế, những gì điều hành trong C có thể cho phép bạn kỳ diệu làm điều này tuần hoàn? Vâng các nhà điều hành modulo, các ký hiệu phần trăm. Vì vậy, những gì là loại mát mẻ về một hàng đợi, mặc dù chúng tôi giữ mảng vẽ là những đường thẳng như thế, nếu bạn loại suy nghĩ về điều này như cong xung quanh như một vòng tròn, sau đó chỉ cần trực giác nó loại hoạt động tinh thần Tôi nghĩ rằng một chút sạch hơn. Bạn vẫn sẽ phải thực hiện rằng mô hình về tinh thần trong mã. Vì vậy, không phải là khó, cuối cùng, để thực hiện, nhưng chúng tôi vẫn mất size-- đúng hơn, Khả năng thay đổi kích thước, trừ khi chúng ta làm điều này. 

Chúng tôi có để thoát khỏi của mảng, chúng tôi thay thế nó bằng một con trỏ duy nhất, và sau đó một nơi nào đó trong mã của tôi, tôi đã có một gọi hàm nào để thực sự tạo ra các mảng gọi là con số không? Malloc, hoặc một số tương tự chức năng, chính xác. Bất kỳ câu hỏi trên ngăn xếp và hàng đợi. Yeah? Câu hỏi hay. Modulo những gì bạn sẽ sử dụng ở đây. Vì vậy, nói chung, khi sử dụng mod, bạn sẽ làm điều đó với kích thước của toàn bộ cấu trúc dữ liệu. Vì vậy, giống như năm hoặc năng lực, nếu đó là liên tục, có lẽ có liên quan. Nhưng chỉ cần làm theo modulo năm có lẽ là không đủ, bởi vì chúng ta cần phải biết làm chúng tôi quấn quanh ở đây hoặc ở đây hoặc ở đây. Vì vậy, có lẽ bạn đang còn sẽ muốn liên quan kích thước của điều này, hoặc biến phía trước là tốt. Vì vậy, nó chỉ này tương đối biểu thức số học đơn giản, nhưng modulo sẽ là thành phần quan trọng. 

Vì vậy, bộ phim ngắn nếu bạn sẽ. Một hình ảnh động mà một số folks tại trường đại học khác đặt lại với nhau rằng chúng tôi đã thích nghi cho cuộc thảo luận này. Nó liên quan đến Jack học sự thật về hàng đợi và số liệu thống kê. 

FILM: Đã có một thời gian, có một chàng trai tên là Jack. Khi nó đến để làm cho bạn bè, Jack đã không có một sở trường riêng. Vì vậy, Jack đã đến nói chuyện với chàng trai nổi tiếng nhất mà ông biết. Ông đến Lou và hỏi, tôi phải làm gì? Lou đã thấy rằng người bạn của mình đã thực sự đau khổ. Vâng, anh bắt đầu, chỉ nhìn cách ăn mặc nữa. Bạn không có bất kỳ quần áo với một cái nhìn khác nhau? Có, Jack nói. Tôi chắc chắn làm được. Đến nhà tôi và Tôi sẽ cho họ với bạn. Vì vậy, họ đã đi off để Jack. Và Jack thấy Lou hộp nơi ông giữ tất cả áo sơ mi của mình, và quần của mình, và vớ của mình. Lou nói, tôi thấy bạn có tất cả quần áo của bạn trong một đống. Tại sao bạn không mặc một số những người khác lần trong một lúc? 

Jack nói, tốt, khi tôi loại bỏ quần áo và vớ, Tôi rửa cho họ và đưa họ đi vào trong hộp. Sau đó đến tiếp theo buổi sáng, và lên Tôi hop. Tôi đi tới hộp và nhận được quần áo của tôi ra khỏi đầu. Lou nhanh chóng nhận ra các vấn đề với Jack. Ông giữ quần áo, đĩa CD, và sách trong ngăn xếp. Khi anh với một cái gì đó để đọc hoặc để mặc, ông muốn chọn cuốn sách đầu hoặc đồ lót. Sau đó, khi ông đã được thực hiện, ông sẽ đặt nó trở lại ngay. Trở lại nó sẽ đi, trên đỉnh của ngăn xếp. Tôi biết các giải pháp, nói một Loud chiến thắng. Bạn cần phải tìm hiểu để bắt đầu sử dụng một hàng đợi. Lou lấy quần áo của Jack và treo chúng trong tủ quần áo. Và khi ông đã làm trống hộp, anh chỉ ném nó. 

Sau đó, ông nói, bây giờ Jack, vào cuối ngày, mặc quần áo của bạn bên trái khi bạn đưa chúng đi. Sau đó vào ngày mai buổi sáng khi bạn nhìn thấy ánh nắng mặt trời, lấy quần áo của bạn bên phải, từ cuối dòng. Anh không thấy? Lou nói. Nó sẽ được tốt đẹp như vậy. Bạn sẽ mặc tất cả mọi thứ một lần trước khi bạn mặc một cái gì đó hai lần. Và với tất cả mọi thứ trong hàng đợi trong tủ quần áo và kệ của mình, Jack bắt đầu cảm thấy khá chắc chắn của mình. Tất cả là nhờ Lou và hàng đợi tuyệt vời của mình. SPEAKER 1: Đúng rồi, đó là đáng yêu. Vì vậy, những gì đã được thực sự đi trên dưới mui xe bây giờ? Rằng chúng ta có con trỏ, rằng chúng ta có malloc, rằng chúng ta có khả năng để tạo ra khối của bộ nhớ cho mình động. Vì vậy, đây là một hình ảnh chúng tôi thoáng thấy chỉ một ngày khác. Chúng tôi đã không thực sự sống trên đó, nhưng hình ảnh này có được đi vào bên dưới mui xe cho tuần nay. Và do đó, điều này thể hiện, chỉ một hình chữ nhật mà chúng tôi đã rút ra, bộ nhớ máy tính của bạn. Và có thể máy tính của bạn, hoặc CS50 ID, có một gigabyte bộ nhớ hoặc bộ nhớ RAM hoặc hai hoặc bốn gigabyte. Nó không thực sự quan trọng. Hệ thống điều hành của bạn Windows hoặc Mac OS hay Linux, về cơ bản cho phép chương trình của bạn để nghĩ rằng nó đã truy cập đến tính toàn vẹn của bộ nhớ của máy tính, mặc dù bạn có thể chạy nhiều chương trình cùng một lúc. Vì vậy, trong thực tế, điều đó không thực sự làm việc. Nhưng đó là loại một ảo tưởng cho tất cả các chương trình của bạn. Vì vậy, nếu bạn đã có hai hợp đồng biểu diễn của RAM, điều này là làm thế nào các máy tính có thể nghĩ về nó. 

Bây giờ tình cờ, một trong những điều, một trong những phân đoạn của bộ nhớ, được gọi là một chồng. Và thực sự bất cứ lúc nào vậy, đến nay trong văn bản mã mà bạn đã gọi là một chức năng, ví dụ chính. Nhớ lại rằng bất cứ lúc nào tôi đã bộ nhớ rút máy tính, Tôi luôn vẽ loại một nửa của một hình chữ nhật ở đây và không bận tâm nói về những gì ở trên. Bởi vì khi chính được gọi là, tôi yêu cầu bồi thường mà bạn có được mảnh bộ nhớ này mà đi xuống đây. Và nếu chính được gọi là một chức năng như hoán đổi, cũng trao đổi tại đây. Và hóa ra, đó là nơi nó kết thúc. Trên một cái gì đó gọi là một chồng bên trong bộ nhớ của máy tính. Bây giờ vào cuối ngày, đây chỉ là địa chỉ. Nó giống như byte zero, byte một, byte 2 tỷ USD. Nhưng nếu bạn nghĩ về nó như đối tượng hình chữ nhật này, tất cả chúng ta đang làm hàng Hiện chúng tôi gọi một chức năng là layering một lát mới của bộ nhớ. Chúng tôi đem lại cho chức năng đó một lát bộ nhớ riêng của mình để làm việc với. 

Và bây giờ mà nhớ lại này là rất quan trọng. Bởi vì nếu chúng ta có một cái gì đó như hoán đổi và hai biến số địa phương như A và B và chúng ta thay đổi những giá trị từ một đến hai hai và một, thu hồi rằng khi hoán đổi trả, nó giống như miếng này bộ nhớ chỉ được đi. Trong thực tế, nó vẫn còn có forensically. Và có điều gì đó vẫn thực sự ở đó. Nhưng khái niệm, nó như là mặc dù nó hoàn toàn biến mất. Và như vậy chính không biết bất kỳ công việc đã được thực hiện trong đó chức năng trao đổi, trừ khi nó thực sự được thông qua trong những lập luận của con trỏ hoặc tham chiếu. Bây giờ, các giải pháp cơ bản cho rằng vấn đề với swap là đi qua những điều trong theo địa chỉ. Nhưng hóa ra, quá, có chuyện gì được diễn ra trên phần đó của hình chữ nhật tất cả các thời gian này là chưa có nhiều bộ nhớ lên ở đó. Và khi bạn tự động cấp phát bộ nhớ, cho dù đó là bên trong của GetString, mà chúng tôi đã làm cho bạn trong CS50 thư viện, hoặc nếu các bạn gọi malloc và yêu cầu hệ điều hành cho một đoạn bộ nhớ, nó không đến từ stack. Nó đến từ một nơi khác trong bộ nhớ máy tính của bạn đó được gọi là heap. Và đó không phải là bất kỳ khác nhau. Đó là bộ nhớ RAM cùng. Đó là cùng một bộ nhớ. Nó chỉ là RAM đó là lên có thay vì xuống đây. 

Và như vậy có nghĩa là gì? Vâng, nếu máy tính của bạn có một số lượng hữu hạn của bộ nhớ và ngăn xếp được ngày càng tăng lên, vì vậy để nói chuyện, và heap, theo vào mũi tên này, đang phát triển xuống. Nói cách khác, mỗi thời gian bạn gọi malloc, bạn đang được đưa ra một lát bộ nhớ từ trên cao, sau đó có thể là một ít thấp, sau đó một chút thấp hơn, mỗi lần bạn gọi malloc, heap, nó sử dụng, là loại ngày càng tăng, phát triển gần gũi hơn và gần gũi hơn với những gì? Stack. Vì vậy, điều này có vẻ như là một ý tưởng tốt? Tôi có nghĩa là, nơi mà nó không thực sự rõ ràng những gì khác bạn có thể làm gì nếu bạn chỉ có một số lượng hữu hạn của bộ nhớ. Nhưng điều này chắc chắn là xấu. Hai mũi tên ở một sụp đổ nhiên cho nhau. 

Và nó chỉ ra rằng kẻ xấu, folks người đặc biệt tốt với các chương trình, và cố gắng để hack vào máy tính, có thể khai thác thực tế này. Trong thực tế, chúng ta hãy xem xét một ít đoạn trích. Vì vậy, đây là một ví dụ bạn có thể đọc về chi tiết hơn trên Wikipedia. Chúng tôi sẽ chỉ cho bạn tại bài viết nếu tò mò. Nhưng có một cuộc tấn công nói chung được gọi là tràn bộ đệm đã tồn tại cho tới chừng con người có khả năng thao tác bộ nhớ của máy tính, đặc biệt là trong C. Vì vậy, đây là một chương trình rất tuỳ tiện, nhưng chúng ta hãy đọc nó từ dưới lên. Chính vào argc char sao argv. Vì vậy, nó là một chương trình mà mất đối số dòng lệnh. Và tất cả các chính không rõ ràng là cuộc gọi một chức năng, gọi nó là F cho đơn giản. Và nó đi trong những gì? Argv của một. Vì vậy, nó đi vào bất cứ điều gì F từ đó mà người dùng gõ tại dấu nhắc sau khi Tên của chương trình ở tất cả. Vì vậy, nhiều như Caesar hoặc Vigenere, mà bạn có thể gọi lại làm với argv. 

Vì vậy, F là gì? F mất trong một chuỗi là đại diện duy nhất của nó, AKA một ngôi sao char, cùng điều, như một chuỗi. Và nó được gọi là tùy tiện thanh trong ví dụ này. Và sau đó char c 12, chỉ trong điều khoản của layman, char khung c 12 làm cho chúng ta là gì? Của nó làm những gì? Phân bổ bộ nhớ, đặc biệt 12 byte cho 12 ký tự. Chính xác. Và sau đó dòng cuối cùng, khuấy đều và copy, bạn đã có thể không nhìn thấy. Đây là một bản sao chuỗi chức năng, mục đích trong cuộc sống là sao chép đối số thứ hai của mình thành số đầu tiên của mình, nhưng chỉ lên đến một số lượng nhất định các byte. Vì vậy, đối số thứ ba nói, có bao nhiêu byte bạn nên sao chép? Chiều dài của thanh, bất cứ điều gì người dùng gõ vào. Và nội dung của bar, chuỗi, là sao chép vào bộ nhớ chỉ ở tại C. 

Vì vậy, điều này có vẻ ngu ngốc, và nó được. Đó là một ví dụ tạo, nhưng nó đại diện của một lớp học của vectơ tấn công, một cách tấn công của một chương trình. Tất cả là tốt và tốt nếu người dùng loại trong một từ đó là 11 ký tự hoặc ít hơn, cộng với dấu gạch chéo ngược zero. Điều gì nếu người dùng đánh vào hơn 11 hoặc 12, 20 hoặc 50 ký tự? Chương trình này sẽ làm những gì? Lỗi có khả năng seg. Nó sẽ một cách mù quáng sao chép tất cả mọi thứ trong quán bar lên theo chiều dài của nó, đó là nghĩa là tất cả mọi thứ trong quán bar, vào địa chỉ được trỏ C. Nhưng C đã chỉ đánh phủ đưa ra là 12 byte. Nhưng không có kiểm tra bổ sung. Không có nếu điều kiện. Không có kiểm tra lỗi ở đây. 

Và vì vậy những gì chương trình này là sẽ làm là chỉ mù quáng sao chép một điều khác. Và như vậy, nếu chúng ta vẽ này như một bức tranh, đây là chỉ là một mảnh của không gian bộ nhớ. Vì vậy, nhận thấy ở phía dưới, chúng tôi có thanh địa phương biến. Vì vậy mà con trỏ đó là sẽ store-- đúng hơn là lập luận địa phương đó là sẽ lưu thanh chuỗi. Và sau đó thông báo chỉ ở trên nó trong một ngăn xếp, bởi vì mỗi khi bạn hỏi cho bộ nhớ trên stack, nó đi một chút ở trên nó trong những bức tranh, thông báo rằng chúng tôi đã có 12 byte có. Người đầu bên trái là khung C bằng không và người dưới bên phải là khung C 11. Đó chỉ là cách các máy tính sẽ lay nó ra. Vì vậy, chỉ bằng trực giác, nếu thanh có hơn hơn 12 ký tự trong tổng số, bao gồm cả các dấu gạch chéo ngược bằng không, mà là 12 hoặc 12 khung C sẽ đi đâu? Hay đúng hơn, nơi là 12 nhân vật hoặc nhân vật thứ 13, các nhân vật trăm đi để kết thúc trong hình ảnh? Trên hay dưới? 

Đúng, bởi vì mặc dù stack tự mọc lên, một khi bạn đã đưa công cụ trong nó, nó cho lý do thiết kế, đặt vào bộ nhớ từ trên xuống dưới. Vì vậy, nếu bạn đã có hơn 12 byte, bạn sẽ bắt đầu ghi đè lên vạch. Bây giờ đó là một lỗi, nhưng nó không thực sự là một vấn đề lớn. Nhưng nó là một vấn đề lớn, bởi vì có nhiều thứ đang diễn ra trong bộ nhớ. Vì vậy, đây là cách chúng ta có thể đặt hello, để được rõ ràng. Nếu tôi gõ trong hello tại dấu nhắc. H-E-L-L-O backslash không, kết thúc trong vòng những 12 byte, và chúng tôi siêu an toàn. Tất cả đều tốt. Nhưng nếu tôi gõ một cái gì đó dài hơn, có khả năng nó sẽ chui vào không gian bar. Nhưng tệ hơn, nó quay ra tất cả các thời gian này, mặc dù chúng tôi đã không bao giờ nói chuyện về nó, ngăn xếp được sử dụng cho các công cụ khác. Nó không chỉ là biến địa phương. 

C là một ngôn ngữ cấp rất thấp. Và nó loại bí mật sử dụng stack cũng cần nhớ khi một hàm được gọi, những gì địa chỉ là các chức năng trước đây, do đó, nó có thể nhảy trở lại chức năng đó. Vì vậy, khi các cuộc gọi chính trao đổi, trong số những điều đẩy vào stack không chỉ hoán đổi biến địa phương, hoặc đối số của nó, cũng bí mật đẩy vào stack như là đại diện bởi các miếng màu đỏ ở đây, là địa chỉ của chính thể chất trong bộ nhớ của máy tính, để khi trao đổi được thực hiện, máy tính biết tôi cần phải quay trở lại chính và kết thúc thực hiện các chức năng chính. Vì vậy, đây là nguy hiểm bây giờ, bởi vì nếu sử dụng các loại trong tốt hơn hello, như vậy mà đầu vào của người dùng clobbers hoặc ghi đè lên rằng phần màu đỏ, một cách hợp lý nếu máy tính chỉ cần đi một cách mù quáng giả các byte trong đó lát đỏ địa chỉ mà nó phải trả lại, nếu các đối thủ là những gì đủ thông minh hoặc may mắn, đủ để đặt một chuỗi các byte có mà trông giống như một địa chỉ, nhưng đó là địa chỉ của mã rằng anh ta muốn máy tính để thực hiện thay vì chính? 

Nói cách khác, nếu những gì dùng đang gõ tại dấu nhắc, không phải là một cái gì đó chỉ như vô thưởng vô phạt hello, nhưng nó thực sự là mã đó là tương đương để xóa tất cả các tập tin của người dùng này? Hoặc gửi email mật khẩu của họ với tôi? Hoặc bắt đầu đăng nhập của họ tổ hợp phím, phải không? Có một con đường, chúng ta hãy định ngày hôm nay, rằng họ có thể gõ vào không chỉ chào thế giới hoặc tên của họ, họ có thể cơ bản vượt qua trong mã, số không và những người thân, rằng máy tính sai lầm cho cả mã và địa chỉ. Vì vậy, mặc dù hơi trừu tượng, nếu loại dùng trong đủ mã đối địch rằng chúng tôi sẽ khái quát ở đây là A. A là tấn công hay kẻ thù. Vì vậy, những thứ chỉ có hại. Chúng tôi không quan tâm về số hoặc các số không hoặc những người thân ngày hôm nay, như vậy mà bạn kết thúc ghi đè lên rằng phần màu đỏ, nhận thấy rằng chuỗi các byte. O 835 C không tám không. Và bây giờ là bài viết của Wikipedia đây đã đề xuất, nếu bây giờ bạn thực sự bắt đầu ghi nhãn các byte trong máy tính của bạn bộ nhớ, những gì các bài viết Wikipedia là đề xuất là, những gì nếu địa chỉ trong đó byte trên bên trái là 80 C 0 3508. 

Nói cách khác, nếu các chàng xấu là đủ thông minh với mã của mình để thực sự đưa một số ở đây mà tương ứng với địa chỉ của mã anh ta hoặc cô tiêm vào máy tính, bạn có thể lừa máy tính vào làm gì. Loại bỏ các tập tin, gửi email điều, sniffing truy cập của bạn, nghĩa là bất cứ điều gì có thể là tiêm vào máy tính. Và do đó, một lỗi tràn bộ đệm tấn công vào cốt lõi của nó chỉ là một ngu ngốc, ngu ngốc trọng của một mảng không có ranh giới của nó kiểm tra. Và đây là những gì là siêu nguy hiểm và đồng thời siêu mạnh trong C là chúng ta thực sự có truy cập vào bất cứ nơi nào trong bộ nhớ. Nó đến với chúng tôi, các lập trình viên, người viết mã ban đầu để kiểm tra độ dài của bất kỳ darn mảng mà chúng ta đang thao tác. Vì vậy, để được rõ ràng, việc sửa chữa là gì? Nếu chúng ta trở lại này mã, tôi không nên chỉ thay đổi chiều dài của thanh, những gì khác tôi cần được kiểm tra? Còn gì nên làm để ngăn chặn cuộc tấn công này hoàn toàn? Tôi không muốn chỉ là một cách mù quáng nói mà bạn nên sao chép như nhiều byte như là chiều dài của thanh. Tôi muốn nói, sao chép như nhiều byte như là trong quán bar đến phân bổ bộ nhớ, hoặc 12 tối đa. Vì vậy, tôi cần một số loại nếu điều kiện mà không kiểm tra độ dài của thanh, nhưng nếu nó vượt quá 12, chúng tôi chỉ cứng mã 12 là khoảng cách tối đa có thể. Nếu không cái gọi là bộ đệm tấn công tràn bộ có thể xảy ra. Ở dưới cùng của những slide, nếu bạn đang tò mò muốn đọc thêm là bài viết thực tế ban đầu nếu bạn muốn có một cái nhìn. 

Nhưng bây giờ, trong số các giá trả ở đây là không hiệu quả. Vì vậy, đó là một cách nhanh chóng cấp thấp này những gì vấn đề có thể phát sinh bây giờ chúng tôi rằng có quyền truy cập vào bộ nhớ của máy tính. Nhưng một vấn đề khác chúng tôi đã vấp vào thứ Hai chỉ là không hiệu quả của một danh sách liên kết. Chúng tôi đang trở lại với thời gian tuyến tính. Chúng tôi không còn có một mảng kề nhau. Chúng tôi không có quyền truy cập ngẫu nhiên. Chúng tôi không thể sử dụng ký hiệu khung vuông. Chúng tôi theo nghĩa đen có sử dụng một vòng lặp trong khi như một trong tôi đã viết một thời gian trước đây. Nhưng vào thứ hai, chúng tôi cho rằng chúng ta có thể leo trở lại vào lĩnh vực hiệu quả đạt được một cái gì đó logarit có thể, hoặc tốt nhất chưa, thậm chí có một cái gì đó cái gọi là thời gian liên tục. Vậy làm thế nào chúng ta có thể làm điều đó bằng cách sử dụng các mới công cụ, những địa chỉ này, các con trỏ, và luồng điều của riêng của chúng tôi? Vâng, giả sử rằng ở đây, đây là một bó các con số mà chúng ta muốn lưu trữ trong một cấu trúc dữ liệu và tìm kiếm hiệu quả. Chúng tôi hoàn toàn có thể tua tới tuần hai, ném chúng vào một mảng, và tìm kiếm chúng bằng cách sử dụng tìm kiếm nhị phân. Chia và chinh phục. Và trên thực tế bạn đã viết tìm kiếm nhị phân trong PSET3, nơi bạn thực hiện các chương trình find. Nhưng bạn có biết những gì. Có một loại hơn cách thông minh để làm điều này. Đó là nhiều hơn một chút tinh vi và nó có lẽ cho phép chúng ta thấy tại sao nhị phân tìm kiếm là nhanh hơn rất nhiều. Đầu tiên, chúng ta hãy giới thiệu khái niệm về một cái cây. Mà mặc dù trong cây thực tế loại phát triển như thế này, trong thế giới của máy tính khoa học họ loại được kéo dài giống như một cây gia đình, nơi bạn có ông bà của bạn hoặc ông bà lớn hoặc không có điều gì ở phía trên cùng, tộc trưởng và các matriarch của gia đình, chỉ cần một cái gọi là gốc, nút, bên dưới mà là con của nó, dưới đây là con của nó, hoặc con cháu của nó nói chung. Và bất cứ ai treo tắt dưới cùng của gia đình cây, bên cạnh là các út trong gia đình, cũng có thể chỉ là khái quát gọi là lá của cây. 

Vì vậy, đây chỉ là một bó của từ và định nghĩa cho một cái gì đó gọi là cây trong máy tính khoa học, giống như một cây gia đình. Nhưng có thân fancier của cây, một trong số đó được gọi là một cây tìm kiếm nhị phân. Và bạn có thể loại tease ngoài những điều này không có gì. Vâng, đó là nhị phân trong ý nghĩa gì? Trường hợp không nhị phân đến từ đây? Xin lỗi? Nó không quá nhiều một trong hai hoặc. Đó là chi tiết mà mỗi nút có không hơn hai đứa con, như chúng ta thấy ở đây. Nói chung, một tree-- và cha mẹ và ông bà của bạn có thể có nhiều trẻ em hoặc cháu khi họ thực sự muốn, và do đó, ví dụ chúng tôi đã có ba trẻ em ra rằng nút tay phải, nhưng trong một cây nhị phân, một nút có bằng không, một, hoặc hai con tối đa. Và đó là một tài sản tốt đẹp, bởi vì nếu nó bị chặn bởi hai, chúng ta sẽ có thể có được một cơ sở đăng nhập ít hai hành động xảy ra ở đây cuối cùng. Vì vậy, chúng tôi có một cái gì đó logarit. Nhưng thêm vào đó trong một thời điểm. Cây tìm kiếm có nghĩa là những con số sắp xếp như là con trái của giá trị lớn hơn căn. Và con phải của nó là lớn hơn so với gốc. Nói cách khác, nếu bạn có bất kỳ của các nút, các vòng tròn trong ảnh này, và nhìn vào bên trái của nó con và con phải của nó, đầu tiên nên được ít hơn, thứ hai phải lớn hơn. Vì vậy, sự tỉnh táo kiểm tra 55. Nó còn con là 33. Nó ít hơn. 55 tuổi, con phải của nó là 77. Nó lớn hơn. Và đó là một định nghĩa đệ quy. Chúng tôi có thể kiểm tra mỗi một trong những các nút và các mô hình tương tự sẽ giữ. 

Vì vậy, những gì tốt đẹp trong một cây tìm kiếm nhị phân, là một trong đó, chúng ta có thể thực hiện nó với một cấu trúc, chỉ như thế này. Và mặc dù chúng ta đang ném rất nhiều cấu trúc tại của bạn, họ đang hơi trực quan chỉ hy vọng. Cú pháp là vẫn còn phức tạp cho chắc chắn, nhưng nội dung của một nút trong này context-- và chúng tôi giữ sử dụng các nút chữ, cho dù đó là một hình chữ nhật trên màn hình hoặc một vòng tròn, nó chỉ là một số thùng chứa chung chung, trong trường hợp này của một cây, như một trong những chúng ta đã thấy, chúng ta cần một số nguyên trong mỗi nút và sau đó tôi cần hai con trỏ trỏ để con trái và con phải, tương ứng. Vì vậy, đó là làm thế nào chúng ta có thể thực hiện điều đó trong một cấu trúc. Và làm thế nào tôi có thể thực hiện nó trong code? Vâng, chúng ta hãy nhanh chóng nhìn vào ví dụ nhỏ này. Đó không phải là chức năng, nhưng tôi đã sao chép và dán cấu trúc đó. Và nếu chức năng của tôi cho một số nhị phân cây tìm kiếm được gọi là tìm kiếm, và điều này cần hai đối số, một số nguyên N và một con trỏ đến một nút, do đó, một con trỏ đến cây hoặc một con trỏ đến thư mục gốc của một cây, làm thế nào để đi về tìm kiếm cho N? Vâng, đầu tiên, bởi vì tôi là đối phó với con trỏ, Tôi sẽ làm một kiểm tra sự tỉnh táo. Nếu equals cây bằng null, là N trong cây này hay không trong cây này? Nó không thể được, phải không? Nếu tôi qua null, có gì ở đó. Tôi có thể cũng chỉ một cách mù quáng nói trở lại sai. Nếu bạn cung cấp cho tôi không có gì, tôi chắc chắn không thể tìm thấy bất kỳ số N. Vì vậy, những gì khác tôi có thể kiểm tra ngay? Tôi sẽ phải nói cũng khác nếu N là ít hơn so với bất cứ điều gì là tại các nút cây mà tôi đã được trao cho N giá trị. Nói cách khác, nếu số tôi tìm kiếm, N, là ít hơn so với các nút mà tôi đang tìm kiếm tại. Và nút Tôi đang tìm tại được gọi là cây, và nhớ lại từ ví dụ trước để có được ở các giá trị trong một con trỏ, Tôi sử dụng các ký hiệu mũi tên. Vì vậy, nếu N là ít hơn so với cây mũi tên N, tôi muốn khái niệm đi bên trái. Làm thế nào để tôi thể hiện: tìm kiếm này lại? Để được rõ ràng, nếu điều này là hình ảnh trong câu hỏi, và tôi đã được thông qua mà trên cùng mũi tên đó là trỏ xuống. Đó là con trỏ cây của tôi. Tôi chỉ vào thư mục gốc của cây. Và tôi đang tìm tiếng nói, cho số 44, tùy tiện. Là 44 hoặc ít hơn lớn hơn 55 rõ ràng? Vì vậy, nó ít hơn. Và vì vậy điều này nếu điều kiện được áp dụng. Vì vậy, khái niệm, tôi muốn những gì để tìm kiếm tiếp theo nếu tôi đang tìm kiếm 44? Yeah? 

Chính xác, tôi muốn tìm kiếm con trái, hoặc trái cây tiểu của hình ảnh này. Và trên thực tế, cho tôi qua hình ảnh xuống đây chỉ trong một khoảnh khắc, kể từ Tôi không thể làm xước này ra. Nếu tôi bắt đầu ở đây là 55, và Tôi biết rằng giá trị 44 Tôi đang tìm kiếm là để bên trái, đó là loại giống như xé cuốn sách điện thoại trong nửa hoặc rách các cây trong một nửa. Tôi không còn phải quan tâm đến toàn bộ nửa này của cây. Chưa hết, tò mò về các cấu trúc, điều này trên đây mà bắt đầu với 33, mà bản thân là một cây tìm kiếm nhị phân. Tôi nói từ trước bởi vì đệ quy thực sự đây là một cấu trúc dữ liệu theo định nghĩa là đệ quy. Bạn có thể có một cái cây đó là này lớn, nhưng mỗi một trong số các con của nó đại diện cho một cây chỉ nhỏ hơn một chút. Thay vì nó là ông nội hoặc bà ngoại, bây giờ nó chỉ là mẹ or-- tôi không thể say-- không mẹ hoặc cha, đó sẽ là kỳ lạ. Thay vào đó, hai đứa trẻ có sẽ giống như anh trai và anh chị em. Một thế hệ mới của các cây gia đình. Nhưng về mặt cấu trúc, đó là ý tưởng tương tự. Và hóa ra tôi có một chức năng mà tôi có thể tìm kiếm một tìm kiếm nhị phân cây. Nó được gọi là tìm kiếm. Tôi tìm kiếm cho N trong cây mũi tên trái khác nếu N là lớn hơn giá trị mà tôi hiện tại là. 55 trong câu chuyện lúc nãy. Tôi có một chức năng gọi là tìm kiếm mà tôi có thể chỉ vượt qua N này và đệ quy tìm kiếm các cây con và chỉ trở lại bất cứ câu trả lời đó. Khác tôi đã có một số trường hợp cơ sở thức ở đây. 

Các vụ án cuối cùng là gì? Cây hoặc là null. Các giá trị tôi hoặc tìm ít hơn hoặc lớn hơn hoặc bằng nó. Và tôi có thể nói bằng bình đẳng, nhưng một cách hợp lý nó tương đương với chỉ nói nào khác ở đây. Vì vậy, thật sự là cách tôi tìm thấy một cái gì đó. Vì vậy, hy vọng đây là một thậm chí ví dụ hấp dẫn hơn hơn các chức năng sigma ngu ngốc chúng tôi đã làm một vài bài giảng trở lại, nơi mà nó đã được chỉ là dễ dàng để sử dụng một vòng lặp để đếm tất cả các số từ một để N. Ở đây với một cấu trúc dữ liệu mà chính nó là đệ quy định nghĩa đệ quy và rút ra, bây giờ chúng tôi có khả năng thể hiện bản thân trong mã đó chính là đệ quy. Vì vậy, đây là mã chính xác cùng ở đây. 

Vì vậy, những gì các vấn đề khác chúng ta có thể giải quyết? Vì vậy, một bước nhanh khỏi cây chỉ trong một khoảnh khắc. Ở đây là, nói, lá cờ Đức. Và có một cách rõ ràng mô hình để lá cờ này. Và có rất nhiều cờ trong thế giới đó là đơn giản như này về màu sắc và các mẫu của họ. Nhưng giả sử này được lưu giữ như một .GIF, Hoặc JPEG, hoặc bitmap, hoặc một ping, bất kỳ định dạng tập tin đồ họa mà bạn đã quen thuộc, một số trong đó chúng tôi chơi với trong PSET4. Điều này dường như không đáng để lưu trữ điểm ảnh màu đen, điểm ảnh màu đen, điểm ảnh màu đen, dot, dot, dot, một bó toàn bộ pixel màu đen cho scanline đầu tiên, hoặc hàng, sau đó một bó toàn bộ giống nhau, sau đó một bó toàn bộ của nhau, và sau đó một bó toàn bộ các điểm ảnh màu đỏ, điểm ảnh màu đỏ, các điểm ảnh màu đỏ, sau đó toàn bộ bó pixel màu vàng, màu vàng, phải không? 

Có không hiệu quả như vậy ở đây. Làm thế nào bạn trực giác nén cờ Đức nếu thực hiện nó như một tập tin? Giống như những thông tin nào có thể chúng ta không bận tâm lưu trữ trên đĩa để để giảm kích thước tập tin của chúng tôi từ như một megabyte để một kilobyte, một cái gì đó nhỏ hơn? Trong đó nằm trong dự phòng ở đây cần được rõ ràng? Bạn có thể làm gì? Yeah? Chính xác. Tại sao không chứ không phải là nhớ màu sắc của mỗi điểm ảnh darn giống như bạn đang làm trong PSET4 với các định dạng tập tin bitmap, tại sao bạn không chỉ đại diện cho cột ngoài cùng bên trái của điểm ảnh, ví dụ một loạt các điểm ảnh màu đen, một bó màu đỏ, và một loạt các màu vàng, và sau đó chỉ cần bằng cách nào đó mã hóa ý tưởng này lặp lại 100 lần hoặc lặp lại điều này 1.000 lần? Nơi 100 hoặc 1000 là chỉ là một số nguyên, vì vậy bạn có thể nhận được ngay với chỉ một số duy nhất thay vì hàng trăm hoặc hàng ngàn điểm ảnh bổ sung. Và quả thực, đó là cách chúng tôi có thể nén các lá cờ Đức. Và Bây giờ những gì về cờ Pháp? Và một chút một số loại rèn luyện tinh thần, mà cờ có thể được nén nhiều hơn trên đĩa? Cờ Đức hoặc Pháp cờ, nếu chúng ta áp dụng phương pháp đó? Cờ Đức, bởi vì có nhiều sự thừa ngang. Và do thiết kế, nhiều tập tin đồ họa định dạng nào thực sự làm việc như quét đường theo chiều ngang. Họ có thể làm việc theo chiều dọc, chỉ cần nhân loại năm trước đã quyết định rằng chúng ta sẽ thường nghĩ về những điều liên tiếp bởi hàng thay vì cột theo cột. Vì vậy, thực sự nếu bạn là để xem các tập tin kích thước của một lá cờ Đức và Pháp cờ, miễn là độ phân giải là như nhau, có cùng chiều rộng và chiều cao, điều này ở đây là có được lớn hơn, bởi vì bạn phải lặp lại chính mình ba lần. Bạn phải xác định màu xanh, lặp lại chính mình, trắng, lặp lại chính mình, đỏ, lặp lại chính mình. Bạn có thể không chỉ đi tất cả các đường bên phải. Và như một sang một bên, để làm cho xóa nén ở khắp mọi nơi, nếu đây là những bốn khung hình từ một video-- bạn có thể nhớ lại rằng một bộ phim hoặc video nói chung là như 29 hoặc 30 khung hình mỗi giây. Nó giống như một lật cuốn sổ nhỏ, nơi bạn chỉ nhìn thấy hình ảnh, hình ảnh, hình ảnh, hình ảnh, hình ảnh chỉ là siêu nhanh như vậy có vẻ như các diễn viên trên màn hình đang di chuyển. Dưới đây là một con ong bumble trên đỉnh của một bó hoa. Và mặc dù nó có thể là loại khó nhìn thấy ở cái nhìn đầu tiên, điều duy nhất di chuyển trong phim này là những con ong. 

Là gì câm về lưu trữ Video giải nén? Đó là loại chất thải để lưu trữ video như bốn hình ảnh gần như giống hệt nhau chỉ khác nhau trong chừng mực mà các ong. Bạn có thể vứt bỏ nhất thông tin mà và nhớ chỉ, ví dụ, frame đầu tiên và frame cuối cùng, khung hình chính nếu bạn đã bao giờ nghe lời, và chỉ lưu trữ trong giữa, nơi thì ong. Và bạn không cần phải lưu trữ tất cả các màu hồng, và màu xanh, và các xanh lá cây là tốt. Vì vậy, đây là chỉ nói rằng nén là ở khắp mọi nơi. Đó là một kỹ thuật chúng ta thường sử dụng hoặc đưa cho các cấp trong những ngày này. 

Nhưng làm thế nào để bạn nén văn bản? Làm thế nào để bạn đi về nén văn bản? Vâng, mỗi nhân vật trong Ascii là một byte, hoặc tám bit. Và đó là loại ngu ngốc, phải không? Bởi vì bạn có thể gõ A và E và I và O và U rất nhiều thường xuyên hơn như W hoặc Q hoặc Z, tùy thuộc vào ngôn ngữ mà bạn đang viết chắc chắn. Và như vậy tại sao chúng ta sử dụng tám bit cho mỗi lá thư, trong đó có ít nhất chữ nổi, phải không? Tại sao không sử dụng bit ít cho các chữ siêu phổ biến, như E, những điều bạn đoán đầu tiên trong Wheel of Fortune, và sử dụng nhiều bit cho các chữ cái ít phổ biến? Tại sao? Bởi vì chúng tôi chỉ cần đi để sử dụng chúng thường xuyên. 

Vâng, nó chỉ ra rằng có có những nỗ lực thực hiện để làm điều này. Và nếu bạn gọi lại từ lớp trường học hoặc trung học, mã Morse. Mã Morse có dấu chấm và dấu gạch ngang có thể được truyền dọc theo một dây như âm thanh hay tín hiệu của một số loại. Tuy nhiên, mã Morse là một siêu sạch. Đó là một loại hệ thống nhị phân trong rằng bạn có dấu chấm hoặc dấu gạch ngang. Nhưng nếu bạn nhìn thấy, ví dụ, hai chấm. Hoặc nếu bạn suy nghĩ lại về điều hành người đi như tiếng bíp, bíp, bíp, beep, đánh một chút kích hoạt mà truyền một tín hiệu, nếu bạn là người nhận, nhận được hai chấm, những tin nhắn đã nhận bạn? Hoàn toàn tùy ý. 

Tôi? Tôi? Hoặc những gì about-- hay tôi? Có lẽ đó chỉ là hai E phải không? Vì vậy, có vấn đề này của decodability với Morse mã, theo đó, trừ khi người gửi cho bạn thông báo thực sự dừng lại vì vậy bạn có thể sắp xếp của nhìn thấy hoặc nghe thấy những khoảng trống giữa các chữ cái, nó không đủ chỉ để gửi một dòng số không và những người thân, hoặc dấu chấm và dấu gạch ngang, bởi vì có sự không rõ ràng. E là một dấu chấm duy nhất, vì vậy nếu bạn thấy hai chấm hoặc nghe thấy hai chấm, có thể nó là của hai E hoặc có thể nó là một I. Vì vậy, chúng ta cần một hệ thống đó là một ít hơn thông minh hơn. Vì vậy, một người đàn ông tên Huffman năm trước đây đã đưa ra chính xác này. Vì vậy, chúng tôi chỉ cần đi để có một cái nhìn nhanh chóng làm thế nào cây Gecman này. Giả sử rằng đây là một số nhắn ngu ngốc bạn muốn gửi, bao gồm các chỉ A, B, C của D's và E của, nhưng có rất nhiều dự phòng ở đây. Nó không có nghĩa là tiếng Anh. Nó không được mã hóa. Nó chỉ là một thông điệp ngu ngốc với rất nhiều sự lặp lại. Vì vậy, nếu bạn thực sự tính ra tất cả các A, B, C, D, và E của, đây là tần số. 20% của các chữ cái A, 45% thư là của E, và ba tần số khác. Chúng tôi đếm được có tay và chỉ cần làm toán. 

Vì vậy, nó chỉ ra rằng Huffman, một số thời gian trước đây, nhận ra rằng, bạn biết những gì, nếu tôi bắt đầu xây dựng một cây, hoặc rừng cây, nếu bạn muốn, như sau, tôi có thể làm như sau. Tôi sẽ đưa ra một nút cho mỗi của các chữ cái mà tôi quan tâm và tôi sẽ lưu trữ bên trong của nút đó các tần số như là một điểm nổi giá trị, hoặc bạn có thể sử dụng nó một N, quá, nhưng chúng tôi sẽ chỉ sử dụng một float ở đây. Và các thuật toán mà ông đề nghị là bạn mất rừng này của nút duy nhất cây, cây nên siêu ngắn, và bạn bắt đầu kết nối chúng với nhóm mới, cha mẹ mới, nếu bạn sẽ. Và bạn làm điều này bằng cách chọn hai tần số nhỏ nhất tại một thời điểm. Vì vậy, tôi mất 10% và 10%. Tôi tạo ra một nút mới. Và tôi gọi là nút mới 20%. 

Mà hai nút tôi kết hợp tiếp theo? Đó là một chút mơ hồ. Vì vậy, có một số trường hợp góc tới xem xét, nhưng để giữ cho mọi thứ khá, Tôi sẽ chọn 20% - Bây giờ tôi bỏ qua các con. Tôi sẽ chọn 20% và 15% và vẽ hai cạnh mới. Và bây giờ mà hai nút Tôi kết hợp một cách hợp lý? Bỏ qua tất cả các con, tất cả các cháu, chỉ cần nhìn vào các rễ bây giờ. Mà hai nút để tôi gắn kết với nhau? Điểm hai và 0,35. Vì vậy, hãy để tôi vẽ hai cạnh mới. Và sau đó tôi đã chỉ có một trái. Vì vậy, đây là một cây. Và nó được rút ra cố tình để tìm loại khá, nhưng nhận thấy các cạnh có cũng được dán nhãn không và một. Vì vậy, tất cả các cạnh còn lại là số không tùy tiện, nhưng luôn. Tất cả các cạnh bên phải là những người thân. 

Và vì vậy những gì Hoffman đề xuất là, nếu bạn muốn đại diện cho một B, chứ không phải là đại diện cho số 66 là một Ascii mà là tám toàn bộ bit, bạn biết những gì, chỉ cửa hàng mô hình không, không, không, bằng không, bởi vì đó là con đường từ cây của tôi, cây của ông Huffman, để các lá từ gốc. Nếu bạn muốn lưu trữ một E, ngược lại, không gửi tám bit đại diện cho một E. Thay vào đó, hãy gửi những gì mô hình của các bit? One. Và những gì là tốt đẹp về việc này là E rằng là thư phổ biến nhất, và bạn đang sử dụng mã ngắn nhất cho nó. Tiếp theo phổ biến nhất thư có vẻ như nó là A. Và như vậy bao nhiêu bit ông đã đề xuất sử dụng cho điều đó? Zero, một. 

Và bởi vì nó được thực hiện như cây này, cho bây giờ hãy để tôi định có không mơ hồ như trong Morse mã, vì tất cả các chữ mà bạn quan tâm đang ở cuối của các cạnh. Vì vậy, đó chỉ là một ứng dụng của một cái cây. Đây is-- và tôi sẽ sóng Mặt tôi lúc này như thế nào bạn có thể thực hiện điều này như là một cấu trúc C. Chúng tôi chỉ cần kết hợp một biểu tượng, như một char, và tần số ở bên trái và bên phải. Nhưng chúng ta hãy nhìn vào hai ví dụ cuối cùng mà bạn sẽ nhận được khá quen thuộc với sau đố zero trong vấn đề thiết lập năm. 

Vì vậy, có cấu trúc dữ liệu được biết đến như là một bảng băm. Và một bảng băm là loại mát ở chỗ nó có xô. Và giả sử có bốn xô ở đây, chỉ cần bốn không gian trống. Dưới đây là một bộ bài, và đây là câu lạc bộ, thuổng, câu lạc bộ, kim cương, câu lạc bộ, kim cương, câu lạc bộ, kim cương, clubs-- vì vậy đây là sự ngẫu nhiên. Hearts, hearts-- nên tôi bucketizing tất cả các yếu tố đầu vào ở đây. Và một nhu cầu bảng băm nhìn vào đầu vào của bạn, và sau đó đặt nó trong một số đặt dựa trên những gì bạn nhìn thấy. Đó là một thuật toán. Và tôi đã sử dụng một siêu Thuật toán trực quan đơn giản. Phần khó nhất trong số đó là ghi nhớ những gì các bức ảnh đều. Và sau đó có tổng cộng bốn điều. 

Bây giờ các ngăn xếp đã được phát triển, trong đó là một thiết kế điều cố ý ở đây. Nhưng những gì khác tôi có thể làm gì? Vì vậy, thực sự ở đây chúng ta có một bó sách thi học cũ. Giả sử rằng một loạt các tên học sinh ở đây. Dưới đây là một bảng băm lớn hơn. Thay vì bốn xô, Tôi đã, chúng ta hãy nói 26. Và chúng tôi không muốn đi vay 26 những thứ từ bên ngoài [? Annenberg?], Vì vậy đây là năm mà đại diện A đến Z. Và nếu tôi nhìn thấy một học sinh có tên bắt đầu bằng A, Tôi sẽ đưa ông hay đố cô ở đó. Nếu ai đó bắt đầu với C, qua đó, A-- thực sự, không muốn làm điều đó. B đi qua đây. Vì vậy, tôi đã có A và B và C. Và bây giờ đây là một Một học sinh. Nhưng nếu bảng băm này là thực hiện với một mảng, Tôi là loại hơi say vào thời điểm này, phải không? Tôi loại cần phải đặt một nơi nào đó. 

Vì vậy, một cách nào tôi có thể giải quyết điều này là, tất cả đúng, A là bận rộn, B là bận rộn, C là bận rộn. Tôi sẽ đưa anh ta trong D. Vì vậy, tại đầu tiên, tôi phải ngẫu nhiên ngay lập tức truy cập cho mỗi nhóm cho các sinh viên. Nhưng bây giờ nó loại phân cấp vào một cái gì đó tuyến tính, bởi vì nếu tôi muốn tìm kiếm ai đó tên mà bắt đầu bằng A, tôi kiểm tra ở đây. Nhưng nếu điều này không phải là A sinh viên, tôi đang tìm, Tôi có loại để bắt đầu kiểm tra xô, bởi vì những gì tôi đã làm là loại tuyến tính thăm dò cấu trúc dữ liệu. Một cách ngu ngốc nói chỉ cần nhìn cho việc mở cửa đầu tiên có sẵn, và đặt như là một kế hoạch B, có thể nói, hoặc kế hoạch D trong trường hợp này, giá trị tại địa điểm đó để thay thế. Đây chỉ là để nếu bạn đã có 26 địa điểm và không có học sinh với Q tên hoặc Z, hoặc một cái gì đó như rằng, ít nhất bạn đang sử dụng không gian. 

Nhưng chúng tôi đã nhìn thấy nhiều hơn giải pháp thông minh ở đây, phải không? Bạn sẽ làm gì thay vì nếu bạn có một vụ va chạm? Nếu hai người có tên A, những gì sẽ đã là một thông minh hơn hay nhiều hơn giải pháp trực quan hơn là chỉ đưa A trong đó D là vụ phải được? Tại sao tôi không chỉ đi bên ngoài [? Annenberg?], như malloc, một nút khác, đặt nó ở đây, và sau đó đưa rằng Một học sinh ở đây. Vì vậy mà tôi về cơ bản có một số loại của một mảng, hoặc có thể thanh lịch hơn như chúng tôi bắt đầu nhìn thấy một danh sách liên kết. 

Và do đó, một bảng băm là một cấu trúc mà có thể trông giống như thế này, nhưng khéo léo hơn, bạn có một cái gì đó gọi là chaining riêng biệt, theo đó một bảng băm khá đơn giản chỉ là một mảng, mỗi mà các thành phần không phải là một con số, bản thân nó là một danh sách liên kết. Vì vậy mà bạn có thể truy cập siêu nhanh quyết định nơi để băm giá trị của bạn. Giống như với ví dụ thẻ, Tôi đã quyết định siêu nhanh. Hearts tại đây, kim cương tại đây. Tương tự ở đây, A đi đây, D đi đây, đi B ở đây. Vì vậy, siêu nhanh look-up, và nếu bạn xảy ra để chạy vào một trường hợp va chạm mà bạn đã có, hai những người có cùng tên, cũng sau đó bạn chỉ cần bắt đầu liên kết chúng lại với nhau. Và có thể bạn giữ chúng được sắp xếp theo thứ tự abc, có lẽ bạn không. Nhưng ít nhất chúng ta có tính năng động. Vì vậy, một mặt chúng ta có siêu nhanh thời gian liên tục, và loại thời gian tuyến tính tham gia nếu các danh sách liên kết bắt đầu để có được một ít lâu. 

Vì vậy, loại này của một ngớ ngẩn, geeky đùa năm trước. Tại CS50 hack-a-thon, khi học sinh nhận phòng, một số TF hoặc CA mỗi năm nghĩ đó thật buồn cười phải đưa lên một dấu hiệu như thế này, mà nó chỉ có nghĩa là nếu tên của bạn bắt đầu với một A, đi theo con đường này. Nếu tên của bạn bắt đầu với B, đi this-- OK, đó thật buồn cười có lẽ sau này trong các học kỳ. Nhưng có một cách làm này, quá. Hãy trở lại đó. 

Vì vậy, có cấu trúc này. Và điều này là cuối cùng của chúng tôi cấu trúc cho ngày hôm nay, mà là một cái gì đó gọi là một Trie. T-R-I-E, mà vì một lý do là ngắn để thu hồi, nhưng nó được gọi là Trie. Vì vậy, một Trie là một thú vị hỗn hợp của rất nhiều những ý tưởng này. Đó là một cái cây, mà chúng tôi đã nhìn thấy trước. Nó không phải là một cây tìm kiếm nhị phân. Đó là một cây với bất kỳ số lượng trẻ em, nhưng mỗi trẻ em trong một Trie là một mảng. Một loạt các kích cỡ, nói, 26 hoặc có thể 27 nếu bạn muốn hỗ trợ tên có dấu nối hoặc dấu nháy trong tên của người dân. 

Và vì vậy đây là một cấu trúc dữ liệu. Và nếu bạn nhìn từ đầu xuống dưới, giống như nếu bạn nhìn vào các nút trên cùng ở đó, M, là trỏ đến tận cùng bên trái có điều, mà sau đó A, X, W, E, L, L. Đây là chỉ là một cấu trúc dữ liệu mà tùy tiện là lưu trữ tên của người dân. Và Maxwell được lưu trữ bởi chỉ sau một con đường của mảng vào mảng vào mảng. Nhưng điều tuyệt vời về một Trie là rằng, trong khi một danh sách liên kết và thậm chí một mảng, là tốt nhất mà chúng tôi từng nhận được là thời gian tuyến tính logarit hoặc thời gian tìm kiếm ai đó lên. Trong cấu trúc dữ liệu này của một Trie, nếu cấu trúc dữ liệu của tôi có một tên trong nó và tôi đang tìm Maxwell, tôi sẽ tìm thấy anh ta khá nhanh chóng. Tôi chỉ cần nhìn cho M-A-X-W-E-L-L. Nếu cấu trúc dữ liệu này, ngược lại, nếu N là một triệu, nếu có một triệu tên trong cấu trúc dữ liệu này, Maxwell vẫn sẽ được phát hiện chỉ sau M-A-X-W-E-L-L bước. Và David-- D-A-V-I-D bước. Nói cách khác, bằng cách xây dựng một cấu trúc dữ liệu đó đã nhận tất cả các mảng, tất cả đều mình hỗ trợ truy cập ngẫu nhiên, Tôi có thể bắt đầu nhìn lên của nhân dân đặt tên bằng cách sử dụng một số lượng thời gian đó là tỷ lệ thuận với số lượng không của sự vật trong các cấu trúc dữ liệu, giống như một triệu tên hiện có. Lượng thời gian cần tôi để tìm M-A-X-W-E-L-L trong cấu trúc dữ liệu này là tỷ lệ chưa đến kích thước của cấu trúc dữ liệu, nhưng với chiều dài của tên. Và thực tế các tên mà chúng ta đang nhìn lên sẽ không bao giờ được điên dài. Có lẽ ai đó có một nhân vật 10 tên, 20 tên nhân vật. Đó chắc chắn là hữu hạn, phải không? Có một con người trên trái đất người có tên dài nhất có thể, nhưng tên đó là một hằng số chiều dài giá trị, phải không? Nó không thay đổi trong bất kỳ ý nghĩa. Vì vậy, theo cách này, chúng tôi đã đạt được một cấu trúc dữ liệu đó là thời gian liên tục nhìn lên. Nó có một số bước tùy thuộc vào độ dài của đầu vào, nhưng không phải là số lượng các tên trong cấu trúc dữ liệu. Vì vậy, nếu chúng ta tăng gấp đôi số lượng tên năm tiếp theo từ một tỷ đến hai tỷ đồng, Phát hiện Maxwell là sẽ mất con số chính xác cùng của bảy bước để tìm thấy anh ta. Và như vậy chúng ta dường như đã đạt được Chén thánh của chúng ta về thời gian chạy. 

Vì vậy, một vài thông báo nhanh chóng. Đố zero là đến. Thêm vào đó trên trang web của khóa học trong vài ngày tới. Thứ hai của lecture-- đó là một kỳ nghỉ ở đây tại Harvard vào thứ hai. Nó không phải ở New Haven, vì vậy chúng tôi đang dùng các lớp New Haven cho bài giảng hôm thứ Hai. Tất cả mọi thứ sẽ được quay và truyền trực tiếp như bình thường, nhưng chúng ta hãy kết thúc ngày hôm nay với một clip 30 giây gọi là "Suy nghĩ sâu" bởi Daven Farnham, mà lấy cảm hứng từ năm ngoái vào thứ Bảy "Suy nghĩ sâu" Night Live của Jack Handy, mà bây giờ nên có ý nghĩa. 

FILM: Và bây giờ, "Deep Suy nghĩ "của Daven Farnham. Bảng băm. 

SPEAKER 1: Đúng rồi, đó là nó cho bây giờ. Chúng tôi sẽ gặp bạn vào tuần tới. 

DOUG: Để nhìn thấy nó trong hành động. Vì vậy, chúng ta hãy nhìn vào đó ngay bây giờ. Vì vậy, ở đây, chúng tôi có một mảng được phân loại. 

IAN: Doug, bạn có thể đi trước và khởi động lại này chỉ cho một thứ hai, xin vui lòng. Tất cả các quyền, máy ảnh đang lăn, vì vậy hành động bất cứ khi nào bạn đã sẵn sàng, Doug, OK? DOUG: Được rồi, vì vậy những gì chúng tôi có ở đây là một mảng được phân loại. Và tôi đã có màu tất cả các yếu tố màu đỏ để chỉ ra rằng đó là, trên thực tế, không được phân loại. Vì vậy, nhớ lại rằng điều đầu tiên chúng tôi làm là chúng tôi sắp xếp một nửa còn lại của mảng. Sau đó, chúng tôi sắp xếp quyền một nửa của mảng. Và ya-da, ya-da, ya-da, chúng tôi kết hợp chúng lại với nhau. Và chúng tôi có một mảng hoàn toàn được sắp xếp. Vì vậy, đó là cách hợp nhất phân loại hoạt động. 

IAN: Whoa, whoa, whoa, cắt, cắt, cắt, cắt. Doug, bạn không thể chỉ ya-da, ya-da, ya-da, theo cách của bạn thông qua sắp xếp hợp nhất. 

DOUG: Tôi chỉ cần làm. Tốt rồi. Chúng tôi đang tốt để đi. Hãy chỉ giữ cán. Vậy thì, 

IAN: Bạn phải giải thích nó đầy đủ hơn đó. Đó chỉ là không đủ. DOUG: Ian, chúng tôi không cần phải quay trở lại một. Tốt rồi. Vì vậy, dù sao, nếu chúng ta tiếp tục với merge-- Ian, chúng ta đang ở giữa tiến trình quay phim. 

IAN: Tôi biết. Và chúng ta không thể chỉ ya-da, ya-da, ya-da, thông qua toàn bộ quá trình. Bạn phải giải thích như thế nào Hai bên nhận sáp nhập với nhau. 

DOUG: Nhưng chúng tôi đã đã giải thích làm thế nào hai sides-- 

IAN: Bạn vừa thể hiện họ một mảng kết hợp. DOUG: Họ biết quá trình này. Họ ổn. Chúng tôi đã đi qua nó mười lần. 

IAN: Bạn chỉ cần bỏ qua ngay trên nó. Chúng ta sẽ trở lại một, bạn không có thể bạn ya-da, ya-da trên nó. Được rồi, trở lại một. 

DOUG: Tôi phải quay trở lại qua tất cả các slide? Chúa tôi. Nó giống như là lần thứ sáu, Ian. Tốt rồi. 

IAN: Tất cả các quyền. Bạn sẵn sàng chưa? Tuyệt vời. Hành động.