Thư viện list trong C++
Khái niệm :List là một danh sách chứa các đối tượng (các nút(node) lưu trữ các thông tin dữ liệu và địa chỉ của nút kế tiếp, nút trước đó) liên kết với nhau và cho phép chèn thêm hay xóa bất kì một đối tượng nào trong danh sách. Là một cấu trúc dữ liệu cơ bản để biết thêm các bạn tham khảo tạidanh sách liên kết đơn. Ưu và nhược điểm :Ưu điểm :chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container nếu biết được interator trỏ đến phần tử đó, (với độ phức tạp là O(1)). Nếu chưa biết interator của phần tử cần xóa hoặc ở vị trí cần chèn thì có thể tìm iterator đó thông qua begin() hoặc end(). Nhược điểm :khả năng truy cập tới phần tử, nó không thể truy xuất A[0] hay A[3] được mà phải thông qua vị trí đầu hoặc cuối của list. ( với độ phức tạp là O(n)). **Lưu ý :end() không phải là iterator trỏ tới phần tử cuối cùng mà trỏ tới sau phần tử cuối cùng. Ví dụ cơ bản :Đầu tiên ta phải khai báo thư viện : Một số cách khai báo list thường dùng là: list tên_list;
// ví dụ list a; Khai báo list khi biết trước size của nó: list tên_list(Size);
//ví dụ list a(5); a =[0,0,0,0,0] Khai báo list khi biết trước size và giá trị khởi tạo: list tên_list(Size,value);
//ví dụ list a(3,2); a =[2,2,2] Khi duyệt các phần tử trong list chúng ta phải làm quen với 1 kiểu dữ liệu là iterator, hiểu đơn giản thì đây là một con trỏ. for (list::iterator it = a.begin(); it !=a.end(); it++) VD1 : Cho một số tự nhiên n. Hãy khởi tạo một list chứa lần lượt các số nguyên từ 1 đến n list initList(int n)
{
list a;
for (int i = 1; i <= n; i++){
a.push_back(i);
}
return a;
}
vector verifyFunction(int n)
{
list lst = initList(n);
vector res(lst.begin(), lst.end());
return res;
} VD2 :Cho một listlinegồm các số nguyên. Hãy tính tổng phẩn tử đầu tiên và phần tử cuối cùng trong list đó, nếu list rỗng trả về-1, còn nếu list chỉ có một phần tử thì trả về phần tử đó.
** Lưu ý :Trong list không thể truy vấn đến các phần tử giống như mảng và vector, không thể sử dụng như a[0], a[1], a[2], int sumOfFirstAndLastElement(list linkedList)
{
if (linkedList.size() == 0) return -1;
if (linkedList.size() == 1) return linkedList.front();
return linkedList.front() + linkedList.back();
}
int verifyFunction(vector v)
{
list l(v.begin(), v.end());
return sumOfFirstAndLastElement(l);
} Bài sau chúng ta sẽ tiếp tục với bài tập về List để hiểu sâu hơn. Chúc các bạn học vui vẻ <3 |
