Cấu trúc dữ liệu Vector List Stack Queue Tree HashTable Dictionary Véc tơ (Vector) Cấu trúc tuyến tính Cấu trúc tuyến tính là một cấu trúc trong đó các phần | Cấu trúc dữ liệu Vector List Stack Queue Tree HashTable Dictionary Bài 6 Véc tơ (Vector) Cấu trúc tuyến tính Cấu trúc tuyến tính là một cấu trúc trong đó các phần tử nằm trên một đường không có nhánh, và các phần tử liên tiếp nhau. Một số ví dụ: Danh sách (lists) Vector, chuỗi (vectors sequences) Danh sách kiểu ngăn xếp, danh sách kiểu hàng đợi (stack, queue) Cấu trúc tuyến tính Cấu trúc phi tuyến Vector Vectors 5/13/2020 11:04:00 PM Kiểu dữ liệu trừu tượng Vector (Vector ADT) Kiểu dữ liệu trừu tượng Vector là sự mở rộng của khái niệm mảng. Vector là một mảng lưu trữ một dãy các đối tượng với số lượng tùy ý. Một phần tử có thể được truy cập, chèn thêm hoặc loại bỏ đi khi biết chỉ số của nó. Khi thực hiện các thao tác trên có thể xảy ra lỗi nếu chỉ số của phần tử không chính xác (Vd, chỉ số âm) V 0 1 2 n Các thao tác trên Vector Các thao tác chính trên Vector: int getAtRank(integer r, object &o): Trả lại phần tử có chỉ số r, nhưng không loại bỏ nó int . | Cấu trúc dữ liệu Vector List Stack Queue Tree HashTable Dictionary Bài 6 Véc tơ (Vector) Cấu trúc tuyến tính Cấu trúc tuyến tính là một cấu trúc trong đó các phần tử nằm trên một đường không có nhánh, và các phần tử liên tiếp nhau. Một số ví dụ: Danh sách (lists) Vector, chuỗi (vectors sequences) Danh sách kiểu ngăn xếp, danh sách kiểu hàng đợi (stack, queue) Cấu trúc tuyến tính Cấu trúc phi tuyến Vector Vectors 5/14/2020 12:40:36 AM Kiểu dữ liệu trừu tượng Vector (Vector ADT) Kiểu dữ liệu trừu tượng Vector là sự mở rộng của khái niệm mảng. Vector là một mảng lưu trữ một dãy các đối tượng với số lượng tùy ý. Một phần tử có thể được truy cập, chèn thêm hoặc loại bỏ đi khi biết chỉ số của nó. Khi thực hiện các thao tác trên có thể xảy ra lỗi nếu chỉ số của phần tử không chính xác (Vd, chỉ số âm) V 0 1 2 n Các thao tác trên Vector Các thao tác chính trên Vector: int getAtRank(integer r, object &o): Trả lại phần tử có chỉ số r, nhưng không loại bỏ nó int replaceAtRank(integer r, object o, object & o1): Thay thế phần tử có chỉ số r bằng phần tử o và trả lại phần tử bị thay thế int insertAtRank(integer r, object o): Chèn phần tử o vào vị trí r int removeAtRank(integer r, object &o): loại bỏ phần tử tại vị trí r, và trả lại phần tử bị loại bỏ Thêm vào đó là 2 phép toán: int size() cho biết kích thước của Vector và int isEmpty() cho biết Vector có rỗng hay không? Cài đặt Vector bằng mảng Sử dụng mảng V có kích thước N Một biến n lưu trữ kích thước của vector (số phần tử được lưu trữ) Phép toán getAtRank(r,o) được thực hiện trong thời gian O(1) bằng việc trả lại V[r] V 0 1 2 n r Chèn thêm phần tử Phép toán insertAtRank(r, o), Chúng ta cần tạo một ô mới có chỉ số r bằng cách đẩy n-r phần tử từ V[r], , V[n - 1] về sau 1 vị trí Trong trường hợp xấu nhất (r = 0), phép toán thực hiện trong thời gian O(n) V 0 1 2 n r V 0 1 2 n r V 0 1 2 n o r Loại bỏ phần tử Phép toán removeAtRank(r,o), chúng ta cần đẩy n - r - 1 phần tử từ V[r + 1], , .
