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

Bài giảng "Cấu trúc dữ liệu và giải thuật: ADT và Véc-tơ" trình bày các nội dung: Kiểu dữ liệu trừu tượng, ADT danh sách, duyệt các phần tử trong ADT, lấy về iterator, các phương thức của iterator, các thao tác của ADT dùng iterator,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: ADT và Véc-tơ - Nguyễn Mạnh HiểnADT và Véc-tơNguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnKiể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 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 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ạiCá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 valCà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 đâyCấ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) // ...