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

CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - HÀNG ĐỢI

Chia sẻ: Lê Ngọc Hoàng | Ngày: | Loại File: PPT | Số trang:19

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

Hàng đợi là một danh sách tuyến tính, trong đó: Việc bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out.

Chủ đề:

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

Lưu

Nội dung Text: CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - HÀNG ĐỢI

  1. HÀNG ĐỢI QUEUE
  2. KHÁI NIỆM đợi là một danh sách tuyến tính,  Hàng trong đó: Việc bổ sung một phần tử vào hàng đợi được thực  hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được  thực hiện ở đầu kia gọi là đầu hàng.  Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out.
  3. KHÁI NIỆM ABCDEF Bổ sung Loại bỏ Đầu hàng Cuối hàng Hình vẽ biểu diễn hàng đợi
  4. BIỂU DIỄN CẤU TRÚC DỮ LIỆU Giả sử các phần tử của HĐ có kiểu dữ liệu là Item, độ dài của  HĐ là N HĐ được lưu trong BNMT bởi mảng 1 chiều (lưu trữ kế tiếp).  Mỗi phần tử của mảng lưu một phần tử của hàng đợi  Hàng đợi được biểu diễn là một cấu trúc có 3 thành phần:  Thành phần thứ nhất là mảng E lưu các phần tử của HĐ  Thành phần thứ hai là biến front lưu chỉ số của phần tử đầu hàng  Thành phần thứ ba là biến rear lưu chỉ số của phần tử cuối hàng  Cấu trúc dữ liệu như sau: 
  5. BIỂU DIỄN CẤU TRÚC DỮ LIỆU 0 1 2 3 4 5 6 7 8 9 = Max-1 A B C D E F E front = 2 rear = 7 Mảng lưu trữ hàng đợi
  6. BIỂU DIỄN CẤU TRÚC DỮ LIỆU #define Max N //Định nghĩa kiểu Item struct Queue{ int front, rear; Item E[Max]; }; Queue Q; /* Q.rear = -1 -> hàng đợi rỗng, Q.rear = Max-1 -> Hàng đợi đầy */
  7. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 1. Khởi tạo hàng đợi rỗng  void Initialize (Queue &Q) { Q.front = 0; Q.rear = -1; } 2. Kiểm tra hàng đợi rỗng  int Empty (Queue Q) { return (Q.rear == -1); }
  8. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI Max=10 0 1 2 3 4 5 6 7 8 9 E front = 0 rear = -1 Biểu diễn hàng đợi rỗng
  9. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 3. Kiểm tra hàng đợi đầy  int Full (Queue Q) { reurn (Q.rear == Max-1); } 10 = Max 0 1 2 3 4 5 6 7 8 9 A B C D E F G H E front = 2 rear = 9 Biểu diễn hàng đợi đầy
  10. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 4. Bổ sung một phần tử vào cuối hàng đợi  10 = Max 0 1 2 3 4 5 6 7 8 9 A B C D E F E X G front = 2 rear = 7 Mảng lưu trữ hàng đợi
  11. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 4. Bổ sung một phần tử vào cuối hàng đợi  10 = Max 0 1 2 3 4 5 6 7 8 9 A B C D E F E X G front = 2 rear = 8 Mảng lưu trữ hàng đợi
  12. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 4. Bổ sung một phần tử vào cuối hàng đợi  10 = Max 0 1 2 3 4 5 6 7 8 9 A B C D E F G E front = 2 rear = 8 Mảng lưu trữ hàng đợi
  13. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 4. Bổ sung một phần tử vào cuối hàng đợi  int AddQ(Queue &Q, Item X) { If (Full(Q)) return 0; else { Q.rear++; Q.E[Q.rear] = X; return 1; } } Hàm AddQ thực hiện bổ sung một phần tử vào cuối hàng, hàm trả về 1 nếu bổ sung thành công, ngược lại hàm trả về 0
  14. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 5. Lấy ra một phần tử ở đầu hàng đợi  Trường hợp hàng đợi có nhiều hơn 1 phần tử  10 = Max 0 1 2 3 4 5 6 7 8 9 A B C D E F E X front = 2 rear = 7 Mảng lưu trữ hàng đợi
  15. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 5. Lấy ra một phần tử ở đầu hàng đợi  Trường hợp hàng đợi có nhiều hơn một phần tử  10 = Max 0 1 2 3 4 5 6 7 8 9 B C D E F E X A front = 3 rear = 7 Mảng lưu trữ hàng đợi
  16. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 5. Lấy ra một phần tử ở đầu hàng đợi  Trường hợp hàng đợi có 1 phần tử  10 = Max 0 1 2 3 4 5 6 7 8 9 B E rear = 3 X front = 3 Mảng lưu trữ hàng đợi
  17. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 5. Lấy ra một phần tử ở đầu hàng đợi  Trường hợp hàng đợi có 1 phần tử  10 = Max 0 1 2 3 4 5 6 7 8 9 E B front = 0 rear = -1 X Hàng đợi rỗng
  18. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 5. Lấy ra một phần tử ở đầu hàng đợi  int DeleteQ(Queue &Q, Item &X) { if (Empty(Q)) return 0; else { X = Q.E[Q.front]; if (Q.front == Q.rear) Initialize(Q); else Q.front = Q.front + 1; return 1; } } Hàm DeleteQ thực hiện lấy ra một phần tử ở đầu hàng, hàm trả về 1 nếu lấy ra thành công, ngược lại hàm trả về 0
  19. ỨNG DỤNG  Viết chương trình: Nhập một chuỗi ký tự, sử dụng hàng đợi,  việc nhập kết thúc khi gõ Enter In chuỗi ra màn hình  Đếm các nguyên âm trong chuỗi 
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