DAVID Malan: Được rồi. Chào mừng trở lại CS50. Đây là khởi đầu của tuần 8. Và nhớ lại rằng vấn đề bộ 5 đã kết thúc với một chút của một thách thức. Vì vậy, giả sử bạn phục hồi tất cả các bạn nghiên cứu sinh giảng dạy và hình ảnh của CA trong tập tin card.raw, bạn có đủ điều kiện Cho đến nay tất cả những người này, và một chiến thắng may mắn sẽ đi bộ về nhà với một những điều này, chuyển động bước nhảy vọt thiết bị mà bạn có thể sử dụng cho thức dự án, ví dụ. 

Này, mỗi năm, dẫn đến một chút creepiness. Và vì vậy những gì tôi nghĩ rằng tôi muốn làm là chia sẻ với bạn một số các ghi chú có đi lại trên danh sách nhân viên cuối năm. Ví dụ, chỉ đêm qua, báo giá unquote, từ một trong những nhân viên các thành viên, "Tôi chỉ có một tiếng gõ sinh viên cửa nhà tôi để chụp ảnh với tôi. Stalker, tôi nói với bạn. "Bắt đầu ra khá mô tả và sau đó chúng tôi chuyển vào, một giờ hoặc lâu sau, "Tôi đã có một sinh viên chờ đợi cho tôi sau khi phần và ông ta đã có tên và hình ảnh của chúng tôi trên một số tờ giấy. "Được rồi. Vì vậy, tổ chức, nhưng không tất cả những gì đáng sợ chưa. 

Sau đó, "Tôi đã ra khỏi thành phố vào cuối tuần này, và khi tôi trở lại, đã có một trong của tôi phòng ngủ. "[Cười] DAVID Malan: quote tiếp từ một nhân viên thành viên ", một sinh viên đến nhà tôi tại Somerville lúc 4:00 sáng nay. "Tiếp nhân viên, "Tôi đã đến khách sạn của tôi ở San Francisco và một sinh viên đã được chờ đợi tôi ở hành lang với ba máy DSLR. " Loại máy ảnh. "Tôi thậm chí không vào nhân viên trong học kỳ này, nhưng một sinh viên xông vào nhà tôi này buổi sáng và ghi lại toàn bộ điều với Google Glass. "Và rồi cuối cùng, "Ít nhất 12 người đã háo hức chờ tôi khi tôi bước ra khỏi của tôi đưa đón, và sau đó tôi tỉnh dậy. "Được rồi. Vì vậy, một trong những hình ảnh, như bạn có thể nhớ lại, là đồng này đây, những người bạn có thể biết như Milo Chuối, sống với Lauren Carvalho, người đứng đầu của chúng tôi giảng dạy viên. Milo, Milo, đến đây cậu bé. Milo. Milo. Tâm trí bạn, anh mặc Google Glass, vì vậy chúng tôi sẽ cho bạn thấy tất cả điều này sau. Vì vậy, đây là Milo nếu bạn muốn chụp một bức ảnh với anh ta sau đó. Nếu bạn muốn để tìm cho ra vào khán giả ở đó. OK. Đó là cảnh quay tốt. Vâng, Milo chuối. Oh, không làm điều đó. 

[Cười] 

OK. Vì vậy, một từ sau đó trên những gì nằm phía trước, bởi vì như chúng ta bắt đầu quá trình chuyển đổi, tuần này cụ thể, từ C trong một môi trường dòng lệnh để PHP và JavaScript và SQL và HTML và CSS trong một môi trường dựa trên web, chúng tôi sẽ trang bị cho bạn với tất cả các kiến thức nhiều hơn cho dự án cuối cùng tiềm năng. Hướng tới mục tiêu đó, khóa học có truyền thống của tổ chức hội thảo mà là về các chủ đề tiếp tuyến cho khóa học. Rất nhiều liên quan đến lập trình và phát triển ứng dụng và vv, nhưng không nhất thiết phải khám phá bởi giáo trình riêng của khóa học. 

Vì vậy, nếu bạn có thể quan tâm trong một hoặc nhiều hơn các cuộc hội thảo năm nay, đăng ký tại cs50.net/seminar. Có các cuộc hội thảo lớn tuổi tại cs50.net/seminars. Và vào danh sách vậy, đến nay trong năm nay là ứng dụng web tuyệt vời với Ruby on Đường ray, đó là một sự thay thế ngôn ngữ PHP. Ngôn ngữ học tính toán. Giới thiệu về iOS, đó là nền tảng được sử dụng cho iPhone và phát triển iPad. JavaScript cho Web Apps, chúng tôi sẽ giới thiệu đó, nhưng trong buổi hội thảo này, bạn sẽ đi vào chi tiết hơn. 

Nhảy chuyển động, vì vậy chúng tôi sẽ thực sự có một số bạn bè của chúng tôi từ Leap Motion, các công ty riêng của mình, chúng tôi tham gia. Ngày mai, trên thực tế, để cung cấp một thực hành hội thảo, nếu quan tâm đến bạn. Meteor.js, một kỹ thuật thay thế cho không sử dụng JavaScript trong trình duyệt, nhưng trên một máy chủ. Node.js, mà là rất nhiều trong tĩnh mạch đó là tốt. Thiết kế kiểu dáng đẹp Android. Android là một lựa chọn rất phổ biến iOS và Windows Phone và các nền tảng di động khác. Và Web Security đăng nhập Quốc phòng. 

Vì vậy, trong thực tế, nếu bạn muốn tham gia trong này, chúng tôi làm cho lưu ý về điều này. Chúng tôi rất vui khi nói rằng bạn bè của chúng tôi tại Leap Chuyển động, đó là một khởi động - thiết bị này thực sự chỉ đến ra cách đây vài tháng - đã ân cần tặng 30 thiết bị như vậy đến lớp cho càng nhiều học sinh, nếu bạn muốn mượn phần cứng hướng tới kết thúc học kỳ và sử dụng nó cho một dự án cuối cùng thực tế. Họ hỗ trợ một số ngôn ngữ. Ai trong số họ C, không ai trong số họ PHP, do đó nhận ra một hoặc nhiều các cuộc hội thảo có thể chứng minh quan tâm. Và tất cả chúng sẽ được quay trong trường hợp bạn không thể tham dự trong người. Lịch trình được công bố thông qua email như chúng ta củng cố phòng. 

Và cuối cùng, nếu bạn đi đến projects.cs.50.net, đây là một trang web chúng tôi duy trì mỗi năm mà chúng tôi mời folks từ cộng đồng, giảng viên, các phòng ban, nhân viên, và cả hai trong một bên ngoài của CS50 để đề xuất ý tưởng dự án. Những điều quan tâm đến các nhóm sinh viên. Những điều quan tâm cho các phòng ban. Do đó, biến đó nếu bạn đang gặp khó khăn với sự không chắc chắn về những gì bạn mình muốn để giải quyết. 

Vì vậy, thời gian qua, chúng tôi đã giới thiệu cho là cấu trúc dữ liệu phức tạp hơn chúng tôi nhìn thấy trong tuần qua. Chúng tôi đã sử dụng các mảng khá hạnh phúc như một hữu ích nếu cấu trúc dữ liệu đơn giản. Sau đó, chúng tôi giới thiệu này, mà tất nhiên là danh sách liên kết. Và những gì là một trong những động lực cho giới thiệu cấu trúc dữ liệu này? Yeah? Đó là những gì? 

ĐỐI TƯỢNG: kích thước động. 

DAVID Malan: kích thước động. Vì vậy, trong khi ở mảng, bạn phải biết kích thước của nó trước khi bạn phân bổ nó. Trong danh sách liên kết, bạn không phải biết điều đó. Bạn có thể chỉ malloc, hay rộng hơn, phân bổ thêm nút, có thể nói, bất cứ lúc nào bạn muốn chèn dữ liệu hơn. Và nút đã không được xác định trước ý nghĩa. Nó chỉ là một thuật ngữ chung mô tả một số loại container chúng tôi sử dụng trong cấu trúc dữ liệu của chúng tôi để lưu trữ một số mặt hàng quan tâm, mà trong này trường hợp xảy ra là các số nguyên. 

Nhưng luôn có một sự cân bằng. Vì vậy chúng tôi có được kích thước năng động của các dữ liệu cấu trúc, nhưng những gì chúng tôi phải trả giá? Các nhược điểm của danh sách liên kết là gì? Yeah? 

ĐỐI TƯỢNG: Yêu cầu bộ nhớ hơn. 

DAVID Malan: Nó đòi hỏi hơn bộ nhớ, làm thế nào chính xác? 

ĐỐI TƯỢNG: [nghe được]. 

DAVID Malan: Chính xác. Vì vậy, bây giờ chúng tôi đã gợi ý đi lên bộ nhớ bổ sung mà chúng tôi trước đây không cần, bởi vì lợi thế của một mảng, tất nhiên, là tất cả mọi thứ là liên tục, trở lại để sao để trở lại, mà cung cấp cho bạn truy cập ngẫu nhiên. Bởi vì chỉ bằng cách sử dụng khung vuông ký hiệu, hoặc kỹ thuật hơn con trỏ số học, bổ sung rất đơn giản, bạn có thể truy cập bất kỳ các yếu tố trong thời gian liên tục. Và trong thực tế, đó là loại ám chỉ khác giá mà chúng ta đang phải trả với một danh sách liên kết. 

Điều gì xảy ra thời gian chạy của một cái gì đó như tìm kiếm, nếu tôi muốn tìm thấy một số giá trị và bên trong của một danh sách liên kết? Không thời gian chạy của tôi trở thành những gì? O lớn của n. Nếu nó được sắp xếp để? Nếu cấu trúc dữ liệu được sắp xếp? Tôi có thể làm tốt hơn so với lớn O của n để tìm kiếm? Không, bởi vì trong trường hợp xấu nhất nó có thể rất tốt được sắp xếp, nhưng số lượng bạn đang tìm kiếm có thể là lớn. Nó có thể là số 100, có thể xảy ra được tất cả cách ở cuối. Và bởi vì bạn chỉ có thể truy cập vào một liên kết danh sách trong thực hiện điều này bằng cách cách của nút đầu tiên, bạn vẫn còn loại ra khỏi may mắn. Bạn phải đi qua toàn bộ điều từ đầu đến cuối để tìm ra có giá trị lớn như 100. Hoặc để xác định xem nó thậm chí không có. 

Vì vậy, chúng tôi không thể làm những gì thuật toán trong một dữ liệu cấu trúc trông như thế này? Chúng ta không thể thực hiện tìm kiếm nhị phân, vì tìm kiếm nhị phân cần thiết mà chúng tôi đã truy cập ngẫu nhiên. Chúng tôi chỉ có thể nhảy từ vị trí đến vị trí mà không cần phải theo những mẩu bánh mì trong các hình thức của tất cả các con trỏ. 

Bây giờ, làm thế nào chúng ta thực hiện điều này? Vâng, nếu chúng ta đi vào màn hình ở đây, nếu chúng ta có thể nhanh chóng reimplement dữ liệu này cấu trúc - chữ viết tay của tôi không phải là tất cả những gì tuyệt vời ở đây, nhưng chúng tôi sẽ cố gắng. Vì vậy, cấu trúc typedef, và những gì đã làm tôi muốn gọi điều này ở đây? Nút. Vì vậy, tôi sẽ nhận được chúng tôi bắt đầu. Và bây giờ, những gì cần phải được bên trong cấu trúc dữ liệu cho rằng đơn lẻ danh sách liên kết? Làm thế nào nhiều lĩnh vực? 

Vì vậy, hai. Một là khá dễ dàng. Vì vậy, int n. Và chúng ta có thể gọi bất cứ điều gì n chúng ta muốn, nhưng nó phải là một int nếu chúng ta thực hiện một danh sách liên kết cho số nguyên. Và bây giờ những gì hiện thứ hai lĩnh vực có được? Struct node *. Vì vậy, nếu tôi làm cấu trúc nút *, và sau đó tôi có thể gọi này cũng bất cứ điều gì tôi muốn, nhưng chỉ để được rõ ràng tôi sẽ gọi nó bên cạnh, như chúng tôi đã làm. Và sau đó tôi sẽ đóng dấu ngoặc nhọn của tôi. 

Và bây giờ, như thời gian qua, Tôi đặt nút xuống đây. Nhưng nếu tôi tuyên bố này như một nút, tại sao tôi bận tâm được như vậy tiết ở đây trong tuyên bố cấu trúc nút * tiếp theo, như trái ngược chỉ nút * tiếp theo? Yeah? 

ĐỐI TƯỢNG: [nghe được]. 

DAVID Malan: Chính xác. Chính xác. Bởi vì C thực sự sẽ đưa bạn theo nghĩa đen và chỉ nhìn thấy định nghĩa của nút đường xuống đây, bạn có thể không đề cập đến nó ở đây. Vì vậy, chúng tôi có loại này ưu tiên khai ở đây, đó là thừa nhận chi tiết hơn. Cấu trúc nút, điều đó có nghĩa bây giờ chúng tôi có thể truy cập bên trong các cấu trúc dữ liệu. 

Và như một sang một bên, bởi vì đây là trở thành một chút chủ quan hơn bây giờ, ngôi sao về mặt kỹ thuật có thể đi đây, nó có thể đi đây, nó có thể thậm chí đi ở giữa. Chúng tôi đã được thông qua, trong hướng dẫn phong cách cho quá trình, quy ước đặt ngôi sao ngay bên cạnh các dữ liệu loại, mà trong trường hợp này, sẽ là nút cấu trúc. Nhưng nhận ra trong rất nhiều sách giáo khoa và tài liệu tham khảo trực tuyến, bạn có thể thực sự nhìn thấy nó ở phía bên kia. Nhưng chỉ nhận ra rằng cả hai sẽ thực sự làm việc và bạn chỉ cần có phù hợp. 

Được rồi. Vì vậy, đó là tuyên bố của chúng tôi của nút cấu trúc. Nhưng sau đó chúng tôi bắt đầu làm nhiều hơn những chuyện phức tạp. Ví dụ, chúng tôi quyết định giới thiệu một cái gì đó giống như một bảng băm. Vì vậy, đây là một bảng băm kích thước n, lập chỉ mục từ 0 phía trên bên trái để n trừ 1 trên dưới cùng bên trái. Điều này có thể là một băm bảng cho bất cứ điều gì. Nhưng những gì các loại điều đã làm chúng tôi nói chuyện về việc sử dụng một bảng băm cho? Lưu trữ những gì? 

Tên. Chúng ta có thể làm những cái tên như chúng tôi đã làm thời gian qua. Và thực sự, bạn có thể lưu trữ bất cứ điều gì. Và chúng ta sẽ thấy điều này một lần nữa trong PHP và JavaScript. Một bảng băm là một loại tốt đẹp của Thụy Sĩ Quân đội dao cho phép bạn lưu trữ khá nhiều bất cứ điều gì bạn muốn bên trong nó bằng cách kết hợp các phím với các giá trị. Phím với các giá trị. 

Bây giờ trong trường hợp này đơn giản, chúng tôi phím chỉ là con số. Chúng tôi đang thực hiện một băm bảng như là một mảng. Và như vậy các phím 0, 1, 2, và vv. Và vì vậy chúng tôi, như con người, quyết định cuối cùng tuần bạn biết những gì, nếu chúng ta sẽ tên cửa hàng, chúng ta hãy chỉ tùy tiện, nhưng khá hợp lý, giả định rằng Alice, một tên A, sẽ chỉ được lập chỉ mục vào 0. Và Bob, một tên B, sẽ được lập chỉ mục vào 1, và vv. Vì vậy, chúng tôi đã có một ánh xạ giữa đầu vào, đó là chuỗi, và băm địa điểm, đó là những con số. 

Vì vậy, quá trình đó thường được gọi là một hàm băm, và bạn có thể thực sự thực hiện nó trong mã. Nếu tôi muốn thực hiện một hàm băm thực hiện chính xác những gì chúng tôi vừa mô tả từ thời gian qua, tôi có thể khai báo một hàm mà có, như đầu vào ví dụ - và chúng ta hãy làm điều này trên này màn hình trên đây. Nếu tôi muốn thực hiện một băm chức năng, tôi có thể nói một cái gì đó như thế này. 

Nó sẽ trả lại một int. Nó sẽ được gọi là băm, và nó sẽ chấp nhận như là một đối một chuỗi, hoặc chúng ta có thể thích hợp hơn bây giờ, và nói char *, chúng tôi sẽ gọi nó là s. Và sau đó tất cả các chức năng này đã làm, cuối cùng, được trả lại một int. Bây giờ, làm thế nào nó mà có thể không thể rõ ràng. Tôi sẽ thực hiện điều này mà không cần bất kỳ hình thành kiểm tra lỗi ngay bây giờ. Tôi chỉ cần đi một cách mù quáng nói, trở về bất cứ điều gì là s khung 0, trừ, hãy nói, vốn Một dấu chấm phẩy. 

Hoàn toàn bị phá vỡ. Nó không phải là hoàn hảo bởi vì một, những gì nếu s là vô giá trị? Những điều xấu sẽ xảy ra. Hai, nếu chữ cái đầu tiên trong này tên không phải là một bức thư vốn? Điều đó sẽ không biến hiện tốt một trong hai. Nó có thể là một chữ thường hoặc không phải là một thư nào cả. Vì vậy, hoàn toàn phòng để cải thiện đây, nhưng đây là ý tưởng cơ bản. 

Những gì chúng tôi mô tả tuần trước bằng lời nói như chỉ là một quá trình lập bản đồ Alice 0 và Bob tới 1 có thể được thể hiện chắc chắn formulaically hơn như là một C hoạt động ở đây. Gọi lại băm, phải mất một chuỗi như đầu vào, và sau đó bằng cách nào đó làm điều gì đó với đầu vào để sản xuất một đầu ra. Không giống như mô tả hộp đen của chúng tôi mà chúng tôi đã thực hiện lâu. Tôi không biết làm thế nào điều này có thể làm việc bên dưới mui xe. 

Cho bộ vấn đề 6, một trong những thách thức là để bạn có thể quyết định những gì hàm băm của bạn sẽ được? Những gì sẽ là bên trong đó màu đen hộp, và có lẽ, nó sẽ là một nhiều hơn một chút thú vị hơn này, và chắc chắn dễ bị lỗi kiểm tra hơn đặc biệt này thực hiện. 

Nhưng vấn đề có thể phát sinh, phải không? Nếu chúng ta có một cấu trúc dữ liệu như thế này một, là những gì một trong những vấn đề bạn có thể chạy vào theo thời gian khi bạn chèn ngày càng có nhiều tên vào bảng băm? Bạn nhận được va chạm, phải không? Nếu bạn có Alice và Aaron, hai người có tên đã xảy ra để bắt đầu với A? Đó đặt ra câu hỏi, nơi bạn đặt thứ hai như một tên? 

Vâng, bạn có thể ngây thơ chỉ cần đặt nó nơi Bob thuộc, nhưng sau đó Bob là loại hơi say nếu bạn cố gắng chèn tên của mình bên cạnh và không có chỗ cho anh ta. Vì vậy, bạn có thể đặt Bob nơi Charlie, và bạn có thể tưởng tượng này rất nhanh chóng phân cấp vào một chút của một mớ hỗn độn. Một cái gì đó tuyến tính cuối cùng, nơi bạn chỉ cần tìm kiếm trên toàn bộ điều tìm kiếm Alice hay Bob hoặc Aaron hoặc Charlie. 

Vì vậy, thay vào đó chúng tôi đề xuất, thay vì chỉ tuyến tính thăm dò cho các không gian mở và nhúng cả những cái tên đó, chúng tôi đề xuất một phương pháp tiếp cận fancier. Một bảng băm thực hiện vẫn có một mảng của các chỉ số, nhưng các loại dữ liệu những chỉ số bây giờ là con trỏ. Con trỏ đến những gì? Con trỏ đến danh sách liên kết. 

Vì nói lại là một danh sách liên kết là thực sự chỉ là một con trỏ tới một nút, và nút có một lĩnh vực tiếp theo, và nút đó có một lĩnh vực tiếp theo, và vv. Vì vậy, bây giờ bạn có thể nghĩ đến mảng này trên phía bên tay trái của một bảng băm như dẫn đến một danh sách liên kết. Ưu điểm của nó là nếu bạn nhận được một va chạm giữa Alice và Aaron, bạn sẽ làm gì với thứ hai người như thế? Bạn chỉ cần đính kèm anh ta hoặc cô đến kết thúc, hoặc thậm chí đầu trong đó danh sách liên kết. 

Và thực sự, chúng ta hãy chỉ ăn liền thông qua đó chỉ là một thứ hai. Mà sẽ làm cho ý nghĩa nhất? Nếu tôi đưa Alice và cô ấy kết thúc tại vị trí đầu tiên, sau đó tôi cố gắng chèn tên A-rôn, và có rõ ràng là một vụ va chạm, tôi nên đặt ông ngay từ đầu của danh sách liên kết? Đó là ở vị trí đầu tiên, hoặc ở cuối? 

ĐỐI TƯỢNG: [nghe được]. 

DAVID Malan: OK. Tôi nghe nói bắt đầu. Tại sao ngay từ đầu? 

ĐỐI TƯỢNG: [nghe được]. 

DAVID Malan: OK. Đó là chữ cái, vì vậy đó là tốt đẹp. Đó là một tài sản tốt. Nó sẽ tiết kiệm cho tôi một số thời gian có khả năng. Nó sẽ không cho phép tôi làm tìm kiếm nhị phân, nhưng tôi có thể ít nhất có thể để thoát ra khỏi của một vòng lặp nếu tôi nhận ra, tốt, tôi là cách qua là Aaron sẽ là trong này sắp xếp danh sách liên kết. Tôi không cần phải lãng phí thời gian của tôi đang tìm tất cả các cách để kết thúc. Vì vậy, đó là hợp lý. Tại sao khác bạn có thể chèn tên va chạm vào đầu danh sách? Đó là những gì? 

ĐỐI TƯỢNG: [nghe được]. 

DAVID Malan: Nó có thể mất một thời gian dài để đến cuối danh sách. Và trong thực tế, lâu hơn và lâu hơn. Tên hơn bạn chèn mà bắt đầu với A, dài hơn dây chuyền là sẽ nhận được. Dài mà liên kết danh sách sẽ nhận được. Vì vậy, bạn thực sự chỉ lãng phí thời gian của bạn. Có lẽ bạn nên duy trì thời điểm chèn liên tục, lớn O 1, bằng cách luôn đặt tên va chạm tại đầu của danh sách liên kết, và không đáng lo ngại như nhiều về phân loại. 

Câu trả lời tốt nhất là gì? Nó không rõ ràng. Nó loại phụ thuộc vào những gì phân phối là, những gì mô hình là trong những cái tên bạn đang chèn. Nó không nhất thiết một câu trả lời rõ ràng. Nhưng đây để, một lần nữa, là một cơ hội thiết kế. 

Vì vậy, sau đó chúng tôi nhìn vào điều này, thực sự là cơ hội lớn khác cho p-bộ 6. Và nhận ra, nếu bạn chưa có, Zamyla lặn vào cả hai, băm bảng và cố gắng, chi tiết hơn. Và hương video nhúng trong trang thiết lập thông số. Đây là một Trie - T-R-tôi-E. Và những gì là thú vị về này là thời gian chạy tìm kiếm một tên, như Maxwell thời gian qua, là O lớn của những gì? Đó là những gì? 

ĐỐI TƯỢNG: Số lượng các chữ cái. 

DAVID Malan: Số chữ cái. Tôi nghe nói hai điều. Số chữ cái và thời gian liên tục. Vì vậy, hãy đi với điều đó đầu tiên. Số lượng các chữ cái. Vâng, cấu trúc dữ liệu này, thu hồi, là như một cái cây, một cây gia đình, mỗi các nút mà được tạo thành mảng. Và những mảng là con trỏ đến các nút khác như vậy, hay như vậy khác mảng trong cây. 

Vì vậy, nếu chúng tôi muốn để sau đó xác định dù Maxwell là ở đây, tôi có thể đi đến các mảng đầu tiên, ở phần trên của cây, cái gọi là gốc, đầu các Trie, và sau đó theo con trỏ m, sau đó là một con trỏ, sau đó x, w, e, l, l. Và sau đó khi tôi nhìn thấy một số biểu tượng đặc biệt, ký hiệu ở đây như một hình tam giác. Trong mã bạn sẽ thấy chúng tôi đề nghị bạn thực hiện như một bool, chỉ nói có hoặc không, một từ dừng lại ở đây. 

Vâng, một khi chúng tôi đã đi đến M-A-X-W-E-L-L, cảm thấy như bảy, có thể tám nếu chúng ta đi một quá khứ nó, tám bước sau để tìm Maxwell. Hoặc hãy gọi nó là K. Nhưng nhớ lại cuối cùng thời gian, tôi cho rằng nếu có thực tế chiều dài tối đa trên một từ, như nhân vật 40-một số lẻ, một tối đa chiều dài hàm ý một giá trị không đổi. Vì vậy, thực sự, có, đó là O kỹ thuật lớn 8 hoặc 7, hoặc O thực sự lớn của K. Tuy nhiên, nếu có một giới hạn hữu hạn về những gì K có thể được, đó là một hằng số. Và vì vậy nó lớn O của 1 tại vào cuối ngày. 

Không trong thế giới thực. Không khi bạn thực sự bắt đầu xem đồng hồ của bạn như chạy chương trình của bạn. Nó hoàn toàn sẽ là một chút chậm hơn so với thực sự không đổi thời gian với một bước. Nó sẽ là bảy hay tám bước, nhưng vẫn còn đó là nhiều, nhiều hơn hơn một thuật toán như O lớn của n mà phụ thuộc vào kích thước của những gì trong cấu trúc dữ liệu. 

Nhận thấy xu hướng tăng giá ở đây là chúng ta có thể chèn hơn một triệu tên thành này cấu trúc dữ liệu, nhưng có bao nhiêu bước nữa là nó sẽ đưa chúng ta đến tìm Maxwell trong trường hợp đó? Không. Anh ấy không bị ảnh hưởng. Và cho đến nay, tôi không nghĩ rằng chúng tôi đã nhìn thấy một ví dụ về một cấu trúc dữ liệu hoặc một thuật toán đó là hoàn toàn không bị ảnh hưởng bởi bên ngoài hành vi như thế. Nhưng điều này không thể là tuyệt vời. Điều này không thể là giải pháp duy nhất cho p-bộ 

Và nó không phải. Điều này không nhất thiết phải là dữ liệu cấu trúc, bạn nên hút đến, vì như bảng băm, sự cân bằng. Giá mà bạn phải trả ở đây là gì? Bộ nhớ. Ý tôi là, đây là một tồi tệ số lượng bộ nhớ. Và bạn không thể hoàn toàn thấy nó ở đây vì tác giả của bức ảnh này rõ ràng là cắt ngắn tất cả các mảng, và chúng tôi không nhìn thấy rất nhiều A và Của B và C và Q và Y và Z trong các mảng. Nhưng họ đang có. 

Mỗi một nút đó là một mảng toàn bộ của một số 26 hoặc nhiều byte, mỗi đại diện cho một thư. 27 trong trường hợp của chúng tôi, để chúng tôi có thể hỗ trợ dấu nháy trong bộ vấn đề. Vì vậy, cấu trúc dữ liệu này thực sự là, thực sự dày đặc và rộng. Và rằng một mình có thể kết thúc chậm điều xuống, hoặc ít nhất là chi phí cho bạn rất nhiều không gian. Nhưng một lần nữa, chúng ta có thể rút ra so sánh ở đây. 

Nhớ lại một khi trở lại, chúng ta đạt được nhiều thời gian hoạt động thú vị hơn trong sắp xếp khi chúng tôi sử dụng kết hợp phân loại, nhưng giá chúng tôi trả tiền để đạt được n đăng nhập n cho hợp nhất loại yêu cầu mà chúng tôi dành hơn những gì tài nguyên? Nhiều không gian hơn. Chúng tôi cần một mảng thứ sao chép vào người, giống như chúng tôi đã làm ở đây trên sân khấu. Vì vậy, một lần nữa, không có người chiến thắng rõ ràng, nhưng chỉ thiết kế chủ quan các quyết định được thực hiện. 

Được rồi. Vậy làm thế nào về điều này? Bất cứ ai cũng nhận ra D-Hall? OK. Vì vậy, ba chúng tôi làm. Mather nhà. Vì vậy, đây là cho ăn uống Mather của. Tôi sẽ đặt cược tất cả các nhà ăn có ngăn xếp các khay như thế này. Và điều này thực sự là đại diện của một cái gì đó chúng tôi đã rõ ràng là nhìn thấy rồi. Chúng tôi gọi nó theo nghĩa đen một chồng. Và ngăn xếp, trong điều khoản của bạn bộ nhớ của máy tính, là nơi mà dữ liệu đi trong khi chức năng đang được gọi. 

Ví dụ, những loại điều đi trên stack đối với với bố trí nhớ chúng tôi đã thảo luận trong tuần qua? Đó là những gì? 

ĐỐI TƯỢNG: Các cuộc gọi đến các chức năng. 

DAVID Malan: Tôi xin lỗi. 

ĐỐI TƯỢNG: Các cuộc gọi đến các chức năng. 

DAVID Malan: Các cuộc gọi đến chức năng, nhưng đặc biệt, bên trong của mỗi của những gì những khung? Những loại việc này? Vâng. Vì vậy, các biến địa phương. Bất cứ lúc nào chúng tôi cần một số lưu trữ địa phương, như một tham số, hay int tôi, hay int tạm thời, hoặc bất cứ địa phương biến được, chúng tôi đã đặt rằng trên stack. Và chúng tôi gọi nó là một chồng vì của ý tưởng không giới hạn. Chỉ cần loại trận đấu với thực tế, các khái niệm đó. 

Nhưng nó chỉ ra rằng một chồng cũng có thể được xem như là một cấu trúc dữ liệu, một thay thế cho một mảng, một sự thay thế một danh sách liên kết. Một cái gì đó khái niệm thú vị hơn mà vẫn có thể được thực hiện bằng cách sử dụng một trong những người điều, nhưng đó là một loại khác nhau của cấu trúc dữ liệu hỗ trợ, thực sự, chỉ có hai hoạt động. Nhưng bạn có thể thêm vào fancier tính năng hơn thế nữa. Nhưng đây là những điều cơ bản - đẩy và pop. 

Và ý tưởng với một chồng là nếu tôi có đây, có hoặc không có Annenberg biết, một khay từ bên cạnh với số 9 trên nó. Vì vậy chỉ cần một int. Và tôi muốn đẩy này vào dữ liệu cấu trúc, mà chưa có hàng. Xem xét việc này dưới cùng của ngăn xếp. Tôi sẽ đẩy con số này lên 9 ngăn xếp, và bây giờ nó phải có. 

Nhưng điều thú vị về một chồng là nếu bây giờ tôi muốn đẩy một số giá trị khác, như 17, và tôi đẩy này vào ngăn xếp, tôi sẽ làm điều trực quan duy nhất, tôi chỉ cần đi để đặt nó bên phải, nơi con người chúng ta sẽ được nghiêng để đặt nó, trên đầu trang. Nhưng điều thú vị tại là, làm thế nào để tôi nhận được ở 9? Bạn biết đấy, tôi không phải không có một số nỗ lực. 

Vì vậy, những gì là thú vị về một chồng là do thiết kế, đó là một cấu trúc dữ liệu LIFO. Cách ngớ ngẩn của mô tả cuối cùng, đầu ra. Vì vậy, con số cuối cùng trong tại thời điểm này là 17. Vì vậy, nếu tôi muốn một cái gì đó để bật tắt của chồng, nó chỉ có thể là 17. Vì vậy, có một trật tự bắt buộc hoạt động ở đây, nơi mà mục cuối cùng trong có phải là một trong những đầu tiên. Do đó các từ viết tắt, LIFO. 

Vì vậy, tại sao điều này có thể có ích? Là bối cảnh của họ, trong đó bạn sẽ muốn có một cấu trúc dữ liệu như thế này? Vâng, nó chắc chắn là hữu ích bên trong máy tính. Hệ thống hoạt động như vậy sử dụng rõ ràng này loại cấu trúc dữ liệu cho ngăn xếp. Chúng tôi cũng sẽ thấy cùng một ý tưởng khi nói đến các trang web. Vì vậy, trong tuần này và tuần tới và xa hơn nữa, và khi bạn bắt đầu thực hiện web trang trong một ngôn ngữ được gọi là HTML, bạn có thể thực sự sử dụng một cấu trúc dữ liệu như này để xác định xem trang là định dạng đúng. Bởi vì chúng ta sẽ thấy tất cả các trang web theo một loại hệ thống phân cấp, xẹp sẽ, vào cuối ngày, là một cơ cấu cây bên dưới mui xe. Vì vậy, thêm vào đó trong chỉ là một chút. 

Nhưng bây giờ, chúng ta hãy đề nghị cho một thời điểm, làm thế nào chúng ta có thể đi về đại diện cho những gì một chồng là? Hãy để tôi đề nghị chúng ta thực hiện một chồng với mã như thế này. Vì vậy, một chồng là sẽ có bên trong của nó hai điều, một mảng, được gọi là khay, chỉ để phù hợp với các bản demo. Và mỗi mục trong mảng là có được một kiểu int. Và năng lực có lẽ là những gì? Bởi vì tôi đã không viết những đầy đủ định nghĩa ở đây. 

Đó có lẽ là tối đa kích thước của mảng. Và nó có thể khai báo là một sắc nét xác định ở trên cùng của các tập tin, một số loại liên tục như ngụ ý của chỉ giá trị vốn hóa. Vì vậy, ở đâu đó công suất được xác định như kích thước tối đa có thể. Trong khi đó, bên trong các cấu trúc dữ liệu được biết đến như một chồng có sẽ là một số nguyên chỉ được biết đến đơn giản là kích thước. 

Vì vậy, nếu tôi được đại diện này ngay bây giờ những bức tranh, chúng ta hãy giả sử rằng điều này hộp đen toàn bộ đại diện cho chồng tôi. Bên trong của nó là hai biến. Vì vậy, tôi sẽ vẽ Người đầu tiên là kích thước. Và điều thứ hai tôi sẽ để vẽ như là một mảng. 

Nhưng chỉ để giữ cho mọi thứ có trật tự, bình thường tôi sẽ rút ra một mảng như thế này, nhưng đó là loại tốt đẹp nếu chúng ta phù hợp với thực tế, hoặc phù hợp với mô hình tâm thần. Vì vậy, hãy để tôi thay vì vẽ mảng theo chiều dọc, mà chỉ là, một lần nữa, màn biểu diễn của nghệ sĩ. Không thực sự có vấn đề gì đó là bên dưới mui xe. Và chúng tôi sẽ nói rằng, theo mặc định, khả năng là có được ba. Vì vậy, đây sẽ là vị trí 0, điều này sẽ là vị trí 1, điều này sẽ là vị trí 2. 

Nếu tôi hối lộ với một quả bóng căng thẳng, sẽ một người nào đó muốn đi lên và chạy hội đồng quản trị ở đây chỉ là một thời điểm? OK, thấy bàn tay của bạn đầu tiên. Lên đây. Được rồi. Vì vậy, tôi tin rằng đó là Steven. Lên đây. Được rồi. 

Nhưng giả sử bây giờ chúng ta quay lại với ban đầu nhà nước trên thế giới mà tôi vừa tuyên bố một chồng, và nó sẽ có công suất ba. Nhưng kích thước vẫn chưa được xác định. Khay chưa được xác định. Vì vậy, một vài câu hỏi đầu tiên. Và hãy để tôi cung cấp cho bạn mic để bạn có thể cùng chia sẻ tích cực hơn trong việc này. 

Vì vậy, những gì bên trong kích thước tại thời điểm này trong thời gian nếu tất cả tôi đã làm là tuyên bố một chồng với một dòng mã? 

STEVEN: Không nhiều lắm. 

DAVID Malan: OK, không nhiều. Chúng ta biết những gì bên trong kích thước, Chúng ta biết những gì bên trong của mảng này đây? 

STEVEN: Chỉ cần mã số ngẫu nhiên, phải không? Chỉ - 

DAVID Malan: Vâng, tôi sẽ gọi nó là mã, nhưng ngẫu nhiên - 

STEVEN: điều. 

DAVID Malan: Những điều như ngẫu nhiên 

STEVEN: Bit. 

DAVID Malan: Bits, phải không? Vì vậy, các giá trị rác, phải không? Vì vậy, hoán vị của của 0 và 1. Chứng tích của tập quán trước bộ nhớ này. Và chúng tôi không thực sự biết những gì các giá trị được, vì vậy chúng tôi thường vẽ chúng là dấu hỏi. 

Vì vậy, điều đầu tiên chúng ta có lẽ sẽ muốn làm ở đây - và hãy để tôi cung cấp cho lĩnh vực này trong trong đó một tên - khay. Những gì nên chúng tôi có lẽ là khởi tạo kích thước nếu chúng ta muốn bắt đầu sử dụng ngăn xếp này? 

STEVEN: Khay là phụ 3. 

DAVID Malan: Vì vậy, OK. Để được rõ ràng, công suất được khai báo ở những nơi khác như ba. Và đó là những gì tôi đã sử dụng phân bổ mảng. Kích thước sẽ đề cập đến bao nhiêu khay hiện nay là trên stack. 

STEVEN: Zero. 

DAVID Malan: Vì vậy, nó phải là không. Nên đi trước, và với bất kỳ ngón tay, rút ra một số không trong kích thước. Được rồi. Vì vậy, bây giờ, những gì bên trong này ở đây, chúng ta không biết. Đây là những giá trị thực sự chỉ là rác. Vì vậy, chúng ta có thể rút ra những dấu hỏi, nhưng chúng ta hãy giữ cho hội đồng quản trị sạch cho bây giờ bởi vì nó không quan trọng những gì đang có. Chúng tôi không cần phải khởi tạo mảng để bất cứ điều gì, bởi vì nếu chúng ta biết rằng kích thước của ngăn xếp là số không, tốt, chúng tôi không nên nhìn vào bất cứ điều gì trong mảng này anyway tại thời điểm này. 

Vì vậy, bây giờ giả sử rằng tôi đẩy số 9 vào ngăn xếp. Làm thế nào chúng ta nên cập nhật các cấu trúc dữ liệu bên trong của hộp đen này? Những giá trị cần phải thay đổi? 

STEVEN: Trong thời hạn - kích thước? 

DAVID Malan: OK. Kích thước nên trở thành những gì? 

STEVEN: Kích thước sẽ là một. 

DAVID Malan: OK. Vì vậy, kích thước nên trở thành một trong. Vì vậy, bạn có thể làm điều này trong một số cách. Hãy để tôi cho bạn, bây giờ của bạn ngón tay là một cục tẩy. Được rồi. Sau đó bây giờ ngón tay của bạn là một bàn chải. Được rồi. Và bây giờ những gì người khác đã thay đổi, rõ ràng, trong cấu trúc dữ liệu? 

Steven: Chúng tôi đang đi từ từ dưới lên đến 9. 

DAVID Malan: 9. OK, tốt. Vì vậy, vẫn không có vấn đề gì là tại vị trí một hoặc hai bởi vì họ giá trị rác, nhưng chúng ta không nên bận tâm tìm kiếm ở đó bởi vì kích thước là nói với chúng tôi rằng chỉ có yếu tố đầu tiên thực sự là hợp pháp. Vì vậy, bây giờ tôi đẩy 17 vào danh sách này. Những gì xảy ra cho hình ảnh này? 

STEVEN: Vì vậy, kích thước sẽ đi đến hai. 

DAVID Malan: OK. Bạn tẩy - oops. Bạn là một cục tẩy. 

STEVEN: Eraser. 

DAVID Malan: Bạn là một bàn chải. 

STEVEN: Brush. 

DAVID Malan: OK. Và những gì khác? 

STEVEN: Và sau đó chúng tôi - 

DAVID Malan: Chúng tôi đã đẩy 17. 

Steven: Chúng tôi dính vào 17 trên đầu, vì vậy - 

DAVID Malan: OK, tốt. 

Steven: - thả nó xuống. 

DAVID Malan: Được rồi. Nó nhận được dễ dàng. Tôi sẽ không để giúp bạn thời gian này. Đẩy 22. 

STEVEN: Xong. Trở thành một cục tẩy. Tôi trở thành một bàn chải. Và sau đó tôi đặt 22. 

DAVID Malan: 22. Tuyệt vời. Vì vậy, hơn một lần. Bây giờ tôi sẽ để đẩy vào ngăn xếp 26. 

STEVEN: Ooh. Ôi trời. Bạn thực sự bắt tôi mất cảnh giác. 

DAVID Malan: Bạn đã không thấy điều này sắp tới? 

Steven: Tôi không thấy điều này tới. Có thể chúng ta khả năng tái ban đầu? 

DAVID Malan: Đó là một câu hỏi hay. Vì vậy, chúng tôi đã loại sơn mình trong một góc ở đây. Có thực sự là không ra tốt cho Steven bởi vì chúng tôi đã phân bổ mảng này tĩnh, có thể nói, bên trong của cấu trúc dữ liệu. Và chúng tôi đã được mã hóa cơ bản cứng nó có kích thước ba. Vì vậy, chúng ta không thể thực sự phân phối lại nó. 

Chúng ta có thể nếu chúng ta quay trở lại trong, chúng tôi xác định lại khay là một con trỏ sau đó chúng tôi sử dụng malloc để nhớ tay. Bởi vì nếu chúng ta có bộ nhớ từ đống thông qua malloc, chúng tôi sau đó có thể giải phóng nó. Nhưng trước khi giải phóng nó, chúng ta có thể tái phân bổ một phần lớn của bộ nhớ, cập nhật con trỏ, và vv. Nhưng hiện nay, điều này thực sự là tốt nhất chúng tôi có thể làm. Đẩy và pop được có lẽ sẽ có để báo hiệu một số lỗi. 

Vì vậy, ví dụ, thực hiện của chúng tôi đẩy có thể trở lại một bool mà trước đó trở thành sự thật, sự thật, sự thật. Nhưng lần thứ tư, nó sẽ có trở lại sai, ví dụ. Được rồi. Thực hiện rất tốt. Xin chúc mừng. Bạn đã kiếm được quả bóng căng thẳng của bạn ngày hôm nay. 

[Vỗ tay] 

Steven: Cảm ơn bạn. 

DAVID Malan: Cảm ơn bạn. OK, vì vậy điều này có vẻ không nhiều một bước về phía trước, phải không? Chúng tôi mô tả cấu trúc dữ liệu này. Nó được hấp dẫn, phải không? Hệ điều hành thích nó. Rõ ràng các trang web có thể tận dụng điều này, và các ứng dụng khác vẫn còn. Nhưng những gì một giới hạn ngu ngốc mà chúng ta sao để sắp xếp tuần hai giới hạn nơi mà chúng tôi đã cố định kích thước mảng. 

Vì vậy, có thực sự là một vài cách chúng ta có thể giải quyết điều này. Chúng tôi tự động có thể phân bổ mảng, không bằng cứng mã hóa nó như tôi đã thực hiện ở đây, nhưng thay vào đó lại tuyên bố này, chỉ cần được rõ ràng, như một cái gì đó như thế này. Int * khay, không quyết định trên công suất được nêu ra. Nhưng khi tôi tuyên bố chồng ở nơi khác trong mã của tôi, sau đó tôi có thể gọi malloc, có được địa chỉ của một đoạn bộ nhớ, và tôi có thể chỉ định địa chỉ để khay. 

Và sau đó, bởi vì nó chỉ là một đoạn bộ nhớ, tôi có thể tiếp tục sử dụng vuông khung ký hiệu theo cách thông thường. Bởi vì một lần nữa, có loại này tương đương với chức năng của mảng và khối của bộ nhớ mà đến trở lại từ malloc. Chúng ta có thể đối xử với người khác như sử dụng con trỏ số học hoặc khung vuông ký hiệu. Vì vậy, đó là một cách tiếp cận. 

Nhưng làm thế nào khác chúng ta có thể thực hiện điều này cấu trúc dữ liệu tương tự, có khả năng? Phải không? Tôi cảm thấy như chúng tôi chỉ giải quyết này vấn đề như một tuần trước đây. Các giải pháp cho vấn đề này là gì rằng Steven chạy vào? Vì vậy, danh sách liên kết, phải. 

Nếu vấn đề là chúng ta đang vẽ mình vào một góc bằng cách phân bổ trước bộ nhớ quá nhỏ mà chúng ta sau đó đã bằng cách nào đó giải quyết, tốt, tại sao không chỉ tránh được phát hành hoàn toàn? Tại sao không chỉ cần khai báo khay là một con trỏ tới một nút, ergo một danh sách liên kết, và sau đó chỉ cần phân bổ các nút mới mỗi khi Steven cần thiết để phù hợp với một số vào cấu trúc dữ liệu. 

Vì vậy, các hình ảnh sẽ phải thay đổi. Nó sẽ không được làm sạch và như đơn giản chỉ là một mảng của ba số nguyên. Bây giờ nó sẽ là một con trỏ đến một cấu trúc, cấu trúc và có nghĩa là sẽ có một int và một con trỏ tới. Nó sẽ dẫn qua con trỏ đến một cấu trúc như vậy một cấu trúc như vậy. Vì vậy, các hình ảnh sẽ thực sự nhận được một chút hỗn độn. Và chúng tôi đã buộc mũi tên tất cả mọi thứ với nhau. 

Nhưng đó là tốt, đúng, bởi vì chúng ta đã thấy cách để làm điều này. Và một khi bạn có được thoải mái thực hiện một cái gì đó giống như một liên kết danh sách, bạn sẽ phải làm gì nếu bạn chọn để thực hiện một bảng băm với chuỗi riêng biệt cho p-bộ 6, bạn có thể sử dụng nó như là một khối xây dựng, hoặc một thành phần, hoặc trong Scratch nói, một thủ tục, một cái gì đó mà bạn đặt, bạn tạo ra mảnh ghép của riêng bạn mà bạn có thể sử dụng lại. Cân bằng như vậy, nhưng các giải pháp tiềm năng mà chúng tôi đã thực sự nhìn thấy trước. 

Vì vậy, khá thường xuyên, bạn sẽ thấy điều này mỗi hoặc hai năm khi Apple phát hành một cái gì đó mới, và tất cả những người điên xếp hàng bên ngoài của Apple cửa hàng để mua cận biên của họ nâng cấp về phần cứng. Tôi nói điều này, đó là OK, vì Tôi là một trong những người đó. Vì vậy, loại cấu trúc dữ liệu có thể đại diện cho thực tế này? 

Vâng, chúng ta hãy gọi nó là một hàng đợi, một dòng. Vì vậy, Anh sẽ gọi nó thường là một hàng đợi anyway, do đó nó là một cái tên đẹp. Và hai hoạt động mà một hàng đợi sẽ hỗ trợ chúng ta sẽ gọi một enqueue hoạt động và hoạt động dequeue, đó cũng tương tự như trong tinh thần để đẩy và pop. Nó chỉ là loại khác nhau trong quy ước, những gì chúng tôi đang gọi điện thoại này. Nhưng để enqueue một cái gì đó có nghĩa là để thêm hoặc chèn nó vào cấu trúc dữ liệu. Để dequeue có nghĩa là để loại bỏ nó. Nhưng trong khi một chồng là một dữ liệu LIFO cấu trúc, một hàng đợi là một trong đầu, đầu tiên trong cấu trúc dữ liệu. 

Nếu bạn là người đầu tiên trong dòng, bạn sẽ là người đầu tiên để có được ra khỏi dòng và mua thiết bị mới của bạn. Hãy tưởng tượng như thế nào khó chịu những người này sẽ được nếu Apple thay vì sử dụng một chồng, cho Ví dụ, để thực hiện việc chọn lên đồ chơi mới của bạn. Vì vậy, hàng đợi có ý nghĩa, chắc chắn, và chúng ta có thể nghĩ về tất cả các loại các ứng dụng, có lẽ, cho hàng đợi, đặc biệt là khi bạn muốn công bằng. Vậy làm thế nào chúng ta có thể thực hiện các như một cấu trúc dữ liệu? 

Vâng, tôi đề nghị chúng ta có thể cần phải làm theo cách này. Vì vậy, tôi sẽ bây giờ có con số. Vì vậy, chúng tôi sẽ giữ nó đơn giản và không nhất thiết phải nói về khay. Chỉ số mà người dân nhận được. Khả năng sẽ đi, một lần nữa, sửa chữa tổng số người có thể ở dòng này, như ba hoặc bất cứ điều gì khác giá trị. 

Nhưng tôi đề nghị rằng tôi cần phải theo dõi không chỉ về kích thước của các hàng đợi, bao nhiêu điều trong đó. Vì vậy kích thước là kích thước, công suất hiện tại là kích thước tối đa. Chỉ cần một lần nữa, danh pháp theo quy ước. Tại sao tôi cần một int thêm bên trong của một danh sách để theo dõi những người trong phía trước của dòng? Tại sao tôi cần phải làm điều đó trong trường hợp này? 

Vâng, làm thế nào là hình ảnh này sẽ thay đổi? Tôi có lẽ có thể tái sử dụng nhất của hình ảnh này. Hãy để tôi đi trước và xóa những gì ở đây. Chúng tôi sẽ cung cấp cho một hơi tên khác nhau ở đây. Hãy thoát khỏi 17, chúng ta hãy thoát khỏi trong số 9, chúng ta hãy thoát khỏi 3. Và chúng ta hãy thêm một điều khác. Tôi đề nghị rằng tôi cần phải theo dõi mặt trước của danh sách, mà chỉ là sẽ là một int là tốt. Và chúng ta sẽ giữ nó đơn giản. Không có danh sách liên kết cho bây giờ. 

Chúng tôi sẽ thừa nhận rằng chúng ta sẽ băng lên chống lại giới hạn này. Nhưng những gì tôi muốn xem xảy ra thời gian này? Vì vậy, giả sử tôi đi trước và là người đầu tiên người đi lên trong dòng, và đó là số 9. Chúng tôi có bóng căng thẳng. Tôi có thể ăn cắp, nói, hai hoặc ba người? Một, hai, ba? Lên đây. Ngay từ trước, bởi vì chúng tôi sẽ thực hiện điều này nhanh chóng. 

Mỗi bạn bây giờ là có được một cậu bé người hâm mộ xếp hàng tại Apple. Bạn sẽ không nhận được phần cứng của Apple vào cuối năm mặc dù điều này. Được rồi. Vì vậy, bạn số 9, bạn số 17, số 22. Đây là những con số tùy ý, như sinh viên ID hay những thứ linh tinh. Và chỉ trong một thời điểm, chúng ta hãy bắt đầu để bắt đầu thêm điều. Và tôi sẽ chạy hội đồng quản trị ở đây thời gian này. 

Vì vậy, trong trường hợp này, tôi đã khởi tạo phía trước là - Tôi thực sự không quan tâm những gì phía trước, bởi vì kích thước là số không. Như vậy có thể này cũng chỉ là một dấu hỏi. Tất cả đều là dấu hỏi. Vì vậy, bây giờ chúng tôi sẽ bắt đầu thực sự thấy một số người xếp hàng tại cửa hàng. 

Vì vậy, nếu số 9, bạn là người đầu tiên có lúc 05:00, đi trước và xếp hàng, hoặc tối hôm trước. OK. Vì vậy, bây giờ là 9 đây. Vì vậy, 9 là ở mặt trước của danh sách. Vì vậy, tôi sẽ đi trước và cập nhật kích thước của dữ liệu hiện tại này cấu trúc không là 0 nữa, nhưng là 1. Tôi sẽ đưa 9 tại phía trước của danh sách. Hãy để tôi đi trước và chuyển đổi màn hình vì vậy chúng tôi có thể nhìn thấy qua chúng tôi ở đây. 

Và bây giờ những gì tôi muốn đặt ở phía trước? Tôi sẽ theo dõi các phía trước của hàng đợi ngay bây giờ là vị trí 0. Bởi vì những gì được tiếp theo sẽ xảy ra? Vâng, giả sử bây giờ tôi enqueue 17 là tốt. Vì vậy, hop trong dòng đó. Và một lần nữa, các loại cửa cho các cửa hàng là có được ở đây. Vì vậy, bây giờ tôi đã bổ sung thêm 17. Và mặc dù những kẻ đang chặn màn hình, đó là OK, bởi vì chúng ta có thể nhìn thấy nó ở đây. Xin lôi. 

ĐỐI TƯỢNG: Chúng tôi có thể di chuyển - 

DAVID Malan: Không, đó là OK. Nó lớn lên ở đó. Vì vậy, bây giờ 17 là bên trong của hàng đợi. Tôi cần phải cập nhật mà lĩnh vực mặc dù bây giờ? OK, chắc chắn kích thước. Và làm thế nào về phía trước? OK, không. Phía trước không nên thay đổi, bởi vì không giống như một chồng, chúng tôi muốn duy trì sự công bằng. Vì vậy, nếu trong 9 đến đầu tiên, chúng tôi muốn 9 là sản phẩm đầu tiên của dòng và vào cửa hàng. 

Trong thực tế, chúng ta thấy điều đó. Trước khi chúng ta chèn 22, chúng ta hãy đi trước và dequeue 9. Tên của bạn là gì nữa? 

ĐỐI TƯỢNG: Jake. 

DAVID Malan: Jake sẽ được dequeued bây giờ. Vì vậy, bạn có thể đi bộ vào cửa hàng. Và giả vờ rằng các cửa hàng là ở đó. Vì vậy, bây giờ những gì cần - dit-dit-dit! Những gì cần phải xảy ra bây giờ? Quyết định thiết kế. Vì vậy, không phải là một bản năng xấu, nhưng - Tên của bạn là gì nữa? 

Khán giả: David. 

DAVID Malan: David. Vì vậy, những gì đã làm David làm gì? Ông đã cố gắng để sắp xếp các sửa chữa dữ liệu cấu trúc và di chuyển từ vị trí của mình vào vị trí cũ của Jake. Và đó là tốt nếu chúng tôi sẵn sàng để chấp nhận điều đó như một chi tiết thực hiện. Nhưng trước tiên, chúng ta hãy cập nhật dữ liệu cấu trúc trước khi chúng tôi làm điều đó. Bởi vì tôi không thích ý tưởng của tất cả các những người chuyển trong dòng này. 

Nó không có việc lớn, nếu David hiện điều đó với một bước, nhưng một lần nữa, nghĩ lại khi tình nguyện viên đã có tám trên sân khấu và chúng tôi đã làm như chèn sắp xếp, nơi mà chúng tôi đã phải bắt đầu di chuyển tất cả mọi người xung quanh. Mà có đắt tiền, phải không? Điều đó làm tôi co rúm người lại về O lớn n, O lớn của n bình phương một lần nữa. Nó không cảm thấy như một kết quả lý tưởng. 

Vì vậy, chúng ta chỉ cần cập nhật này. Vì vậy kích thước của hàng đợi không còn là 2. Nó bây giờ chỉ đơn giản là 1. Nhưng bây giờ tôi có thể cập nhật một cái gì đó Tôi đã không cập nhật trước, phía trước của danh sách. Tôi chỉ có thể nói, là vị trí mà 1? Vì vậy, bây giờ chúng tôi có giá trị rác đây, giá trị rác ở đây, và David trong giữa rác này. Nhưng cấu trúc dữ liệu vẫn còn nguyên vẹn. 

Và trong thực tế, tôi thậm chí không cần phải thay đổi số trước đây của Jake 9, bởi vì những người quan tâm. Tôi có đủ thông tin bây giờ trong kích thước mà tôi biết có một người trong hàng đợi này. Và tôi biết rằng người đó là ở vị trí 1, không phải 0. Tôi không đếm. Vì vậy, 1 là tốt. Vì vậy, các cấu trúc dữ liệu vẫn OK. 

Vâng, những gì xảy ra tiếp theo? Hãy enqueue - Tên của bạn là gì? 

ĐỐI TƯỢNG: Callen. 

DAVID Malan: Callen. Hãy enqueue một Callen, và 22 giờ là trong hàng đợi. Vì vậy, bây giờ những gì có để thay đổi đây? Phía trước sẽ không thay đổi, rõ ràng. Kích thước sẽ thay đổi được 2 lần nữa. Và 22 kết thúc ở đây, 9 vẫn còn hiện diện, nhưng đó là một cách hiệu quả giá trị rác tại. Nó chỉ là một tàn dư của Jake qua. 

Vì vậy, bây giờ những gì sẽ xảy ra nếu Tôi dequeue David? Một hoạt động cuối cùng, dequeue David. Chúng tôi có thể thay đổi, nhưng tôi đề nghị chúng ta hãy làm càng ít việc càng tốt. Bây giờ cấu trúc dữ liệu của tôi đi sao có kích thước 2-1. Nhưng phía trước của hàng đợi bây giờ trở thành 2. Tôi không cần phải thay đổi những con số chỉ được nêu ra, bởi vì chúng chỉ giá trị rác. 

Nhưng bây giờ những gì sẽ xảy ra? Giả sử tôi enqueue bản thân mình, 26? Tôi cảm thấy mình không thuộc về đây. Vì vậy, tôi được enqueued. Vì vậy, tôi loại thuộc về nơi này. Và ngay cả khi bạn không hoàn toàn đánh giá cao này trực quan trên sân khấu, bởi vì chúng tôi có rất nhiều phòng, tôi nên không được đứng ở đây, tại sao? 

ĐỐI TƯỢNG: Bạn nằm ngoài giới hạn. 

DAVID Malan: Đúng vậy. Tôi ra khỏi giới hạn. Tôi đã được lập chỉ mục ngoài giới hạn của mảng này. Tôi thực sự phải ở trong một trong những ba địa điểm có thể. Bây giờ, nơi là tự nhiên nhất để đi? Tôi đề nghị chúng ta sử dụng đòn bẩy một tuần một trick. Các nhà điều hành mod, tỷ lệ phần trăm. Bởi vì tôi đang đứng ở mặt kỹ thuật vị trí 3, nhưng tôi làm 3 công suất mod, do đó, 3, một dấu phần trăm, 3 - công suất là 3. Đó là những gì? Phần còn lại là những gì khi bạn chia 3 của 3? 0. 

Vì vậy, mà đặt tôi đã Jake, mà thực sự là tốt. Vì vậy bây giờ thực hiện điều này sẽ là một chút đau đầu. Nó thực sự chỉ là một dòng đau đầu, mã. Nhưng ít nhất bây giờ có rác giá trị ở đây, nhưng có hai ints hợp pháp ở đây. Và tôi cho rằng bây giờ chúng tôi đã thực hiện chính xác những gì chúng ta cần phải làm như vậy miễn là chúng ta thay đổi những gì của Jake giá trị đã là 26. 

Bây giờ chúng tôi có đủ thông tin vẫn còn để duy trì tính toàn vẹn cấu trúc dữ liệu này. Chúng ta vẫn còn loại ra khỏi may mắn khi chúng tôi muốn chèn bốn hoặc nhiều hơn tổng số yếu tố, nhưng tôi có thể ít nhất là làm đẹp hiệu quả sử dụng liên tục này thời gian, trên thực tế. Tôi không phải lo lắng về thay đổi tất cả mọi người, như độ nghiêng của David là. 

Bất kỳ câu hỏi trên ngăn xếp, hoặc hàng đợi này? 

ĐỐI TƯỢNG: là lý do tại sao bạn cần kích thước để bạn biết nơi có một người? 

DAVID Malan: Chính xác. Tôi cần phải biết kích thước của mảng bởi vì tôi cần phải biết chính xác có bao rất nhiều những giá trị này là hợp pháp, và vì vậy mà tôi có thể tìm thấy nơi để đặt người tiếp theo. Chính xác. Kích thước là - trên thực tế, chúng tôi đã không cập nhật này. Tôi thêm bản thân mình tại 26. Kích thước là bây giờ, không phải 1, nhưng 2. Vì vậy, bây giờ điều này thực sự giúp tôi tìm thấy đứng đầu danh sách, mà không phải là 0, không 1, nhưng là 2. Mặt trước của danh sách thực sự là số 22. Bởi vì ông đến đầu tiên, vì vậy ông nên được cho phép vào cửa hàng trước khi tôi, mặc dù trực quan tôi đang đứng gần cửa hàng. 

Tất cả phải không? Một tràng pháo tay cho những kẻ và chúng tôi sẽ cho họ ra khỏi đó. 

[Vỗ tay] 

DAVID Malan: tôi có thể cho phép bạn giữ khay. Chúng ta có thể xem những gì sẽ xảy ra nếu bạn muốn, nhưng có lẽ không. Được rồi. Vì vậy, những gì bây giờ không để lại cho chúng tôi? Vâng, hãy để tôi đề xuất rằng có một vài cấu trúc dữ liệu khác mà chúng tôi có thể bắt đầu thêm vào bộ công cụ của chúng tôi sẽ thực sự là khá, khá liên quan như chúng tôi đi sâu vào công cụ web. Mà một lần nữa, có một số loại kết nối để trồng trong các hình thức một cái gì đó gọi là DOM, tài liệu mô hình đối tượng. Nhưng chúng ta sẽ thấy nhiều hơn mà chẳng bao lâu. 

Hãy để tôi đề xuất rằng chúng ta definitionally gọi cây bây giờ những gì bạn có thể biết như nhiều hơn một cây gia đình, nơi bạn có một số tổ tiên tại rễ của cây. Một nữ chúa gia trưởng hoặc tại phần trên của cây. Nếu không có vợ hoặc chồng, trong trường hợp này. Nhưng bây giờ chúng tôi có những gì chúng tôi sẽ gọi trẻ em, trong đó có các nút treo ra khỏi con trái hoặc con phải, mũi tên như mô tả ở đây. 

Nói cách khác, trong một cấu trúc dữ liệu cây trong máy tính, một cây có không hoặc nhiều nút. Nếu nó có ít nhất một nút, đó được gọi là gốc. Đó là những việc trực quan mà chúng ta rút ra ở đầu trang. Và nút đó, giống như bất kỳ nút khác, có thể có không, một, hoặc hai, hoặc ba, hoặc tuy nhiên nhiều trẻ em cấu trúc dữ liệu hỗ trợ. Trong trường hợp này, các gốc, lưu trữ giá trị một, có hai con, 2 và 3, vì vậy chúng tôi thường gọi 2 bên trái trẻ em và 3 con phải. 

Và sau đó khi chúng tôi có được giảm xuống còn 5, 6, và 7, 6 có thể được gọi là con giữa. Nếu bạn có bốn người con, nó được gây nhầm lẫn. Vì vậy, chúng tôi ngừng sử dụng loại đó các phím tắt bằng lời nói. Nhưng nó thực sự chỉ là một cây gia đình. Và lá ở đây là các nút mình không có con. Họ treo ra dưới cùng của cây. 

Vậy làm thế nào chúng ta có thể thực hiện một cây chỉ có hai trẻ em tối đa? Chúng tôi sẽ gọi nó là một cây nhị phân. Bi lại có nghĩa là hai, trong này trường hợp, như với nhị phân. Và do đó, nó có thể có không, một, hoặc hai con tối đa. 

Tôi sẽ đề nghị chúng ta thực hiện các nút cho rằng cấu trúc với một int n, và sau đó hai con trỏ, một được gọi là còn lại, một được gọi là đúng. Nhưng những người chỉ đẹp ước tùy ý. Và những gì tốt đẹp hiện nay, đặc biệt là nếu bạn loại vật lộn với khái niệm đệ quy, hoặc nghĩ rằng đó là không thực sự là một giải pháp cho bất cứ điều gì, đặc biệt là nếu bạn có thể chạy ra khỏi bộ nhớ. Bây giờ chúng ta đang nói về dữ liệu cấu trúc và thuật toán cho phép chúng tôi đi qua và vận dụng chúng, chỉ ra rằng đệ quy trở lại trong một nhiều hơn nữa hấp dẫn nếu không cách đẹp. 

Vì vậy, đây tôi đề xuất là việc thực hiện của một chức năng tìm kiếm. Cho hai đầu vào - để nghĩ về điều này như một hộp đen. Với hai yếu tố đầu vào, n, một int, và một con trỏ vào một cái cây, một con trỏ đến một nút, hoặc thực sự là gốc của một cây, tôi cho rằng chức năng này có thể trở lại đúng hay sai, mà giá trị n là bên trong của cây này. 

Bên trong của hộp đen này là gì? Vâng, bốn chi nhánh. Chỉ kiểm tra đầu tiên. Nếu cây là vô giá trị, chỉ cần trả về false. Nếu không có nút, không có n, không có số, chỉ cần trả về false. Nếu mặc dù, n, giá trị mà bạn đang tìm kiếm cho, nhỏ hơn cây mũi tên n, và chỉ để được rõ ràng, điều đó có nghĩa là khi Tôi viết cây và sau đó mũi tên ký hiệu, n? Chính xác. Nó có nghĩa là tới đích mà con trỏ được gọi là cây. Đi đến đó, và sau đó đi vào bên trong mà nút và nhận được lĩnh vực của mình gọi là n. Và sau đó so sánh n thực tế đó là thông qua vào tìm kiếm chống lại nó. 

Vì vậy, nếu n là ít hơn, giá trị n trong nút cây chính nó, tốt, có nghĩa là gì? Điều đó có nghĩa không có gì ở cái nhìn đầu tiên. Phải không? Cũng giống như khi bạn có một mảng của giá trị, bạn có thể muốn áp dụng nhị phân Tìm kiếm là một hình thức phân chia và chinh phục. Nhưng những gì đã giả định chúng ta cần phải thực hiện cho tìm kiếm nhị phân để làm việc ở tất cả các trong danh bạ điện thoại và thí dụ trước đây? 

Làm thế nào để được sắp xếp. Vì vậy, hãy tinh chỉnh các định nghĩa của cây đây không phải chỉ là một cây, có thể có bất kỳ số lượng trẻ em. Không chỉ là một cây nhị phân, có thể có 0, 1, 2 hoặc tối đa. Nhưng như một cây tìm kiếm nhị phân, hoặc BST, mà chỉ là một cách nói một cây nhị phân như vậy mà mỗi nút con trái, nếu có, là dưới nút. Và con phải của mỗi nút, nếu có, là lớn hơn hơn các nút đó. 

Vì vậy, nói cách khác, nếu bạn đã vẽ ra khỏi cây, tất cả các con số sự cân cẩn thận như thế này để nếu bạn có 55 như là gốc, 33 có thể đi bên trái của nó vì nó ít hơn 55. 77 có thể đi bên phải của nó bởi vì nó lớn hơn 55. Nhưng bây giờ nhận thấy, cùng một định nghĩa, đó là một định nghĩa đệ quy bằng lời nói, phải áp dụng cho 33. Con trái 33 của phải nhỏ hơn nó, và con phải của 33, 44, phải lớn hơn nó. 

Vì vậy, đây là một cây tìm kiếm nhị phân, và Tôi đề nghị, sử dụng một chút đệ quy, chúng ta có thể tìm thấy n. Vì vậy, nếu n là ít hơn so với n giá trị đó là nút hiện tại, tôi sẽ đi trước và punt, vậy để nói chuyện, và chỉ trở lại bất cứ câu trả lời là của tìm kiếm n trên con trái cây của. Nhận thấy một lần nữa, chức năng này chỉ hy vọng sẽ là một ngôi sao nút, một con trỏ đến một nút. Vì vậy, chắc chắn tôi chỉ có thể làm cây mũi tên trái, sẽ dẫn tôi sang một nút khác. Nhưng nút đó là những gì? 

Vâng, theo tuyên bố này, trái chỉ là một con trỏ, để chỉ có nghĩa là tôi đang đi qua với chức năng tìm kiếm một con trỏ khác nhau, cụ thể là là cái đại diện cây con trái của tôi. Vì vậy, trong trường hợp này, con trỏ đến 33, nếu đây là mẫu đầu vào của chúng tôi khi đó, nếu n lớn hơn n giá trị tại nút hiện tại trong cây, sau đó tôi sẽ đi trước và punt trong khác hướng và chỉ nói rằng, tôi không biết nếu giá trị n này nằm ở cây, nhưng tôi biết nếu nó có, nó xuống của tôi chi nhánh bên phải, vậy để nói chuyện. Vì vậy, hãy để tôi gọi đệ quy tìm kiếm, đi qua một n một lần nữa, nhưng đi qua trong một con trỏ đến con phải của tôi. 

Nói cách khác, nếu tôi là hiện tại 55 và tôi đang tìm kiếm 99, tôi biết rằng 99 lớn hơn 55, vì vậy chỉ cần như tôi xé những tuần trước bạ điện thoại và chúng tôi đi bên phải, tương tự như chúng ta sẽ đi ngay đây. Và tôi không biết nếu nó ở bên phải của tôi trẻ em, và nó không phải, 77 là có, nhưng Tôi biết đó là theo hướng đó. Vì vậy, tôi gọi tìm kiếm trên con phải của tôi, 77, và để cho con số tìm kiếm ra khỏi nếu có 99 trong tùy ý này ví dụ là thực sự có. 

Khác, trường hợp thức là những gì? Nếu cây là null là một trường hợp. Nếu n là ít hơn so với các nút của hiện tại giá trị là một trường hợp khác. Nếu n là lớn hơn so với hiện tại giá trị nút là một trường hợp thứ ba. Trường hợp thứ tư và cuối cùng là những gì? Tôi nghĩ rằng chúng ta hết trường hợp, phải không? Nó phải được rằng n là trong nút hiện tại là tôi đang trên. 

Vì vậy, nếu tôi đang tìm kiếm 55 vào thời điểm này trong những câu chuyện, chi nhánh của cây sẽ trở thành sự thật. Vì vậy, điều thú vị ở đây là chúng tôi trên thực tế, không giống như tuần qua, chúng tôi loại của có hai trường hợp cơ sở. Và họ không cần phải được tất cả ở đầu trang. Phía trên là một trường hợp cơ sở bởi vì nếu cây là vô giá trị, không có gì để làm cả. Chỉ trả lại một mã hóa cứng giá trị sai. 

Chi nhánh phía dưới là sắp xếp của mặc định, theo đó nếu chúng tôi đã kiểm tra vô giá trị, chúng tôi đã kiểm tra nếu nó phải được để lại, nhưng nó không phải là, chúng tôi đã kiểm tra nếu nó nên được quyền, nhưng nó không nên, rõ ràng nó phải được đúng cái mình đang có. Đó là một trường hợp cơ sở. Do đó, có hai trường hợp đệ quy kẹp có ở giữa. Nhưng tôi có thể viết này theo thứ tự nào. Tôi chỉ nghĩ đó loại cảm thấy tự nhiên kiểm tra đầu tiên cho một lỗi có thể, sau đó kiểm tra lại, sau đó kiểm tra ngay, sau đó giả định rằng bạn đang ở nút bạn đang thực sự tìm kiếm. 

Vì vậy, tại sao điều này có thể có ích? Vì vậy, nó quay ra - và cho tôi chuyển đến một lời trêu ghẹo đây đó trong các trang web. Chúng ta sẽ bắt đầu sử dụng không phải là một ngôn ngữ lập trình đầu tiên, nhưng một ngôn ngữ đánh dấu. Ngôn ngữ đánh dấu là một trong đó là tinh thần tương tự lập trình ngôn ngữ, nhưng nó không cung cấp cho bạn khả năng thể hiện bản thân một cách hợp lý. Nó chỉ cung cấp cho bạn khả năng thể hiện bản thân cấu trúc. 

Nơi nào bạn muốn đặt một cái gì đó trên trang web, các trang web? Màu sắc làm những gì bạn muốn làm cho nó? Những gì kích thước phông chữ nào bạn muốn làm cho nó? Từ những gì bạn thực sự muốn trên các trang web? Vì vậy, đó là một ngôn ngữ đánh dấu. Nhưng sau đó chúng tôi sẽ rất nhanh chóng giới thiệu JavaScript, đó là một chính thức ngôn ngữ lập trình. Tương tự như cú pháp xuất hiện C, nhưng nó sẽ có một số tốt đẹp, mạnh mẽ hơn, tính năng thân thiện. 

Và một trong những nỗi thất vọng tại này điểm trong học kỳ là chúng ta sẽ sớm thực hiện Speller trong rất ít dòng mã sử dụng các ngôn ngữ khác hơn so với C chính nó cho phép, nhưng vì lý do của chúng tôi sẽ sớm hiểu. Đây sẽ là lần đầu tiên trang web như vậy. Nó sẽ hoàn toàn underwhelming, người đầu tiên chúng tôi thực hiện. Nó sẽ chỉ đơn giản, xin chào thế giới. Nhưng nếu bạn đã bao giờ nhìn thấy nó trước, đây là HTML, HyperText Markup Language. 

Nếu bạn đi đến một tùy chọn menu nhất định trong hầu hết bất kỳ trình duyệt trên bất kỳ trang web trên internet, bạn sẽ nhìn thấy HTML rằng một số người đã viết thư cho tạo ra trang web đó. Và nó có thể không giống như ngắn gọn hoặc là gọn gàng như thế này. Nhưng nó sẽ đi theo mô hình của các mở ngoặc và dấu gạch chéo và thư và có khả năng con số. 

Tôi nghĩ rằng tôi muốn cung cấp cho bạn một lời trêu ghẹo những gì bạn sẽ có thể làm sau khi CS50. Cho tôi đi đến cs.harvard.edu / cướp, Rob trang chủ của chúng ta Bowden của. Ông thực hiện điều này cho chúng ta. Vì vậy, bạn sẽ sớm có thể làm điều đó. Và cũng có thể, những gì bạn nghe sáng nay - những gì bạn nghe sáng nay - 

[HAMSTER DANCE MUSIC] 

- Vì bạn sẽ có thể thực hiện điều này. Đang chờ đợi chúng tôi vào thứ tư. Chúng ta sẽ thấy bạn sau đó. 

[HAMSTER DANCE MUSIC] DAVID Malan: Tại tới CS50 -