Link tải luận văn miễn phí cho ae Kết nối
SỬ DỤNG cấu TRÚC HÀNG đợi để xây DỰNG hệ THỐNG QUẢN lý bán vé tàu
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
ĐỀ TÀI 1: SỬ DỤNG CẤU TRÚC HÀNG ĐỢI ĐỂ XÂY DỰNG HỆ THỐNG QUẢN LÝ BÁN VÉ TÀU
I. KHÁI NIỆM HÀNG ĐỢI VÀ CÁC ĐẶC TRƯNG CỦA HÀNG ĐỢI
1. Khái niệm hàng đợi
Hàng đợi là một cấu trúc dữ liệu gần giống với ngăn xếp, nhưng khác với ngăn xếp ở nguyên tắc chọn phần tử cần lấy ra khỏi tập phần tử.
Trái ngược với ngăn xếp, phần tử được lấy ra khỏi hàng đợi không phải là phần tử mới nhất được đưa vào mà là phần tử đã được lưu trong hàng đợi lâu nhất. Quy luật này của hàng đợi còn được gọi là Vào trước – Ra trước (First in – First out).
Như vậy ta có thể định nghĩa hàng đợi là một dạng đặc biệt của danh sách mà việc lấy một phần tử ra được thực hiện ở 1 đầu (gọi là đầu hàng), còn việc bổ sung một phần tử mới được thực hiện ở một đầu (gọi là cuối hàng).
2. Một số thao tác trong hàng đợi
- Enqueue: thêm phần tử vào hàng đợi.
- Dequeue: xóa phần tử khỏi hàng đợi.
- Clear: xóa tất cả phần tử của hàng đợi.
- Count: đếm số phần tử trong hàng đợi.
- IsEmpty: kiểm tra hàng đợi có rỗng hay không.
3. Các đặc trưng của hàm đợi
Thứ tự mà mà theo đó các công việc trong hàng xếp được phục vụ gọi là quy tắc phục vụ. Hầu như các hệ thống xếp hàng ngày nay được sử dụng để phục vụ khách hàng theo trình tự mà chúng tới. Trình tự phục vụ đó là FIFS( First Come First Served). Ngoài ra, còn có một số kiểu phục vụ khác như là:
- LCFS( Last Come First Served) hay LIFO (Last In First Out): Theo đó các khách hàng đến sau sẽ được phục vụ trước.
- LCFSPR( LCFS With Pre- Emptive): Khi khách hàng đến sau nhất sẽ thế chỗ của khách hàng đang được phục vụ xong thì phục vụ có thể tiếp tục đối với khách hàng bị thế chỗ ngay nơi mà nó bị ngắt trước đây, trong trường hợp đó ta có dịch vụ với quyền ưu tiên phục vụ trước – LIFOPR.
- RR(Round Robin): Phục vụ vòng tròn, thời gian tại một tài nguyên được phân chia thành một số khoản nhỏ có độ dài cố định và được gọi là các lượng tử.
II. THUẬT TOÁN
1. Ý tưởng của thuật toán
Các khách hàng đến được sắp xếp vào hàng đợi đến lượt phục vụ. Để đơn giản ta thiết kế một hàng. Các khách hàng được chọn để phục vụ theo nguyên tắc” đến trước phục vụ trước” nghĩa là phục vụ cho khách hàng đứng đầu hàng. Khi khách hàng đứng đầu hàng được phục vụ xong thì đến lượt khách hàng tiếp theo tiến hành thủ tục mua vé. Khi có khách hàng mới đến mua vé thì sẽ được sắp xếp vào hàng đợi rỗng hay hàng đợi chưa đầy.
Cần xây dựng các chức năng cần thiết cho chương trình:
- Khởi tạo hàng đợi
- Kiểm tra hàng đợi có rỗng không
- Thêm một phần tử mới vào hàng, giả sử hàng đợi chưa đầy.
- Loại một phần tử ra khỏi hàng, phần tử bị loại là phần tử đầu hàng, thường là phần tử vừa được xử lý xong.
- Xem phần tử tại đầu hàng
- Phần tử đầu hàng được phục vụ trước
2. Thuật toán
Queue là hàng đợi để lưu các phần tử, có quy tắc phần tử vào trước thì ra trước. Head là vị trí của phần tử đầu tiên trong Queue. Coun: Lưu số lượng các phần tử trong Queue.
Thuật toán ta có thể viết riêng rẻ ra như sau, nếu muốn tổng hợp thì có thể gộp tuần tự các đoạn lại với nhau.
1. Thêm phần tử vào hàng đợi.
B1: if(IsFull()) B3; else B2;
B2: Coun++; Jump(B4);
B3: printf(“Hàng đợi đã full”);
B4: Thoát chương trình.
2. Xóa một phần tử ra khỏi Queue.
B1: If(IsEmpty()) b4;else B2;
B2: Queue[Head].check = false;
B3: Head = (Head+1)%MAX; Coun--; Jump(B5);
B4: printf(“Hàng đợi đã Empty”);
B5: Thoát chương trình.
3. Kiểm tra hàng đợi có Empty hay không?
B1: if(Coun<=0) return true; else return false;
4. Kiểm tra hàng đợi có Full hay không?
B1: if(Coun>MAX) return true; else return false;
5. In một phần tử x của Queue.


56dEpjsk20tEn94

---