Bài 3: List - Khái niệm cơ bản - Sử dụng thư viện chuẩn STL cho C/C++

Đăng bởi: Admin | Lượt xem: 10801 | Chuyên mục: C/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. Là một cấu trúc dữ liệu cơ bản để biết thêm các bạn tham khảo tại danh sá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 :

#include<list>

Một số cách khai báo list thường dùng là:

Khai báo list rỗng:

list<kiểu_dữ_liệu> tên_list;
// ví dụ list<int> a;

Khai báo list khi biết trước size của nó:

list<kiểu_dữ_liệu> tên_list(Size);
//ví dụ list<int> 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<kiểu_dữ_liệu> tên_list(Size,value);
//ví dụ list<int> a(3,2); a =[2,2,2]

Duyệt list:

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<int>::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<int> initList(int n)
{
	list<int> a;
	for (int i = 1; i <= n; i++){
		a.push_back(i);
	}
	return a;
}

vector<int> verifyFunction(int n)
{
	list<int> lst = initList(n);
	vector<int> res(lst.begin(), lst.end());
	return res;
}

VD2 : Cho một list line gồ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ử đó.

Gợi ý :

Với line = [1, 2, 3, 4], thì verifyFunction(line) = 5.
Với line = [7], thì verifyFunction(line) = 7.
Để lấy giá trị đầu tiên trong list, ta dùng hàm front().
Để lấy giá trị cuối cùng trong list, ta dùng hàm back().
Để kiểm tra list có rỗng hay không, ta dùng hàm empty() (hàm trả về true nếu list rỗng, ngược lại trả về false).
Để lấy kích thước (số phần tử) của list, ta dùng hàm size().

** 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],

Code mẫu :

int sumOfFirstAndLastElement(list<int> linkedList)
{
   if (linkedList.size() == 0) return -1;
   if (linkedList.size() == 1) return linkedList.front();
   return linkedList.front() + linkedList.back(); 
}

int verifyFunction(vector<int> v)
{
	list<int> 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

Bài tiếp theo: Các hàm thông dụng của List >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!