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)
17 trang |
Chia sẻ: candy98 | Lượt xem: 1047 | Lượt tải: 1
Bạn đang xem nội dung tài liệu 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, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trê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++;
}