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ơ
Bạn đang xem tài liệu "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ơ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
bai_giang_cau_truc_du_lieu_giai_thuat_data_structures_algori.pdf
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ơ
- 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 ::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) 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; }