tailieunhanh - 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)

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ử, | 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 amp 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 amp 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 amp 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ỏ 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 V n 1 về trước một 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 o 0 1 2 r n V 0 1 2 r n V 0 1 2 r n 9 Các ứng dụng của Vector Ứng dụng trực tiếp Lưu trữ tập .