Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 5: ADT và Véc-tơ

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 5: ADT và Véc-tơ

1. ADT và Véc-tơ Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Kiểu dữ liệu trừu tượng (Abstract Data Type – ADT) • Một ADT bao gồm: − một tập các dữ liệu − một tập các thao tác trên những dữ liệu đó • ADT không chỉ rõ các thao tác phải được cài đặt như thế nào • Ví dụ ADT: véc-tơ, danh sách liên kết, ngăn xếp, hàng đợi, cây nhị phân tìm kiếm, cây AVL, bảng băm, hàng đợi ưu tiên (đống)
3. ADT danh sách (List) • Dữ liệu: − Các phần tử A0, A1, , AN-1 − Kích thước danh sách N • Các thao tác (tùy thuộc người thiết kế): − printList // in danh sách − makeEmpty // xóa rỗng danh sách − find // tìm một phần tử − insert // chèn một phần tử mới − remove // xóa một phần tử − v.v
4. Duyệt các phần tử trong ADT • Một số ADT (như véc-tơ) hỗ trợ chỉ số: for (int i = 0; i < v.size(); i++) cout << v[i] << endl; • Nhưng các ADT khác (như danh sách liên kết) không hỗ trợ chỉ số cần một cơ chế chung để duyệt các phần tử đó là iterator (bộ lặp)!
5. Iterator • Một kiểu dữ liệu cho phép duyệt qua các phần tử của ADT • Các thao tác cần có đối với một iterator: − Khởi tạo ở đầu hoặc cuối danh sách phần tử − Dịch sang vị trí liền trước hoặc liền sau − Phát hiện điểm kết thúc lặp − Truy vấn phần tử hiện hành • Trong thư viện STL (Standard Template Library) của C++, iterator được cài đặt ở bên trong các ADT • Ví dụ: − Kiểu iterator của vector : vector ::iterator itr; − Kiểu iterator của list : list ::iterator itr;
6. Lấy về iterator • Trong thư viện STL của C++, có hai cách: − iterator begin(): Trả về iterator tới phần tử đầu tiên − iterator end(): Trả về iterator biểu diễn điểm kết thúc (ở ngay sau phần tử cuối) • Ví dụ: for (int i = 0; i ::iterator itr=v.begin(); itr != v.end(); itr++) cout << *itr << endl;
7. Các phương thức của iterator • Nhiều phương thức dùng nạp chồng toán tử (operator overloading): − itr++ và ++itr dịch iterator sang vị trí kế tiếp − *itr trả về phần tử đang được iterator tham chiếu − itr1 == itr2 true nếu itr1 và itr2 tham chiếu đến cùng vị trí, và false nếu ngược lại − itr1 != itr2 true nếu itr1 và itr2 tham chiếu đến các vị trí khác nhau, và false nếu ngược lại
8. Các thao tác của ADT dùng iterator • Thêm phần tử iterator insert(iterator pos, const Object & x) − Chèn x vào trước pos − Trả về iterator biểu diễn vị trí của x • Xóa phần tử iterator erase(iterator pos) − Xóa phần tử ở vị trí pos − Trả về iterator biểu diễn vị trí của phần tử sau pos • Xóa các phần tử trong một khoảng iterator erase(iterator start, iterator end) − Xóa các phần tử từ start đến end (không bao gồm end)
9. Ví dụ iterator • Xóa tất cả các phần tử trong danh sách template void removeAll(Container & lst) { typename Container::iterator itr = lst.begin(); while (itr != lst.end()) itr = lst.erase(itr); }
10. ADT danh sách dưới dạng véc-tơ • Véc-tơ mở rộng khái niệm mảng − Lưu trữ một dãy phần tử có 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) − Vẫn hỗ trợ truy nhập các phần tử thông qua chỉ số
11. Lớp vector trong thư viện STL của C++ • Các phần tử có kiểu chung Object nào đó • Các thao tác: − int size(): trả về số phần tử − void clear(): xóa tất cả các phần tử − bool empty(): trả về true nếu véc-tơ rỗng − void push_back(const Object & x): thêm x vào cuối véc-tơ − void pop_back(): xóa phần tử ở cuối véc-tơ − Object & back(): trả về phần tử ở cuối véc-tơ − Object & front(): trả về phần tử ở đầu véc-tơ
12. Lớp vector trong STL (tiếp) • Các thao tác khác: − Object & operator[] (int index) • Trả về hoặc gán giá trị ở vị trí index − int capacity() • Trả về dung lượng của véc-tơ ( số phần tử) • Số phần tử véc-tơ có thể chứa mà không phải cấp phát thêm bộ nhớ − void resize(int newSize, const Object & val = Object()) • Thay đổi kích thước của véc-tơ • Các phần tử mới tạo được khởi tạo giá trị bằng val
13. Cài đặt véc-tơ • Đặt tên lớp là Vector với chữ V lớn để phân biệt với lớp vector với chữ v nhỏ trong STL • Các dữ liệu: − Một mảng C++ thông thường − Dung lượng véc-tơ (capacity) − Số phần tử hiện có trong véc-tơ (size) • Các thao tác: − Hàm tạo sao chép (copy constructor) − Toán tử gán (operator=) − Hàm hủy để giải phóng mảng bên trong véc-tơ − Các thao tác khác đã thấy trước đây
14. Cấu trúc của lớp Vector template class Vector { public: // Các phương thức sẽ được viết ở đây typedef T * iterator; private: int theSize; int theCapacity; T *array; };
15. Các phương thức của lớp Vector (1) Vector(int initialSize = 0) : theSize(initialSize), theCapacity(initialSize + 16) { array = new T[theCapacity]; } ~Vector(){ delete[] array; } void pop_back() { theSize ; } iterator begin() { return array; } iterator end() { return array + theSize; } T & operator[](int index) { return array[index]; }
16. Các phương thức của lớp Vector (2) const Vector & operator=(const Vector &rhs) { if(this != &rhs) // ngăn cản tự sao chép { delete[] array; theSize = rhs.theSize; theCapacity = rhs.theCapacity; array = new T[theCapacity]; for(int k = 0; k < theSize; k++) array[k] = rhs.array[k]; } return *this; }
17. Các phương thức của lớp Vector (3) void reserve(int n) void push_back(T & x) { { if (n <= theSize) if(theSize == theCapacity) return; reserve(2 * theSize); T *old = array; array[theSize] = x; array = new T[n]; theSize++; for (int k = 0; k < theSize; k++) } array[k] = old[k]; theCapacity = n; delete[] old; }