Bài giảng Thuật toán ứng dụng - Chương 2: Cấu trúc dữ liệu và thư viện - Phạm Quang Dũng

Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn THUẬT TOÁN ỨNG DỤNG 1 CẤU TRÚC DỮ LIỆU VÀ THƯ VIỆN 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 4 #include using namespace std; int main(){ list L; for(int i = 1; i<=5;i++){ L.push_back(i); } list::iterator it; it = find(L.begin(),L.end(),3); L.insert(it,10); for(it = L.begin(); it != L.end(); it++){ cout << *it << endl; } } Vector 5 #include using namespace std; int main(){ vector 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] << " "; } } 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 7 #include using namespace std; int main(){ set Y; for(int i = 1; i <= 10; i++){ Y.insert(i); } for(set::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; } Á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ạ 9 #include using namespace std; int main(){ map m; for(int i = 1; i <= 5; i++) m.insert(pair(i,10*i)); m[6] = 100; for(int k = 1; k <= 6; k++) cout << m[k] << endl; map m1; m1["abc"] = "abcabc"; m1["xyz"] = "xyzxyz"; string s = "abc"; cout << m1[s] << endl; } Ánh xạ 10 #include using namespace std; int main(){ map, pair > m2; m2[pair(2,5)] = pair(20,50); m2[pair(3,5)] = pair(30,50); int i = 3; int j = 5; pair p = m2[pair(i,j)]; cout << p.first << "," << p.second << endl; } Ngăn xếp  Cấu trúc dữ liệu cất trữ các đối tượng một cách tuyến tính  Thao tác  Thêm 1 phần tử  Lấy ra 1 phần tử  Nguyên tắc: Vào trước – ra sau 11 Hàng đợi  Cấu trúc dữ liệu cất trữ các đối tượng một cách tuyến tính  Thao tác  Thêm 1 phần tử  Lấy ra 1 phần tử  Nguyên tắc: vào trước – ra trước 12 Stack 13 #include using namespace std; int main(){ stack S; for(int i = 0; i < 5; i++){ S.push(i); } while(!S.empty()){ int v = S.top(); S.pop(); cout << v << endl; }} Queue 14 #include using namespace std; int main(){ queue Q; for(int i = 0; i < 5; i++){ Q.push(i); } while(!Q.empty()){ int v = Q.front(); Q.pop(); cout << v << endl; } } Sắp xếp 15 #include #include using namespace std; int main(){ int N = 6; double a[N] = {1.1, 5.5, 7.7, 2.2, 8.8, 3.3}; sort(a+3,a+N,greater());// decreasing order for(int i = 0; i < N; i++) cout << a[i] << " "; cout << endl; sort(a,a+N); for(int i = 0; i < N; i++) cout << a[i] << " "; }