zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Ngôn ngữ lập trình C - Chương 7 - Bài 3. Queue

Chia sẻ: Nguyen Duc Anh | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

141
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Queue (Hàng đợi) - Là một hàng chờ đợi, xếp hàng (waiting line) - Là một cấu trúc dữ liệu trong đó cho phép sử dụng cả 2 phía: một phía để thêm và một phía để lấy ra phần tử

Chủ đề:

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

Lưu

Nội dung Text: Ngôn ngữ lập trình C - Chương 7 - Bài 3. Queue

4/28/2010 Chương 7. Bài 3. Queue ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI Nội dung  1. Khái niệm queue  2. Xây dựng queue  2.1. Sử dụng mảng  2.2. Sử dụng danh sách liên kết 2 1. Khái niệm queue  Queue (Hàng đợi)  Là một hàng chờ đợi, xếp hàng (waiting line)  Là một cấu trúc dữ liệu trong đó cho phép sử dụng cả 2 phía: một phía để thêm và một phía để lấy ra phần tử 3 1
4/28/2010 1. Khái niệm Queue  Dữ liệu được thêm vào ở lối sau lối (rear), và lấy ra ở lối trước trước (front)  Cấu trúc FIFO (First In First Out) – Vào trước ra trước  Thao tác  enqueue(Element e)  Element dequeue() lối sau Các thao tác cơ bản của Queue  enQueue: Thêm một phần tử vào Queue Data D Enqueue A B A B D rear rear front front Queue Queue Các thao tác cơ bản của Queue  deQueue: Lấy một phần tử khỏi Queue Data A Dequeue A B D B D rear rear front front Queue Queue 2
4/28/2010 Ứng dụng của Queue  Hàng đợi trong các phòng bán vé  Truy nhập vào các thiết bị dùng chung tại văn phòng (ví dụ máy in) 7 Ghi nhớ  Queue được hình dung như một hàng đợi bao gồm nhiều nhiều người xếp hàng với 2 thao tác đưa vào và đẩy ra theo nguyên tắc:  Người nào vào trước sẽ được ra trước – FIFO (First In First Out) 2. Xây dựng Queue  Lưu trữ được các đối tượng dữ liệu  Xây dựng 2 thao tác Push và Pop theo nguyên tắc FIFO  Có hai cách cài đặt queue  Sử dụng mảng  Sử dụng danh sách liên kết 3
4/28/2010 2.1. Sử dụng mảng 0 1 2 MAX-1 ... F (Front) R (Rear)  Biễu diễn Queue dưới dạng mảng Q  Lưu trữ chỉ số phần tử lối trước và lối sau của Queue qua biến F và R  Khởi tạo F=R=-1  Queue rỗng (empty) F = R = -1  Queue đầy (full) R=MAX-1 2.1. Sử dụng mảng  Để thuận tiện định nghĩa cấu trúc Queue gồm mảng và 2 biến Front, Rear #define MAX 100 typedef ... ElementType; typedef struct { ElementType Elements[MaxLength]; //Lưu trữ các chỉ số int Front, Rear; } Queue; Queue Q; 11 2.1. Sử dụng mảng  Khởi tạo Queue  Front = -1  Rear = -1  Khi bổ sung thêm một phần tử vào Queue  Nếu Front=-1 thì gán Front=0  Rear tăng lên 1.  Khi lấy ra một phần tử trong Queue  Nếu Front==Rear thì gán Front = Rear = -1  Ngược lại Front tăng lên 1 12 4
4/28/2010 Enqueue int EnQueue(ElementType N){ if(Q.Rear==MAX-1) return 0; else{ if(Q.Front==-1) Q.Front=0; Q.Rear=Q.Rear+1; Q.Elements[Q.Rear]=X; return 1; } 13 } Dequeue int DeQueue(ElementType *N){ if(Q.Front == -1) return 0; else{ *N = Q.Element[Q.Front]; if (Q.Front == Q.Rear){ Q.Front = -1; Q.Rear = -1; }else Q.Front=Q.Front+1; return 1; //Dequeue thanh cong }} 2.1. Sử dụng mảng  Nhược điểm của cách tổ chức lưu trữ này  Hiện tượng ĐẦY (Full) vẫn xảy ra dù mảng Q vẫn còn chỗ nhưng R = MAX-1 0 1 2 MAX-1 ... F (Front) R (Rear) 15 5
4/28/2010 Cải tiến EMPTY QUEUE [2] [1] [2] [1] J2 J3 [0] [3] [0] [3] J1 [5] [4] [5] [4] front = -1 front = 0 rear = -1 rear = 2 Cải tiến [1] [2] [1] [2] J8 J9 J2 J3 J4 [3][0] J7 [0] [3] J1 J6 J5 J5 [5] [4] [5] [4] front =0 front =4 rear = 4 rear = 2 Thêm vào theo chiều kim đồng hồ 2.2. Sử dụng danh sách liên kết Front Rear  Biểu diễn  Front trỏ tới đầu danh sách  Rear: trỏ tới cuối danh sách  Queue là cấu trúc FIFO (First In First Out)  Thao tác Push, Pop? 18 6
4/28/2010 2.2. Sử dụng danh sách liên kết  Push  Thêm một nút vào sau nút cuối cùng trong danh sách  Pop  Lấy giá trị nút đầu tiên trong danh sách  Loại bỏ nút này khỏi danh sách 19 2.2. Sử dụng danh sách liên kết struct node { Front ElemType data; 7 struct node *next; }; 1 struct node *Front, *Rear; //Front, Rear được khai báo 8 là hai biến toàn cục \ Rear enQueue void enQueue(ElemType N){ Front struct node *Temp; Temp=(struct node *) 7 malloc(sizeof(struct node)); Temp->data = N; 1 Temp->next = NULL; if(Front==NULL){ 8 Temp Front = Temp; Rear = Temp; \ }else{ 45 Rear Rear->next = Temp; Rear = Rear - >next; }} 7
4/28/2010 enQueue void enQueue(ElemType N){ Front struct node *Temp; Temp=(struct node *) 7 malloc(sizeof(struct node)); Temp->data = N; 1 Temp->next = NULL; if(Front==NULL){ 8 Temp Front = Temp; Rear = Temp; }else{ 45 Rear Rear->next = Temp; Rear = Rear - >next; }} enQueue void enQueue(ElemType N){ Front struct node *Temp; Temp=(struct node *) 7 malloc(sizeof(struct node)); Temp->data = N; 1 Temp->next = NULL; if(Front==NULL){ 8 Temp Front = Temp; Rear = Temp; }else{ 45 Rear Rear->next = Temp; Rear = Rear - >next; }} deQueue int deQueue(ElementType *N){ Front Temp struct node *Temp=Front; if(Front==NULL) return 0; 7 else{ *N = Front ->data; 1 if(Front==Rear){ Front = NULL;Rear = NULL; 8 }else Front = Front ->next; 45 free(Temp); Rear return 1; } } 8
4/28/2010 deQueue int deQueue(ElementType *N){ Front Temp struct node *Temp=Front; if(Front==NULL) return 0; 7 else{ *N = Front ->data; 1 if(Front==Rear){ Front = NULL;Rear = NULL; 8 }else Front = Front ->next; 45 free(Temp); Rear return 1; } } deQueue int deQueue(ElementType *N){ Front Temp struct node *Temp=Front; if(Front==NULL) return 0; else{ *N = Front ->data; 1 if(Front==Rear){ Front = NULL;Rear = NULL; 8 }else Front = Front ->next; 45 free(Temp); Rear return 1; } } Bài tập  Demo dQueue.c  Bài 1. Kiểm tra tính đối xứng của một xâu  Dùng stack: lưu các kí tự của xâu  Dùng Queue: lưu các kí tự của xâu  Lấy lần lượt khỏi stack và queue các phần tử và so sánh 27 9
4/28/2010 Bài tập  Ví dụ  Đầu vào : MADAM  Bước 1: Đọc xâu từ trái top front sang phải, lưu vào trong MADAM MADAM Stack và Queue Stack Queue M= M  Bước 2: Lấy lần lượt các top front ký tự ra khỏi Stack và MADA ADAM Queue Stack A= A Queue top front MAD DAM Stack Queue Bài tập  Bài 2. Kiểm tra cặp ngoặc Mỗi dấu “(”, “{”, or “[” đều phải có một dấu đóng tương ứng “)”, “}”, or “[”  Đúng: ( )(( )){([( )])}  Sai: )(( ))  Sai: ({[ ])}  Viết giải thuật nhận một xâu đầu vào gồm các ký tự mở , đóng ngoặc. Kiểm tra xâu có hợp lệ không 29 Thảo luận 30 10

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.