Bài giảng điện tử chuyên đề Tin học 12 - Định hướng Khoa học máy tính chân trời sáng tạo

CHÀO MỪNG CÁC EM HỌC SINH ĐẾN VỚI BÀI HỌC!

KHỞI ĐỘNG

Khi làm thủ tục tại các cơ quan hành chính nhà nước, em sẽ gặp các hệ thống xếp hàng tự động (Hình 1). Theo em, các hệ thống này hoạt động theo nguyên tắc nào?

Ø  Nguyên tắc của hệ thống xếp hàng tự động:

Ai đến trước sẽ được xếp hàng trước để xử lí công việc trước

CHUYÊN ĐỀ 1: TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

BÀI 1.1. HÀNG ĐỢI

01 HÀNG ĐỢI

Đọc và tìm hiểu thông tin trong mục 1.SGK-tr.5,6 để trả lời các câu hỏi:

• Hàng đợi là gì? Cơ chế hoạt động của hàng đợi là gì?
• Trình bày các thao tác cơ bản “Thêm vào” và “Lấy ra” trên hàng đợi.
• Khái niệm: Hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.
• Cơ chế hoạt động: căn cứ theo thứ tự các phần tử được thêm vào hàng đợi, gọi là vào trước ra trước (FIFO – First In, First Out).
• THAO TÁC CƠ BẢN

Thảo luận và trả lời câu hỏi củng cố tr.7:

Cho Hình 4 biểu diễn một hàng đợi, hãy cho biết:

1. Phần tử đầu hàng đợi, phần tử cuối hàng đợi.
2. Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử nào?
3. Sau khi thêm vào phần tử “k” vào thì phần tử cuối hàng đợi là phần tử nào?
4. 2. Cho một hàng đợi rỗng, hãy vẽ hình minh họa từng bước thực hiện các thao tác sau: enqueue(1), enqueue(3), enqueue(5), dequeue(), dequeue(), enqueue(7).

KẾT LUẬN

•       Khái niệm: hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.

•       Hai thao tác cơ bản trên hàng đợi: thao tác thêm vào (enqueue) ở cuối hàng đợi (rear) và thao tác lấy ra (dequeue) ở đầu hàng đợi (front). Hai thao tác này thể hiện cơ chế hoạt động “Vào trước - Ra trước” (FIFO – First In, First Out).

02 BIỂU DIỄN VÀ CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG MỘT CHIỀU

a. Biểu diễn hàng đợi bằng mảng một chiều

Quan sát hình 5, nghiên cứu mục 2a SGK-tr.7 để trả lời câu hỏi sau: Cho biết 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 là bao nhiêu?

Phần tử đầu của hàng đợi được đặt vào phần tử có chỉ số front = 0

Phần tử cuối hàng đợi được đặt vào phần tử có chỉ số rear = 6.

Thảo luận và trả lời câu hỏi củng cố tr.7:

1. Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng một chiều là gì?