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

Bài giảng Cấu trúc hàng đợi (Queue)

Chia sẻ: Trần Hoàng Huân | Ngày: | Loại File: PDF | Số trang:15

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

Bài giảng "Cấu trúc hàng đợi - Queue" giới thiệu đến các bạn những nội dung về khái niệm hàng đợi, phép toán trên hàng đợi, cài đặt hàng đợi bằng mảng, cài đặt hàng đợi bằng dữ liệu liên kết,.. Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích cho các bạn.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc hàng đợi (Queue)

  1. CẤU TRÚC HÀNG ĐỢI (QUEUE) Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin & Truyền thông Đại học Cần Thơ
  2. KHÁI NIỆM HÀNG ĐỢI  Là một dạng danh sách ñặc biệt mà việc thêm phần tử chỉ thực hiện tại một ñầu, gọi là cuối hàng; việc loại bỏ phần tử thực hiện ở ñầu kia, gọi là ñầu hàng.  Làm việc theo nguyên tắc FIFO(First In First Out).
  3. PHÉP TOÁN TRÊN HÀNG ĐỢI  MAKENULL_QUEUE(Q): khởi tạo hàng ñợi rỗng.  EMPTY_QUEUE(Q): kiểm tra hàng ñợi rỗng.  FULL_QUEUE(Q): kiểm tra hàng ñợi ñầy.  FRONT(Q): nội dung phần tử ñầu hàng.  ENQUEUE(X,Q): thêm phần tử X vào cuối hàng ñợi Q.  DEQUEUE(Q): xóa phần tử ở ñầu hàng ñợi.
  4. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG front rear  Mô hình lưu trữ:  Khai báo: 0 1 2 3 …. maxlength-1 #define . . . MaxLength typedef ... ElementType; typedef struct{ ElementType Elements[MaxLength]; int front, rear; } Queue; Queue Q;
  5. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Hàng ñầy: front rear 0 1 2 3 …. maxlength-1  Hàng tràn: front rear 0 1 2 3 …. maxlength-1  Sử dụng bộ nhớ không hiệu quả. Phải xử lý hàng tràn.
  6. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Xử lý hàng tràn bằng mảng tịnh tiến: rear front 0 1 2 … maxlength-1 front rear  Xử lý hàng tràn bằng mảng vòng:
  7. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Khởi tạo hàng rỗng void MakeNull_Queue(Queue *Q){ Q->Front = -1; Q->Rear = -1; }
  8. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Kiểm tra hàng rỗng int Empty_Queue(Queue Q){ return Q.Front == -1; }
  9. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Kiểm tra hàng ñầy int Full_Queue(Queue Q){ return (Q.Rear-Q.Front+1) % MaxLength == 0; }
  10. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Nội dung phần tử ñầu hàng: ElementType Front(Queue Q){ if (Empty_Queue (Q)) printf(“Loi ! Hang doi rong”); else return Q.Element[Q.Front]; }
  11. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Xóa phần tử ñầu hàng:
  12. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Xóa phần tử ñầu hàng: void DeQueue(Queue *Q){ if (Empty_Queue(*Q)) printf("Loi: Hang rong!"); else if (Q->Front == Q->Rear) MakeNull_Queue(Q); else Q->Front=(Q->Front+1) % MaxLength; }
  13. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Thêm phần tử vào cuối hàng:
  14. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG  Thêm phần tử vào cuối hàng: void EnQueue(ElementType X,Queue *Q){ if (Full_Queue(*Q)) printf("Loi: Hang day!"); else{ if (Empty_Queue(*Q)) Q->Front = 0; Q->Rear = (Q->Rear+1) % MaxLength; Q->Elements[Q->Rear] = X; } }
  15. CÀI ĐẶT HÀNG ĐỢI BẰNG DSLK front rear
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
52=>1