DOUG LLOYD: Vì vậy, trong CS50, chúng tôi đã được bảo hiểm rất nhiều cấu trúc dữ liệu khác nhau, bên phải? Chúng tôi đã nhìn thấy mảng, và liên kết danh sách, và các bảng băm, và cố gắng, ngăn xếp và hàng đợi. Chúng tôi cũng sẽ tìm hiểu một chút về cây và đống, nhưng thực sự những tất cả chỉ kết thúc lên được biến tấu trên một chủ đề. Có thực sự là những loại bốn ý tưởng cơ bản rằng tất cả mọi thứ khác có thể đun sôi xuống. Mảng, danh sách liên kết, bảng băm, và cố gắng. Và như tôi đã nói, có là các biến thể trên chúng, nhưng điều này là khá nhiều sẽ tóm tắt tất cả mọi thứ chúng ta sẽ nói chuyện trong lớp này về C. Nhưng làm thế nào để các biện pháp lên tất cả, phải không? Chúng tôi đã nói chuyện về những ưu và khuyết điểm của mỗi trong video riêng về họ, nhưng có rất nhiều con số bị ném ra xung quanh. Có rất nhiều chung suy nghĩ bị ném ra xung quanh. Hãy thử và củng cố nó chỉ vào một nơi. Hãy cân nhắc những ưu chống lại các khuyết điểm, và xem xét mà cấu trúc dữ liệu có thể là dữ liệu đúng cấu trúc cho tình hình cụ thể của bạn, bất cứ loại dữ liệu bạn đang lưu trữ. Bạn không nhất thiết phải luôn luôn cần phải sử dụng chèn siêu nhanh, xóa, và tra cứu của một Trie nếu bạn thực sự không quan tâm về chèn và xóa quá nhiều. Nếu bạn cần một cách nhanh chóng chỉ ngẫu nhiên truy cập, có thể là một mảng là tốt hơn. Vì vậy, chúng ta hãy chắt lọc đó. Hãy nói về một trong bốn loại chính của cấu trúc dữ liệu mà chúng tôi đã nói chuyện về, và chỉ nhìn thấy khi họ có thể là tốt, và khi họ có thể không được tốt như vậy. Vì vậy, chúng ta hãy bắt đầu với mảng. Vì vậy, chèn, đó là loại xấu. 

Chèn vào cuối mảng là OK, nếu chúng ta đang xây dựng một mảng như chúng tôi đi. Nhưng nếu chúng ta cần phải chèn các yếu tố vào trung lộ, nghĩ lại để chèn sắp xếp, có rất nhiều của việc chuyển đổi để phù hợp với một yếu tố trong đó. Và vì vậy nếu chúng ta sẽ chèn bất cứ nơi nào nhưng cuối mảng, đó có lẽ không tuyệt vời như vậy. 

Tương tự như vậy, xóa, trừ khi chúng tôi xóa từ cuối mảng, có lẽ cũng không quá lớn nếu chúng tôi không muốn để lại những khoảng trống rỗng, mà thông thường chúng ta không làm. Chúng tôi muốn loại bỏ một phần tử, và sau đó nó làm chúng snug một lần nữa. Và do đó, xóa các phần tử từ một mảng, cũng không tuyệt vời như vậy. 

Tra cứu, mặc dù, là rất tốt. Chúng tôi có quyền truy cập ngẫu nhiên, tra cứu thời gian liên tục. Chúng tôi chỉ nói bảy, và chúng tôi đi vào mảng di dời bảy. Chúng tôi nói 20, với đi tới mảng di dời 20. Chúng tôi không phải lặp qua. Đó là khá tốt. 

Mảng cũng tương đối dễ dàng để sắp xếp. Mỗi lần chúng tôi nói chuyện về một phân loại thuật toán, chẳng hạn như lựa chọn loại, sắp xếp chèn, bong bóng sắp xếp, hợp nhất sắp xếp, chúng tôi luôn luôn sử dụng mảng để làm điều đó, vì mảng là khá dễ dàng để sắp xếp, liên quan đến các cấu trúc dữ liệu chúng tôi đã nhìn thấy cho đến nay. 

Họ cũng là tương đối nhỏ. Không có rất nhiều không gian thêm. Bạn chỉ cần dành ra chính xác như nhiều khi bạn cần để giữ dữ liệu của bạn, và đó là khá nhiều đó. Vì vậy, họ đang khá nhỏ và hiệu quả theo cách đó. Nhưng nhược điểm khác, mặc dù, là chúng được cố định trong kích thước. Chúng ta phải khai báo chính xác như thế nào lớn, chúng tôi muốn mảng của chúng tôi có được, và chúng tôi chỉ nhận được một bắn vào nó. Chúng ta không thể phát triển và thu nhỏ nó. 

Nếu chúng ta cần phải phát triển hoặc thu nhỏ nó, chúng tôi cần phải khai báo một mảng hoàn toàn mới, copy tất cả các yếu tố của mảng đầu tiên vào mảng thứ hai. Và nếu chúng ta tính nhầm mà thời gian, chúng ta cần phải làm điều đó một lần nữa. Không tuyệt vời như vậy. Vì vậy, các mảng không cho chúng ta sự linh hoạt có số biến của các yếu tố. 

Với một danh sách liên kết, chèn là khá dễ dàng. Chúng tôi chỉ tack lên phía trước. Xóa cũng khá dễ dàng. Chúng ta phải tìm các yếu tố. Điều đó liên quan đến một số tìm kiếm. 

Nhưng một khi bạn đã tìm thấy phần tử bạn đang tìm kiếm, tất cả các bạn cần làm là thay đổi một con trỏ, có thể là hai nếu bạn có một liên kết list-- một gấp đôi danh sách liên kết, rather-- và sau đó bạn chỉ có thể giải phóng các node. Bạn không cần phải thay đổi tất cả mọi thứ xung quanh. Bạn chỉ cần thay đổi hai con trỏ, vì vậy đó là khá nhanh chóng. 

Lookup là xấu mặc dù, phải không? Để chúng tôi để tìm một phần tử trong một danh sách liên kết, dù đơn lẻ hoặc gấp đôi liên kết, chúng ta phải tìm kiếm nó là tuyến tính. Chúng ta phải bắt đầu từ đầu và di chuyển cuối cùng, hoặc bắt đầu di chuyển cuối để bắt đầu. Chúng tôi không có quyền truy cập ngẫu nhiên nữa. Vì vậy, nếu chúng ta đang làm một rất nhiều tìm kiếm, có thể một danh sách liên kết không phải là khá tốt như vậy đối với chúng tôi. 

Chúng tôi cũng thực sự khó khăn để sắp xếp, phải không? Cách duy nhất bạn có thể thực sự sắp xếp một danh sách liên kết là để sắp xếp nó như bạn xây dựng nó. Nhưng nếu bạn sắp xếp nó như bạn xây dựng nó, bạn sẽ không còn làm cho chèn nhanh nữa. Bạn sẽ không chỉ tacking đồ lên phía trước. Bạn phải tìm ra đúng chỗ để đặt nó, và sau đó chèn của bạn trở thành chỉ là về như xấu như chèn vào một mảng. Vì vậy, danh sách liên kết không tuyệt vời như vậy để phân loại dữ liệu. 

Họ cũng đang khá nhỏ, kích thước-khôn ngoan. Danh sách liên kết kép hơi lớn hơn so với danh sách đơn lẻ liên kết, mà là lớn hơn một chút là các mảng, nhưng nó không phải một số tiền rất lớn của không gian lãng phí. Vì vậy, nếu không gian là một bảo hiểm, nhưng không phải là một cao cấp thực sự mạnh điều này có thể đúng cách để đi. 

Bảng băm. Chèn vào một bảng băm là khá đơn giản. Đó là một quá trình hai bước. Trước tiên chúng ta cần phải chạy dữ liệu của chúng tôi thông qua một hàm băm để có được một mã băm, và sau đó chúng ta chèn phần tử vào bảng băm ở vị trí mã băm. 

Xóa, tương tự như danh sách liên kết, là dễ dàng một khi bạn tìm thấy phần tử. Bạn có thể tìm thấy nó đầu tiên, nhưng sau đó khi bạn xóa nó, bạn chỉ cần trao đổi một vài con trỏ, nếu bạn đang sử dụng chain riêng biệt. Nếu bạn đang sử dụng thăm dò, hoặc nếu bạn không sử dụng ở tất cả các chuỗi trong bảng băm của bạn, xóa thực sự là thực sự dễ dàng. Tất cả bạn cần làm là băm dữ liệu, và sau đó đi đến vị trí đó. Và giả sử bạn không có bất kỳ va chạm, bạn sẽ có thể xóa rất nhanh chóng. 

Bây giờ, tra cứu là nơi mà mọi thứ nhận được nhiều hơn một chút phức tạp. Đó là trên trung bình tốt hơn hơn danh sách liên kết. Nếu bạn đang sử dụng loạt, bạn vẫn còn có một danh sách liên kết, có nghĩa là bạn vẫn có tìm kiếm phương hại một danh sách liên kết. Nhưng bởi vì bạn đang dùng liên kết của bạn danh sách và tách nó trên 100 hoặc 1000 hoặc n nguyên tố trong bảng băm của bạn, bạn danh sách liên kết đều là một thứ n kích thước. Tất cả chúng đều nhỏ hơn đáng kể. Bạn đã n danh sách liên kết thay vì một danh sách liên kết kích thước n. 

Và như vậy trong thế giới thực này không đổi yếu tố, mà tôi, chúng thường không nói về trong thời gian phức tạp, nó không thực sự làm cho một sự khác biệt ở đây. Vì vậy, tra cứu vẫn là tuyến tính tìm kiếm nếu bạn đang sử dụng loạt, nhưng độ dài của danh sách Bạn đang tìm kiếm thông qua là rất, rất ngắn bằng cách so sánh. Một lần nữa, nếu phân loại là của bạn Mục tiêu ở đây, băm bảng của có lẽ không phải là cách đúng để đi. Chỉ cần sử dụng một mảng nếu phân loại là thực sự quan trọng với bạn. 

Và họ có thể chạy âm giai của kích thước. Thật khó để nói liệu một bảng băm là nhỏ hay lớn, bởi vì nó thực sự phụ thuộc vào làm thế nào lớn bảng băm của bạn là. Nếu bạn chỉ sẽ được lưu trữ năm yếu tố trong bảng băm của bạn, và bạn có một bảng băm với 10.000 phần tử trong nó, có thể là bạn đang lãng phí rất nhiều không gian. Ngược lại là bạn cũng có thể có bảng băm rất nhỏ gọn, nhưng nhỏ hơn bảng băm của bạn được, lâu hơn mỗi của những danh sách liên kết được. Và như vậy có thực sự không có cách nào để xác định chính xác kích thước của một bảng băm, nhưng nó có thể là an toàn để nói nó thường sẽ lớn hơn so với một liên kết danh sách lưu trữ các dữ liệu tương tự, nhưng nhỏ hơn một Trie. 

Và cố gắng là thứ tư của các cấu trúc rằng chúng ta đang nói về. Chèn vào một Trie là phức tạp. Có rất nhiều động cấp phát bộ nhớ, đặc biệt là ở đầu, như bạn đang bắt đầu xây dựng. Nhưng đó là thời gian liên tục. Đó chỉ là yếu tố con người ở đây mà làm cho nó khó khăn. Có gặp phải con trỏ null, malloc không gian, đến đó, không gian có thể malloc từ đó một lần nữa. Việc sắp xếp các yếu tố đe dọa của con trỏ trong cấp phát bộ nhớ động là rào cản để xóa. Nhưng một khi bạn đã xóa nó, chèn thực sự đi kèm khá đơn giản, và chắc chắn là thời gian liên tục. 

Xóa là dễ dàng. Tất cả bạn cần làm là hướng xuống một vài con trỏ và miễn phí các nút, vì vậy đó là khá tốt. Lookup cũng khá nhanh. Nó chỉ dựa trên chiều dài của dữ liệu của bạn. Vì vậy, nếu tất cả các dữ liệu của bạn là năm chuỗi ký tự, Ví dụ, bạn đang lưu trữ năm chuỗi kí tự trong Trie của bạn, nó chỉ mất năm bước để tìm thấy những gì bạn đang tìm kiếm. Năm chỉ là một yếu tố không đổi, do đó, một lần nữa, chèn, xóa, và tra cứu đây là tất cả thời gian liên tục, hiệu quả. 

Một điều nữa là Trie của bạn là loại thực sự đã được sắp xếp, phải không? Nhờ thế nào chúng tôi yếu tố chèn, bằng cách đi từng chữ của quan trọng, hoặc từng số của key, thường, Trie của bạn kết thúc lên được loại được sắp xếp như bạn xây dựng nó. Nó không thực sự làm cho tinh thần để suy nghĩ về phân loại trong cùng một cách chúng ta nghĩ về nó với mảng, hoặc danh sách liên kết, hoặc các bảng băm. Nhưng trong một số ý nghĩa, bạn Trie được sắp xếp như bạn đi. 

Nhược điểm, tất nhiên, là một Trie nhanh chóng trở nên khổng lồ. Từ mỗi điểm giao nhau, có lẽ bạn have-- nếu key của bạn bao gồm các chữ số, bạn có 10 khác nơi bạn có thể đi đến đâu, có nghĩa là tất cả các nút chứa thông tin về các dữ liệu bạn muốn lưu trữ tại nút đó, cộng với 10 con trỏ. Trong đó, trên CS50 IDE, là 80 byte. Vì vậy, nó ít nhất là 80 byte cho mỗi nút mà bạn tạo ra, và điều đó thậm chí không đếm dữ liệu. Và nếu các nút của bạn là chữ thay vì chữ số, bây giờ bạn có 26 con trỏ từ mọi vị trí. Và 26 lần 8 có lẽ là 200 byte, hoặc một cái gì đó như thế. Và bạn có vốn và lowercase-- bạn có thể nhìn thấy nơi tôi đang đi với điều này, phải không? Các nút của bạn có thể nhận được thực sự lớn, và do đó, các Trie chính nó, tổng thể, có thể có được thực sự lớn, quá. Vì vậy, nếu không gian là ở mức cao phí bảo hiểm trên hệ thống của bạn, một Trie thể không phải là cách đúng đắn để đi, mặc dù lợi ích khác của nó đi vào chơi. Tôi Doug Lloyd. Đây là CS50.