tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Vector - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Vector" cung cấp cho người học các kiến thức: Cấu trúc dữ liệu là gì, vector, chèn phần tử, xóa phần tử, thời gian chạy. | Vector Nguyễn Mạnh Hiển hiennm@ Nội dung 1. Cấu trúc dữ liệu là gì 2. Vector 3. Chèn phần tử 4. Xóa phần tử 5. Thời gian chạy 1. Cấu trúc dữ liệu là gì Cấu trúc dữ liệu Là cách tổ chức dữ liệu trong bộ nhớ máy tính sao cho các thao tác xử lý dữ liệu tìm chèn xóa hiệu quả hơn nhanh hơn tốn ít bộ nhớ hơn . Ví dụ cấu trúc dữ liệu Vector Danh sách liên kết Ngăn xếp Hàng đợi Cây Bảng băm Cài đặt cấu trúc dữ liệu Mỗi cấu trúc dữ liệu được cài đặt bằng một lớp C template T là kiểu phần tử class tên-cấu-trúc-dữ-liệu public Hàm tạo constructor Hàm hủy destructor Các thao tác xử lý Bên ngoài gọi được private Các trường dữ liệu Chỉ dùng nội bộ Các thao tác trợ giúp Chỉ dùng nội bộ 2. Vector Vector Quản lý một dãy phần tử nằm liên tục trong bộ nhớ như mảng một chiều kích thước thay đổi được trong khi kích thước của mảng là cố định sau khi khai báo . Các thao tác chính Chèn và xóa phần tử ở cuối vector Chèn và xóa phần tử ở giữa vector bao gồm đầu vector Lấy kích thước vector Truy nhập phần tử dùng chỉ số Cài đặt vector Chú ý Lớp vector trong thư viện chuẩn C dùng chữ v thường. template size 2 class Vector public capacity 4 Hàm tạo và hàm hủy array Toán tử gán Lấy kích thước vector Truy nhập phần tử dùng chỉ số Các thao tác chèn và xóa 3 8 private int size Kích thước vector số phần tử int capacity Dung lượng vector sức chứa T array Con trỏ tới mảng chứa các phần tử Các thao tác trợ giúp Hàm tạo và hàm hủy initCapacity là dung lượng ban đầu của vector và có giá trị ngầm định bằng 16. Vector int initCapacity 16 size 0 Ban đầu chưa có phần tử nào capacity initCapacity Khởi tạo dung lượng array new T capacity Tạo mảng chứa phần tử Vector delete array Xóa mảng giải phóng bộ nhớ Toán tử gán rhs right-hand side là vector vế phải của phép gán. this là con trỏ tới vector hiện hành tức là vế trái. Vector amp operator Vector amp rhs if this amp rhs Ngăn cản tự sao chép size Đặt kích thước mới capacity Đặt dung lượng mới delete array Xóa mảng hiện tại array