Danh sách các cấu trúc dữ liệu cơ bản - tôi thiếu gì?

Question

Tôi đã nghiên cứu cấu trúc dữ liệu cơ bản của mình một loạt gần đây, cố gắng đảm bảo rằng tôi đã khiến chúng bị lạnh.

Bởi "cơ bản", tôi có nghĩa là những cơ bản thực sự. Những cái ưa thích như Red-Black Trees và Bloom Filters rất đáng được biết, nhưng chúng thường là những cải tiến cơ bản (Red-Black Trees là cây tìm kiếm nhị phân với các thuộc tính đặc biệt để giữ chúng cân bằng) hoặc chúng chỉ hữu ích trong tình huống cụ thể (Bloom Filters).

Cho đến nay, tôi là "thông thạo" trong cấu trúc dữ liệu sau đây:

• Mảng
• danh sách liên kết
• Stacks/Queues
• Binary Search Trees
• Heaps Queues/ưu tiên
• Bàn băm

Tuy nhiên, tôi cảm thấy như tôi đang thiếu một cái gì đó. Có những thứ cơ bản mà tôi quên không?

EDIT: Thêm những sau khi đăng câu hỏi

• Strings (được đề xuất bởi catchmeifyoutry)
• Sets (được đề xuất bởi Peter)
• đồ thị (được đề xuất bởi Nick D và AJ)
• B-Trees (Được đề xuất bởi tloach)
  • Tôi là một chút trên hàng rào về việc liệu những ar e quá ưa thích hay không, nhưng tôi nghĩ rằng chúng đủ khác biệt với các cấu trúc cơ bản (và đủ quan trọng) để có giá trị học tập cơ bản.

Answer 1

Sets

Như một nguyên tắc tôi không bao giờ nói thử [anySearhEngine] vào nó, nhưng bạn có thể kiểm danh sách này: http://en.wikipedia.org/wiki/List_of_data_structures

Answer 2

Bạn đã quên những cái cơ bản: struct, object và enums.

Answer 3

B-Cây và các loại cây khác

Answer 4

Tôi sẽ thêm bản đồ trừ khi bạn muốn xem xét việc đặt trong bộ.

Answer 5

Matrices vì chúng làm cơ sở cho các vấn đề xây dựng mô hình như:

• Đồ thị
• Affine Transformations
• Giải quyết các hệ thống tuyến tính chuỗi
• Markov
• vv

Answer 6

Cũng Graph data structure là cơ bản.

Answer 7

Để được trợ giúp, hãy đọc tài liệu Bộ sưu tập Java. Chúng chia nhỏ mọi thứ thành một tầng trừu tượng (Set, List và Map) và một tầng thực hiện (ArraySet, HashSet, ArrayList, LinkedList, TreeMap, HashMap).

Để được trợ giúp, hãy đọc tài liệu Bộ sưu tập Python. Chúng chia nhỏ mọi thứ thành các lớp cơ sở trừu tượng như Set, Sequence và Map được tạo từ các tính năng mixin của một bộ sưu tập.

Answer 8

Matrices

Graphs

Answer 9

chuỗi, mặc dù họ có thể được thực hiện như mảng dưới mui xe (như một số cấu trúc dữ liệu khác).

Bất kỳ chương trình nào tương tác với người dùng đều sẽ sử dụng chuỗi. Điều quan trọng là phải biết cách thao tác dây.

Answer 10

một số có thể được coi là ít cơ bản hơn những người khác:

• toán học vectơ/matricies
• đồ thị, danh sách kề/matricies
• cố gắng cây tiền tố/hậu tố
• không gian lập chỉ mục - cây quad/kd -trees r-trees
• luồng/chuỗi null chấm dứt chuỗi/lớn ints

Answer 11

Quadtree s, là loại chỉ mục không gian đơn giản nhất.

Answer 12

Bit array không phải là cơ bản nhưng nó là rất tiện dụng và nó có thể lễ bày hiệu quả sử dụng số nguyên (và các nhà khai thác Bitwise)

Answer 13

Bạn có thể xem xét union/find datastructures. Chúng là nền tảng cho một số thuật toán đồ thị.

Answer 14

Mảng kết hợp là cách nói chung của Từ điển, Bản đồ, v.v. Bạn có thể tìm thấy điều này trong hầu hết mọi khung công tác.

http://en.wikipedia.org/wiki/Associative_array

Answer 15

Tuples.

Ngoài ra, nếu tôi có thể chỉ định một cấu trúc dữ liệu không cơ bản, nó sẽ là tiền tố bit phân đoạn liên tục Hash Tries từ Clojure.Nói chung, tôi tin rằng sự bền bỉ là một thuộc tính rất quan trọng và thường bị bỏ qua của bất kỳ cấu trúc dữ liệu nào.

Answer 16

Ô tiêu đề. Với nó, bạn có thể xây dựng nhiều công trình khác dữ liệu (danh sách, cây, vv)

http://en.wikipedia.org/wiki/Cons

Answer 17

tôi nghĩ rằng câu hỏi của bạn không rõ ràng, bởi vì bạn đang trộn thực hiện và mục đích ...

sau loại mô tả thực hiện:

• danh sách liên kết
• đúp danh sách liên kết
• skip list
• mảng
• dynamic array
• bảng băm
• (nhị phân) cây
• "quản lý" (nhị phân) cây (đống, san bằng cây, vv, tức là cây nơi chèn và xóa không được thực hiện trực tiếp nhưng thông qua một thủ tục mà đảm bảo hạn chế nhất định cho cây)
• đồ thị (mặc dù rất ưa thích)

sau mô tả mục đích:

• stack (có nghĩa là Filo & có thể được thực hiện bởi một danh sách liên kết, mà còn với một mảng hoặc vector)
• hàng đợi (có nghĩa là FIFO & có thể được thực hiện bởi một danh sách liên kết đôi, hoặc có thể theo những cách hợp lý khác)
• dequeue (...)
• hàng đợi ưu tiên (có nghĩa là "cao nhất/thấp nhất chính First Out" đây là một khái niệm trừu tượng, mà có thể được thực hiện trong many different ways)
• bản đồ/kết hợp mảng/từ điển (có nghĩa là bạn các khóa bản đồ cho các giá trị. thường yêu cầu một hàm bổ sung để chuyển đổi khóa thành các khóa hợp lệ cho bảng băm hoặc cây bên dưới)
• đặt (có nghĩa là đó là một bộ sưu tập có thể lặp lại và có thể biết được liệu giá trị đó có phải là thành phần của tập hợp hay không). giá trị, đó là một phần tử của bộ phải chính xác một lần trong quá trình lặp, một bộ có thể có thể thay đổi hoặc không (có thể cho phép thêm hoặc loại bỏ các phần tử). .) khi nói đến thực hiện, có một số khả năng)

tốt, có muốn được một điều cuối cùng tôi xem xét rất nhiều điều đáng nói: algebraic data types ... tùy thuộc vào ngôn ngữ, họ hoặc là tồn tại tự nhiên, hoặc bạn phải cạnh tranh với họ ... haXe và C# (theo như tôi đã nghe) sẽ là hai ngôn ngữ bắt buộc cung cấp chúng bằng cách cho phép các thông số cho enums ... chúng có thể được sử dụng để thực hiện danh sách, cây và nhiều thứ đẹp khác ... ví dụ, chúng hoàn hảo để đại diện cho AST và rất nhiều cấu trúc phức tạp khác ...

Answer 18

Không thể triển khai "đối tượng chức năng", "con trỏ hàm" hoặc "đóng cửa" ở một số ngôn ngữ hạn chế có mảng, danh sách được liên kết, vv Nhưng có lẽ chúng gần với các kiểu dữ liệu hơn là cấu trúc dữ liệu.

"rope" implementation (như được triển khai trong thư viện "dây") là triển khai yêu thích của tôi về cấu trúc dữ liệu trừu tượng "chuỗi", nhưng có lẽ nó không thực sự "cơ bản".