tailieunhanh - BÀI GIẢNG: HÀNG ĐỢI

Hàng đợi cải tiến được biểu diễn là một bản ghi gồm có 2 trường : Trường thứ nhất : là mảng một chiều có kích thước đủ lớn để lưu các phần tử của hàng đợi. Trường thứ hai là số nguyên dùng để lưu chỉ số phần tử cuối hàng đợi trong mảng các phần tử. | HÀNG ĐỢI QUEUE CẤU TRÚC HÀNG ĐỢI Khái niệm, đặc điểm Lưu trữ kế tiếp của hàng đợi Hàng đợi móc nối /52 Khái niệm, đặc điểm của hàng đợi Khái niệm Hàng đợi là một danh sách tuyến tính. Phép toán 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. Phép toán loại bỏ một phần tử khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. /52 Khái niệm, đặc điểm của hàng đợi Phần tử đưa vào hàng đợi trước sẽ được lấy ra xử lí trước, phần tử đưa vào hàng đợi sau sẽ được lấy ra xử lí sau. Được gọi là danh sách FIFO (First - In - First – Out) /52 Khái niệm, đặc điểm của hàng đợi A B C D E F Đầu hàng Cuối hàng Loại bỏ Bổ sung Hình vẽ biểu diễn hàng đợi /52 Lưu trữ kế tiếp của hàng đợi Định nghĩa và khai báo cấu trúc dữ liệu Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản /52 Định nghĩa và khai báo cấu trúc dữ liệu Hàng đợi được biểu diễn là một bản ghi gồm có 3 trường : Trường thứ nhất : là mảng một . | HÀNG ĐỢI QUEUE CẤU TRÚC HÀNG ĐỢI Khái niệm, đặc điểm Lưu trữ kế tiếp của hàng đợi Hàng đợi móc nối /52 Khái niệm, đặc điểm của hàng đợi Khái niệm Hàng đợi là một danh sách tuyến tính. Phép toán 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. Phép toán loại bỏ một phần tử khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. /52 Khái niệm, đặc điểm của hàng đợi Phần tử đưa vào hàng đợi trước sẽ được lấy ra xử lí trước, phần tử đưa vào hàng đợi sau sẽ được lấy ra xử lí sau. Được gọi là danh sách FIFO (First - In - First – Out) /52 Khái niệm, đặc điểm của hàng đợi A B C D E F Đầu hàng Cuối hàng Loại bỏ Bổ sung Hình vẽ biểu diễn hàng đợi /52 Lưu trữ kế tiếp của hàng đợi Định nghĩa và khai báo cấu trúc dữ liệu Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản /52 Định nghĩa và khai báo cấu trúc dữ liệu Hàng đợi được biểu diễn là một bản ghi gồm có 3 trường : Trường thứ nhất : là mảng một chiều có kích thước đủ lớn để lưu các phần tử của hàng đợi Trường thứ hai và thứ ba là số nguyên để lưu chỉ số của phần tử đầu hàng đợi và chỉ số của phần tử cuối hàng đợi trong mảng các phần tử /52 Định nghĩa và khai báo cấu trúc dữ liệu Khai báo cấu trúc : const max = ; struct queue { ptu[max] ; int front, rear ; } q ; /52 Định nghĩa và khai báo cấu trúc dữ liệu A B C D E F 0 1 2 3 4 5 6 7 8 max=10 front = 2 rear = 7 q Mảng lưu trữ hàng đợi /52 Các phép toán cơ bản Khởi tạo hàng đợi rỗng : creat(q) Kiểm tra hàng đợi rỗng : empty(q) Kiểm tra hàng đợi đầy : full(q) Chèn phần tử x vào cuối hàng đợi : add(x,q) Loại phần tử đầu hàng đợi gán cho x : del(q,x) /52 Các phép toán cơ bản Khởi tạo hàng đợi rỗng void creat(queue &q) { = 0; = -1; } /52 Các phép toán cơ bản 0 1 2 3 4 5 6 7 8 front = 0 rear = -1 q Biểu diễn hàng đợi rỗng max=10 9 /52 Các phép toán cơ bản Kiểm tra hàng đợi rỗng int empty(queue q) { return > .