Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 6: Véc tơ (Vector)" cung cấp cho người học các kiến thức: Cấu trúc tuyến tính, kiểu dữ liệu trừu tượng Vector, các thao tác trên Vector, chèn thêm phần tử, loại bỏ phần tử, nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 6: Véc tơ (Vector) Cấu trúc dữ liệu -Vector -List -Stack -Queue -Tree -HashTable -Dictionary 1 Bài 6 Véc tơ (Vector) 2 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ử Cấu trúc nằm trên một đường không tuyến tính có nhánh, và các phần tử liên tiếp nhau. Một số ví dụ: Danh sách (lists) Cấu trúc phi Vector, chuỗi (vectors, tuyến sequences) Danh sách kiểu ngăn xếp, danh sách kiểu hàng đợi (stack, queue) 3 Vector 4 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 ý. V 0 1 2 n 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) 5 Các thao tác trên Vector int getAtRank(int r, object &o): Trả lại phần tử có chỉ số r, nhưng không loại bỏ nó int replaceAtRank(int 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(int r, object o): Chèn phần tử o vào vị trí r int removeAtRank(int 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ỏ int size() cho biết kích thước của Vector int isEmpty() cho biết Vector có rỗng hay không? 6 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 r n 7 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 r n V 0 1 2 r n V o 0 1 2 r n 8 Loại bỏ
