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)

Chia sẻ: Mỹ Nhân | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

67
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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)

Vector Nguyễn Mạnh Hiển hiennm@tlu.edu.vn
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 & operator=(Vector & rhs) { if (this != &rhs) { // Ngăn cản tự sao chép size = rhs.size; // Đặt kích thước mới capacity = rhs.capacity; // Đặt dung lượng mới delete[] array; // Xóa mảng hiện tại array = new T[capacity]; // Tạo mảng có chiều dài mới // Sao chép các phần tử từ vế phải sang vế trái for (int i = 0; i < size; i++) array[i] = rhs.array[i]; } this return *this; rhs } vector vế trái = vector vế phải
Kích thước vector và truy nhập phần tử // Lấy kích thước vector (số phần tử hiện có). int getSize() { return size; } // Kiểm tra vector có đang rỗng hay không. Nếu rỗng, trả // về true; nếu có ít nhất một phần tử, trả về false. bool isEmpty() { return (size == 0); } // Truy nhập một phần tử thông qua chỉ số index của nó. T & operator[](int index) { return array[index]; }
3. Chèn phần tử
Tăng dung lượng vector // Đây là thao tác trợ giúp cho các thao tác chèn. // newCapacity là dung lượng mới (phải lớn hơn kích thước). void expand(int newCapacity) { if (newCapacity
Chèn phần tử vào cuối vector // newElement là phần tử mới cần chèn vào cuối vector. void pushBack(T newElement) { // Gấp đôi dung lượng nếu vector đã đầy if (size == capacity) expand(2 * capacity); // Chèn phần tử mới vào ngay sau phần tử cuối cùng array[size] = newElement; array newElement // Cập nhật kích thước chèn vào đây size++; } 3 8 size
Chèn phần tử vào giữa vector // pos (position) là vị trí chèn, có giá trị từ 0 đến size-1. // newElement là phần tử mới cần chèn. void insert(int pos, T newElement) { // Gấp đôi dung lượng nếu vector đã đầy if (size == capacity) expand(2 * capacity); // Dịch chuyển các phần tử ở pos và sau pos sang phải một vị trí; // phải quét ngược từ phải sang trái (for lùi) để tránh ghi đè. for (int i = size; i > pos; i--) array[i] = array[i – 1]; pos = 1 array // Đặt phần tử mới vào vị trí chèn phải dịch 8, 9, array[pos] = newElement; 2, 5 sang phải // Cập nhật kích thước size++; 3 8 9 2 5 } size
4. Xóa phần tử
Xóa phần tử ở cuối vector // Xóa phần tử ở cuối vector. void popBack() { size--; // Giảm kích thước một đơn vị nghĩa // là “quên” phần tử cuối cùng. } // Xóa tất cả các phần tử. void clear() { size = 0; // Đặt kích thước về 0 nghĩa là // “quên” tất cả các phần tử. }
Xóa phần tử ở giữa vector // pos (position) là vị trí của phần tử cần xóa. void erase(int pos) { // Dịch các phần tử nằm sau vị trí xóa sang trái để // lấp đầy chỗ trống để lại do việc xóa. for (int i = pos; i < size - 1; i++) array[i] = array[i + 1]; // Cập nhật kích thước size--; pos = 1 array } phải dịch 9, 2, 5 sang trái 3 8 9 2 5 size
5. Thời gian chạy
Phân tích thời gian chạy • Hàm tạo, hàm hủy: O(1) • Toán tử gán (operator=): O(n)  vì phải sao chép n phần tử. • getSize, isEmpty, operator[]: O(1) • expand: O(n)  vì phải sao chép n phần tử. • pushBack: O(1) • insert: O(n)  vì phải dịch n phần tử sang phải trong trường hợp tồi nhất (chèn vào đầu vector). • popBack: O(1) • clear: O(1) • erase: O(n)  vì phải dịch n - 1 phần tử sang trái trong trường hợp tồi nhất (xóa phần tử đầu tiên).