Bài giảng Kỹ thuật lập trình - Bài 12: Ngăn xếp và Hàng đợi - Lê Gia Minh

Nội dung text: Bài giảng Kỹ thuật lập trình - Bài 12: Ngăn xếp và Hàng đợi - Lê Gia Minh

1. Stack - Queue Ngăn xếp và Hàng Đợi 1
2. Nội dung § Giới thiệu § Chồng-Stack. § Minh họa về sử dụng stack § Hàng đợi - Queue § Sử dụng queue § Tóm tắt. 2
3. Giới thiệu § Mảng thông thường cho phép truy xuất bất kỳ phần tử nào Không hạn chế truy cập. § Có những danh sách hạn chế cách truy cập. § Chồng(stack) chỉ cho phép truy cập 1 chiều : đỉnh stack FILO § Hàng đợi khi mua vé là một danh sách hạn chế cách truy cập : FIFO 3
4. Stack Thêm vào và lấy ra đều từ đỉnh Stack l Chồng (stack) Cơ chế: Khi đã đầy Last In First Out LIFO First in Last Out FILO Thêm vào Lấy ra 4
5. Queue- Hàng đợi Hàng đầy Cơ chế: Vào trước ra trước First In First Out- FIFO 5
6. Stack và ứng dụng l Là kiểu danh sách tuyến tính đặc biệt l Bổ sung và lọai bỏ phần tử luôn ở đỉnh Stack (LIFO) l Ứng dụng trong việc xây dựng compiler l Ứng dụng : khử đệ quy 6
7. Khai báo Stack - Khai báo một stack với mỗi phần tử là int #define MAX 100 typedef struct { int top ; // đỉnh Stack int nodes[MAX]; }Stack ; 7
8. Khai báo Stack (tt) l Khai báo stack mỗi phần tử là một cấu trúc #define MAX 100 typedef struct Stack { typedef struct Sinhvien int top ; { Sinhvien nodes[MAX]; } char Hoten[20]; int Tuoi; }; 8
9. Các thao tác với Stack l Khởi tạo Stack (Init) l Kiểm tra Stack rỗng (Empty) l Kiểm tra Stack đầy (Full) l Thêm một phần tử vào Stack (Push) l Lấy một phần tử từ đỉnh Stack(Pop) 9
10. Khởi tạo (init) l Cho giá trị đỉnh stack (top) là -1 l Khởi tạo mảng nếu là cấp phát động void Init(Stack *ps) { ps top = -1 ; } 10
11. Thao tác Empty l #define TRUE 1 l #define FALSE 0 int isEmpty(Stack *ps) { if (ps top == -1) return TRUE ; return FALSE ; } 11
12. Thao tác kiểm tra Stack Full int isFull(Stack *ps) { if (ps top==MAX-1) return TRUE; return FALSE; } 12
13. Thao tác Push Int Push(Stack *ps , KieuDulieu x) { ; } int Push(Stack *ps , int x) { if (isFull(ps)) return FALSE; ps top = ps top +1 ; ps nodes[ps top] = x ; return TRUE; } 13
14. Thao tác POP KieuDulieu Pop(Stack *ps) { ; } Một giá trị đặc biệt báo thát bại int Pop (Stack *ps) { if (isEmpty(ps) return –MAXINT ; return (ps nodes[ps top ]; } 14
15. Bài toán đổi số l Nhập 1 số long ( thí dụ nhập n=13) và cơ số (thí dụ CoSo=2) , xuất biểu diễn số theo cơ số này. 13 2 1 6 2 0 3 2 Ngưng 1 1 2 chia 1 0 1 1 1 1 1 Lấy ra 0 0 0 0 1 1 1 1 1 15
16. Bài toán đảo chuỗi S l Chuỗi nhập: qwert Chuỗi xuất: trewq l Thư viện string.h có hàm strrev (string reverse) làm điều này. l Có thể tự xây dựng đảo chuỗi bằng stack các ký tự q w e r t while (!isEmpty(ps) { char c; c =Pop(ps); Init(ps); printf(“%c”,c); t int L= strlen (S); r } for (i=0;i<L;i++) e Push( ps , S[i]); w q 16
17. Ký pháp nghịch đảo Balan(RPN) Reverse Polish Notation l Lewinski đã chứng minh rằng mọi biểu thức đều có thể viết dưới dạng hậu tố (postfix notation, toán tử đặt sau toán hạng) và tính toán từ trái sang phải. l Thí dụ: (3+5)*2 3 5+2* Lấy 3 với 5 cộng nhau rồi lấy 2 nhân vào. l Thí dụ ((3+5)*2)3 3 5+2*3$ với $ là ký hiệu của toán tử lũy thừa (do ta chọn). l Thí dụ: ((3*4)+(5*6)+(7*8))*3 3 4*5 6*+7 8*+3* 17
18. Thuật tóan chuyển từ dạng trung tố sang RPN 1. Khởi tạo stack rỗng chứa các tóan tử 2. While(!error && !ketthucchuoi) 1. Đọc TOKEN 2. Nếu TOKEN là : 1. Dấu ngoặc trái : push vào stack 2. Dấu ngoặc phải : lấy ra và hiển thị các phần tử của stack cho đến khi dấu ngoặc trái được đọc(nếu stack rỗng báo lỗi) 3. Một tóan tử : nếu stack rỗng hay TOKEN có độ ưu tiên cao hơn phần tử ở đỉnh stack push TOKEN vào stack - Ngược lại : pop và hiển thị phần tử ở đỉnh stack ; lặp lại việc so sánh TOKEN ơới phần tử ở đỉnh stack 4. Một tóan hạng : hiển thị nó 3. Kết thúc biểu thức trung tố thì lấy từ stack và hiển thị cho đến khi stack rỗng Ngoặc trái có độ ưu tiên thấp nhất 18
19. Hàm tính độ ưu tiên tóan tử int Priority(char Operator) { switch(Operator) { case ‘(‘ : return 0 ; case ‘+’ : case ‘-’ : return 1; case ‘*’ : case ‘/’ : return 2; } } 19
20. Lượng giá biểu thức hậu tố 1. Khởi động Stack rỗng 2. Lặp lại đến khi đọc hết biểu thức hậu tố 1. Đọc TOKEN tiếp theo trong biểu thức RPN 2. Nếu là tóan hạng Push vào Stack, ngược lại nếu là tóan tử , thực hiện các bước sau : 1. Lấy tử đỉnh Stack 2 giá trị ( nếu không đủ thì biểu thức RPN là sai) 2. Áp dụng tóan tử trên cho 2 giá trị vừa lấy ra 3. Đẩy kết quả tính được vào Stack 3. Khi hết biểu thức, trị của RPN là giá trị duy nhất còn lại trong Stack 20
21. Bài tập về Stack l Đổi số từ thập phân ra hệ : 2,8,16 l Viết chương trình lượng giá RPN l Viết chương trình chuyển từ dạng hậu tố sang trung tố : ¡ AB+ A + B ¡ AB+CD-* ((A+B)*(C-D)) 21
22. Queue(Hàng Đợi) 22
23. QUEUE ( Hàng đợi ) l Mô tả hàng đợi l Khởi tạo 1 hàng đợi l Kiểm tra hàng trống l Kiểm tra hàng đầy l Thêm 1 phần tử vào hàng l Lấy phần tử đầu hàng ra. 23
24. Mô tả Hàng đợi l Là một danh sách tuyến tính l Thao tác bổ sung được thực hiện ở 1 đầu gọi là lối vào (rear) l Thao tác lấy một phần tử được thực hiện ở một đầu khác (front) l FIFO (First In First Out) 24
25. Mô tả hàng đợi l Mô tả hàng đợi: Mảng 1 chiều Vị trí lấy ra Vị trí sẽ thêm luôn là 0 phần tử mới ( đầu hàng (biến rear - đợi) đuôi) 25
26. Demo Hàng rỗng : rear = front = -1 3 4 Thêm 5,6,7 lọai bỏ 3,4 front rear 5 6 7 front rear 26
27. Khai báo Queue bằng mảng § #define MAX 10 § typedef int Data; § typedef struct Queue § { § int front , rear ; § Data nodes[MAX]; § }; § void Init(Queue *pq); § int isEmpty(Queue *pq); § void Insert(Queue *pq , Data x); § Data Remove(Queue *pq); § int isFull(Queue *pq); § void PrintQueue(Queue *pq); 27
28. Cài đặt hàng với phương pháp di chuyển tịnh tiến khi hàng bị tràn (tt) l void Init(Queue *pq) l { l pq->front = pq->rear = -1 ; l } l // l int isEmpty(Queue *pq) l { l return (pq->front == -1); l } l // l int isFull(Queue *pq) l { l return ((pq->rear - pq->front + 1)== MAX); l } 28
29. l void Insert(Queue *pq , Data x) l { l if (!isFull(pq)) l { l if (isEmpty(pq)) pq->front = 0 ; l // tinh tien l if (pq->rear == (MAX-1)) l { l memmove(&pq->nodes[0] , &pq->nodes[pq->front] ,( pq- >rear-pq->front +1)*sizeof(Data)); l pq->rear = MAX-(pq->front)-1; l pq->front = 0 ; l } l pq->rear = pq->rear + 1 ; l pq->nodes[pq->rear] = x ; l } l else l { l printf("Hang day \n"); l exit(1); l } l } 29
30. l Data Remove(Queue *pq) l { l int tmp ; l if (!isEmpty(pq)) l { l tmp = pq->front ; l pq->front = pq->front + 1 ; l if (pq->front>pq->rear) Init(pq); l return pq->nodes[tmp]; l } l else l { l printf("Hang rong khong co data \n"); l exit(1); l } l } 30
31. Cài đặt Queue bằng mảng xoay vòng l Khi rear = MAX-1 nhưng Queue chưa đầy : front > 0 Thêm phần tử mới vào vị trí 0 và cứ tiếp tục như vậy. l Vì từ vị trí 0 cho đến front-1 là các vị trí trống 31
32. Kiểm tra hàng đầy int isFull(Queue *pq) { return ((pq->rear – pq->front+ 1)%MAX ==0) } 32
33. Xoa 1 phần tử l Data Remove(Queue *pq) l { l int tmp ; l if (!isEmpty(pq)) l { l tmp = pq->front ; l if (pq->front == pq->rear) Init(pq); l else l { l pq->front = pq->front + 1 ; l if (pq->front==MAX) pq->front = 0; l } l return pq->nodes[tmp]; l } l else l { l printf("Hang rong khong co data \n"); l exit(1); l } l } 33
34. Chen 1 phần tử l void Insert(Queue *pq , Data x) l { l if (!isFull(pq)) l { l if (isEmpty(pq)) pq->front = 0 ; l pq->rear = pq->rear + 1 ; l if (pq->rear == MAX) pq->rear=0 ; l pq->nodes[pq->rear] = x ; l } l else l { l printf("Hang day \n"); l exit(1); l } l } 34
35. In nội dung 1 Queue l void PrintQueue(Queue *pq) l { l int i ; l if (pq->rear>=pq->front) l { l for( i = pq->front ; i rear ; i++) l printf("%d ",pq->nodes[i]); l } l else l { l for(i = pq->front ; i nodes[i]); l for(i = 0 ; i rear ; i++) printf("%d ",pq->nodes[i]); l } l } 35
36. Hàng đợi ưu tiên l Cần xử lý trước các công việc theo một độ ưu tiên nào đó. l Các công việc có độ ưu tiên cao nhất sẽ được thực hiện trước l Các công việc có độ ưu tiên như nhau được thực hiện theo cách “đến trước phục vụ trước Hàng đợi ưu tiên. 36
37. l struct PRINTJOB l { char Machine[20]; l int NumPage; l }; l // l void OutPrintJob( PRINTJOB prnj) l { printf("%-25s%7d\n",prnj.Machine, prnj.NumPage); l } l void main() l { QUEUE Q; clrscr(); l Init(Q,50); l PRINTJOB prnj1= { "May1",10 }; l PRINTJOB prnj2= { "May2",17 }; l PRINTJOB prnj3= { "May5",21 }; l Add(prnj1,Q); l Add(prnj2,Q); l Add(prnj3,Q); l printf("DANH SACH CAC MAY CHO IN\n"); l while (!Empty(Q)) l { PRINTJOB p; l Remove(Q,p); l OutPrintJob(p); l } l getch(); l } 37
38. Bài tập l Mỗi máy trong môi trường Internet được nhận diện bằng một địa chỉ IP (Internet Protocol Address) gồm 4 byte. Mô tả 4 byte này theo dạng: 202.168.9.0 .Ba byte đầu của IP address dùng để nhận dạng mạng mà máy này có kết nối (vì Internet là mạng của các mạng), byte cuối cùng dùng để nhận dạng máy tính này trong mạng. l Một máy client có thể truy xuất từ server 1 tài nguyên (1 file). l Một server nhận nhiều yêu cầu từ client. l Viết chương trình cho biết server sẽ lần lượt phục vụ client theo thứ tự nào và tài nguyên nào. 38