Thuật toán ứng dụng Samsung - Cấu trúc dữ liệu và giải thuật (ET2100) | Trường Đại học Bách khoa Hà Nội
Deque – Hàng đợi hai đầu (Double-Ended Queue)
Môn: Cấu trúc dữ liệu và giải thuật (ET2100)
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
Tài liệu liên quan:
Preview text:
lOMoAR cPSD| 27879799 DATA STRUCTURES
1. Deque – Hàng đợi hai đầu (Double-Ended Queue) #include Deque myQueue;
- Hỗ trợ phương thức của kiểu vector và list Size(): kích thước Front() phần tử đầu Back() phần tử cuối
Push_front() thêm vào đầu Push_end() thêm vào cuối Pop_front() xóa đầu Pop_back() xóa cuối 2. Biểu diễn tập hợp Tập rỗng: 0
Tập có một phần tử: 1 << i
Tập vũ trụ (Tất cả các phần tử): (1 << i) – 1 Giao: x & y Hợp: x | y
Phần bù 1 tập: x & ((1 << i) – 1)
VD: Ktra một phần tử xuất hiện trong tập: If (x & (1 << i)) { //yes } else { // no }
3. Stack (Vào sau – Ra trước) - Ứng dụng:
Xử lý bài toán theo thứ tư: vào sau ra trước Khử đệ quy Tìm kiếm chiều sâu Đảo ngược chuỗi lOMoAR cPSD| 27879799 Ktra dãy ngoặc
4. Queue( vào trước ra trước) - Ứng dụng:
Xử lý vào trước ra trước Tìm kiếm chiều rộng
Đường đi qua ít cạnh nhất Thuật toán loang 5. Priority_Queue
Ưu 琀椀 ên gtri sử dụng tốt nhất
Tìm đường đi ngắn nhất trên đồ thị Cây khung min (Prim) Tham lam 6. Map Giá trị + Khóa Bảng tần suất
Mảng lưu trữ trong Quy hoạch động EXHAUSTIVE SEARCH 1. Đệ quy: Void Try(input) { If ()
// trả về kq trường hợp cơ sở } else { // Bước đệ quy Foreach () Call Try(new_input); Combine() Return solu 琀椀 on; } } lOMoAR cPSD| 27879799 2. Pp giải:
- Duyệt toàn bộ (Brute force – Exhaus 琀椀 ve search) - Chia để trị - Qui hoạch động - Tham lam