Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: ADT và Véc-tơ - Nguyễn Mạnh Hiển

ADT và Véc-tơ Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn 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) 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... 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)! 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; 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 < v.size(); i++) cout << v[i] << endl; có thể viết lại dùng iterator như sau: for (vector::iterator itr=v.begin(); itr != v.end(); itr++) cout << *itr << endl; 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 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) 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); } 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ố 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ơ 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 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 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; }; 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]; } 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; } Các phương thức của lớp Vector (3) void reserve(int n) { if (n <= theSize) return; T *old = array; array = new T[n]; for (int k = 0; k < theSize; k++) array[k] = old[k]; theCapacity = n; delete[] old; } void push_back(T & x) { if(theSize == theCapacity) reserve(2 * theSize); array[theSize] = x; theSize++; }