THUẬT TOÁN ỨNG DỤNG CẤU TRÚC DỮ LIỆU VÀ THƯ VIỆN 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn NộI dung  Danh sách tuyến tính  Tập hợp  Ánh xạ  Ngăn xếp  Hàng đợi  Sắp xếp 2 Danh sách tuyến tính  Lưu trữ các đối tượng theo quan hệ tuyến tính (trước – sau)  Thao tác: thêm, xóa, tìm kiếm 3 List #include <bits/stdc++.h> using namespace std; int main(){ list<int> L; for(int i = 1; i<=5;i++){ L.push_back(i); } list<int>::iterator it; it = find(L.begin(),L.end(),3); L.insert(it,10); for(it = L.begin(); it != L.end(); it++){ cout << *it << endl; } } 4 Vector #include <bits/stdc++.h> using namespace std; int main(){ vector<int> V(3,100); // initialize 3 elements 100 for(int v = 0; v <= 10; v++) V.push_back(v); cout << "vector: "; for(int i = 0; i < V.size(); i++){ cout << V[i] << " "; } } 5 Tập hợp  Lưu các đối tượng, không trùng nhau  Thao tác: thêm, xóa, tìm kiếm 6 Tập hợp #include <bits/stdc++.h> using namespace std; int main(){ set<int> Y; for(int i = 1; i <= 10; i++){ Y.insert(i); } for(set<int>::iterator it = Y.begin(); it != Y.end(); it++){ cout << *it << endl; } if(Y.find(7) != Y.end()) cout << "Y contains 7" << endl; else cout << "Y does not contains 7" << endl; } 7 Ánh xạ  Cấu trúc dữ liệu cất trữ các cặp (khóa, giá trị)  Phục vụ tìm kiếm nhanh với khóa đầu vào 8 Ánh xạ #include <bits/stdc++.h> using namespace std; int main(){ map<int,int> m; for(int i = 1; i <= 5; i++) m.insert(pair<int,int>(i,10*i)); m[6] = 100; for(int k = 1; k <= 6; k++) cout << m[k] << endl; map<string, string> m1; m1["abc"] = "abcabc"; m1["xyz"] = "xyzxyz"; string s = "abc"; cout << m1[s] << endl; } 9 fb.com/g