intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Hàng đợi, sử dụng mảng

Chia sẻ: Nguyễn Thị Phương Phương | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST
Báo xấu
115
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các đối tượng trong hàng đợi được sắp thứ tự theo thời gian chúng được chèn vào hàng Đối tượng được lấy ra khỏi hàng đợi là đối tượng được chèn vào trước nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Hàng đợi, sử dụng mảng

  1. Hàng đợi • Cấu trúc dữ liệu hoạt động theo cơ chế first-in first-out (FIFO) • Hai thao tác cơ bản: – Chèn vào hàng đợi: enqueue – Lấy ra khỏi hàng đợi: dequeue • Các đối tượng trong hàng đợi được sắp thứ tự theo thời gian chúng được chèn vào hàng • Đối tượng được lấy ra khỏi hàng đợi là đối tượng được chèn vào trước nhất
  2. Hàng đợi dequeue enqueue A B C D ... M N head of queue tail of queue
  3. Hàng đợi, sử dụng mảng Khai báo cấu trúc hàng đợi Typerdef struct Queue { int *arrQueue; int max; int numItems; int front; int rear; }
  4. Hàng đợi, sử dụng mảng  Thao tác khởi tạo hàng đợi rỗng int InitQueue(Queue &q, int maxItems) { q.arrQueue = new int(maxItems); if(q.arrQueue == Null) return 0; // không cấp phát được bộ nhớ q.max = maxItems; q.numItems = 0; // chưa có phần tử nào trong queue q.front = q.rear = -1; return 1; // khởi tạo thành công }
  5. Hàng đợi, sử dụng mảng  Thao tác kiểm tra hàng đợi rỗng int IsEmpty(const Queue q) { if(q.numItems == 0) return 1; // Queue rỗng return 0; // Queue không rỗng }
  6. Hàng đợi, sử dụng mảng  Thao tác kiểm tra hàng đợi đầy int IsFull(const Queue q) { if(q. numItems == q.max) return 1; // Queue đầy return 0; // Queue không đầy }
  7. Problem • Nếu mảng có kích thước là n, ta có: • Phải thực hiện 11 lần chèn vào, 9 lần lấy ra: enqueue( 0 ) 0 enqueue( 1 ) 0 1 dequeue() 1 enqueue( 2 ) 1 2 enqueue( 9 ) 8 9 dequeue(8) 9 enqueue( 10 ) 9
  8. Trừu tượng mảng
  9. Trừu tượng mảng
  10. Giải pháp • Trở lại đầu dãy: enqueue( 10 ) 10 9 • Yêu cầu: – front chỉ số đầu hàng đợi – rear chỉ số cuối hàng đợi – numItems biến đếm – array_size chiều dài mảng
  11. Hàng đợi, sử dụng mảng  Thao tác EnQueue: thêm 1 phần tử vào cuối hàng đợi int EnQueue(Queue &q, int newItem) { if (IsFull(q)) return 0; // Queue đầy, không thêm vào được q.rear++; if(q.rear == q.max) // tràn giá q.rear = 0; // quay trở về đầu mảng q.arrQueue[q.rear] = newItem; // thêm phần tử vào cuối Queue if(q.numItems == 0) q.front = 0; q.numItems++; return 1; // thêm thành công }
  12. Hàng đợi, sử dụng mảng  Thao tác DeQueue: lấy ra 1 phần tử ở đầu hàng đợi int DeQueue(Queue &q, int &itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không lấy ra được itemout = q.arrQueue[q.front]; // lấy phần tử đầu ra q.front++; q.numItems--; if(q.front == q.max) // nếu đi hết mảng … q.front = 0; // … quay trở về đầu mảng if(q.numItems == 0) q.front = q.rear = -1; return 1; // xóa thành công }
  13. Hàng đợi, sử dụng mảng  Thao tác QueueFront: kiểm tra phần tử ở đầu hàng đợ i int QueueFront(const Queue &q, int &itemout) { if (IsEmpty(q)) return 0; // lấy phần tử đầu ra itemout = q.arrQueue[q.front]; return 1; }
  14. Hàng đợi, sử dụng mảng  Thao tác QueueRear: kiểm tra phần tử ở cuối hàng đợ i int QueueRear(const Queue &q, int &itemout) { if (IsEmpty(q)) return 0; // lấy phần tử cuối ra itemout = q.arrQueue[q.rear]; return 1; }
  15. Applications • Kiểu Client-server : – Một hoặc nhiều clients đang yêu cầu được phục vụ từ một hay nhiều servers – Có thể có nhiều hơn một client đang đợi để được phục vụ tại cùng thời điểm – Các clients trong hàng đợi sẽ được phục vụ theo theo thứ tự thời gian chúng được chèn vào
  16. Application • Một vài ứng dụng dễ nhìn thấy: – Kiểu client-server, khi mà có nhiều hơn một client gởi yêu cầu phục vụ tới một Web server – Ví dụ, một (simple) web server chỉ có thể phục vụ mỗi lần một yêu cầu – Rõ ràng có nhiều yêu cầu hầu như đồng thời được gởi tới từ các trình duyệt – Yêu cầu đầu tiên sẽ được phục vụ, những yêu cầu tiếp theo được đưa vào hàng đợi
  17. Application • Một ứng dụng khác là thực hiện duyệt một cây theo chiều ngang (breadth-first) • Cho trước một cây sau
  18. Application • Giả sử ta muốn liệt kê tất cả nút theo trật tự breadth-first • Ta liệt kê tất cả nút ở một mức trước khi xuống mức tiếp theo
  19. Application • Về điều này, ta cần một vài thuật ngữ: – Nút gốc (root node) – Nút con (child nodes hoặc children)
  20. Application • Việc hiện thực dễ nhất là: – Đặt nút gốc vào hàng đợi – Khi hàng đợi không rỗng: • Lấy nút head ra • chèn tất cả con của nó vào hàng đợi – Trật tự của các phần tử được lấy ra khỏi hàng đợi gọi là trật tự breadth-first
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2