Đăng bởi: Admin | Lượt xem: 6470 | Chuyên mục: C/C++
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ại danh sách liên kết đơn.
Ư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.
Đầ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à:
Khai báo list rỗng:
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]
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::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