Cấu trúc dữ liệu Vector là gì

Question

Tôi biết Vector trong C++ và Java, nó giống như mảng động, nhưng tôi không thể tìm thấy bất kỳ định nghĩa chung nào về cấu trúc dữ liệu Vector. Vậy Vector là gì? Vector có phải là một cấu trúc dữ liệu chung (như arrray, stack, queue, tree, ...) hay nó chỉ là một kiểu dữ liệu phụ thuộc vào ngôn ngữ?

Answer 1

Đó là một mảng có không gian được phân bổ động, mỗi lần bạn vượt quá không gian mới này trong bộ nhớ được cấp phát và mảng cũ được sao chép sang bộ nhớ mới. Một cái cũ được giải thoát rồi.

Hơn nữa, vectơ thường phân bổ bộ nhớ nhiều hơn mức cần thiết, vì vậy nó không phải sao chép tất cả dữ liệu khi phần tử mới được thêm vào.

Có vẻ như, danh sách đó tốt hơn nhiều, nhưng không nhất thiết phải như vậy. Nếu bạn không thay đổi vectơ của bạn thường xuyên (về kích thước), thì bộ nhớ cache của máy tính hoạt động tốt hơn nhiều với vectơ, hơn là danh sách, bởi vì chúng liên tục trong không gian bộ nhớ. Nhược điểm là khi bạn có vectơ lớn, bạn cần mở rộng. Sau đó, bạn phải đồng ý sao chép lượng lớn dữ liệu vào một không gian khác trong bộ nhớ.

Còn gì nữa. Bạn có thể thêm dữ liệu mới vào cuối và tới mặt trước của vectơ. Bởi vì Vector là giống như mảng, sau đó mỗi khi bạn muốn thêm phần tử vào đầu của vectơ tất cả các mảng phải được sao chép. Việc thêm các phần tử vào cuối vectơ sẽ hiệu quả hơn nhiều. Không có vấn đề như vậy với danh sách được liên kết.

Vector cho phép truy cập ngẫu nhiên vào dữ liệu được lưu giữ nội bộ của nó, trong khi danh sách, hàng đợi, ngăn xếp thì không.

Answer 2

Từ "vectơ" được áp dụng cho khoa học/lập trình máy tính được mượn từ toán học, điều này có thể làm cho việc sử dụng khó hiểu (thậm chí câu hỏi của bạn có thể là nhiều chủ đề).

Ví dụ đơn giản nhất về vectơ trong toán là dòng số, được sử dụng để dạy toán sơ cấp (đặc biệt là giúp hiển thị số âm, trừ số âm, thêm số âm, v.v ...).

Vectơ là khoảng cách và hướng từ một điểm. Đây là lý do tại sao nó có thể gây nhầm lẫn cho cuộc thảo luận, bởi vì cấu trúc dữ liệu vectơ có thể là ba điểm, X, Y, Z, trong một cấu trúc được sử dụng trong công cụ đồ họa 3D hoặc điểm 2D (chỉ X, Y). Trong bối cảnh đó, phép trừ của hai điểm như vậy dẫn đến một véc-tơ - vec-tơ mô tả khoảng cách và hướng đi từ một trong các toán hạng nguồn đến giá trị kia.

Điều này áp dụng cho lưu trữ, như vectơ stl hoặc vectơ Java, trong bộ nhớ đó được biểu thị bằng khoảng cách từ địa chỉ (nơi địa chỉ bộ nhớ tương tự với một điểm trong không gian hoặc trên một dòng số).

Khái niệm này liên quan đến mảng, vì mảng có thể là lưu trữ được phân bổ cho một véc tơ, nhưng tôi gửi rằng véc tơ là một khái niệm lớn hơn mảng. Một vec-tơ phải bao gồm khái niệm khoảng cách từ điểm bắt đầu và nếu bạn nghĩ về sự khởi đầu của một mảng làm điểm bắt đầu, khoảng cách đến cuối mảng là kích thước của nó.

Vì vậy, cấu trúc dữ liệu đại diện cho một vectơ phải bao gồm kích thước, trong khi mảng không có bộ nhớ để bao gồm kích thước, nó được giả định theo cách được phân bổ. Tức là, nếu bạn phân bổ động mảng, không có cấu trúc dữ liệu nào lưu trữ kích thước của mảng đó, lập trình viên phải giả định rằng kích thước đó hoặc lưu trữ nó trong một số nguyên hoặc dài.

Cấu trúc dữ liệu vectơ (nói thiết kế lớp vectơ) KHÔNG cần lưu trữ kích thước, vì vậy ở mức tối thiểu, sẽ có điểm bắt đầu (cơ sở của mảng hoặc địa chỉ trong bộ nhớ) và một khoảng cách từ điểm đó cho biết kích thước.

Đó thực sự là "RAM" được định hướng, bởi vì có thêm một điểm chưa được mô tả mà phải là một phần của dữ liệu mô tả vectơ - khái niệm về kích thước phần tử. Nếu một vector biểu diễn byte và bộ nhớ thường được tính bằng byte, địa chỉ và khoảng cách (hoặc kích thước) sẽ biểu diễn một vectơ byte, nhưng không có gì khác - và đó là suy nghĩ cấp độ rất máy. Một suy nghĩ cao hơn, về cấu trúc nào đó, có kích thước riêng của nó - giả sử, kích thước của một phao hoặc gấp đôi, hoặc của một cấu trúc hoặc một lớp trong C++. Bất kể kích thước phần tử là gì, bộ nhớ cần thiết để lưu trữ N của chúng đòi hỏi rằng cấu trúc dữ liệu vectơ có một số kiến ​​thức về những gì nó lưu trữ, và nó lớn như thế nào. Đây là lý do tại sao bạn nghĩ về "vectơ dây" hoặc "vectơ điểm". Một vectơ cũng phải lưu trữ kích thước phần tử.

Vì vậy, một cấu trúc dữ liệu vector cơ bản phải có:

Một địa chỉ (điểm khởi đầu)

Một yếu tố kích thước (mỗi điều nó lưu là X byte dài)

Một số yếu tố được lưu trữ (bao nhiêu lần yếu tố kích thước phần tử là kích thước bộ nhớ 'tối thiểu').

Một "giả thiết" quan trọng được tạo trong danh sách 3 mục đơn giản trong cấu trúc dữ liệu vectơ là địa chỉ được cấp phát bộ nhớ, phải được giải phóng tại một số điểm và được bảo vệ khỏi truy cập ngoài phần cuối của vectơ.

Điều đó có nghĩa là có điều gì đó bị thiếu. Để thực hiện công việc lớp vectơ, có một sự khác biệt có thể nhận biết được giữa số lượng ITEMS được lưu trữ trong vectơ và lượng bộ nhớ ALLOCATED cho bộ nhớ đó. Thông thường, như bạn có thể nhận ra từ việc sử dụng vector từ STL, nó có thể "biết" nó có chỗ để lưu trữ 10 mục, nhưng hiện tại chỉ có 2 mục.

Vì vậy, lớp vectơ hoạt động sẽ C haveNG phải lưu trữ lượng cấp phát bộ nhớ. Đây sẽ là cách nó có thể tự mở rộng chính nó - bây giờ nó sẽ có đủ thông tin để mở rộng lưu trữ tự động.

Suy nghĩ qua cách bạn thực hiện hoạt động lớp vectơ mang đến cho bạn cấu trúc dữ liệu cần thiết để vận hành lớp vectơ.