intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Ngăn xếp và hàng đợi - Nguyễn Minh Huy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST
Báo xấu
10
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Ngăn xếp và hàng đợi, được biên soạn gồm các nội dung chính sau Tổng quan về ngăn xếp; tổng quan về hàng đợi. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Ngăn xếp và hàng đợi - Nguyễn Minh Huy

  1. Ngăn x p và Hàng đ i GV. Nguy n Minh Huy K thu t l p trình - Nguy n Minh Huy 1
  2. N i dung T ng quan v ngăn x p. p. T ng quan v hàng đ i. i. K thu t l p trình - Nguy n Minh Huy 2
  3. N i dung T ng quan v ngăn x p.p. T ng quan v hàng đ i. i. K thu t l p trình - Nguy n Minh Huy 3
  4. T ng quan v ngăn x p Khái ni m ngăn x p: p: Dãy ph n t ho t đ ng theo cơ ch LIFO. Cơ ch LIFO (Last In First Out). (L Th t vào sau ra trư c. c. Vào sau Ra trư c Truy xu t t do M ng 5 7 2 6 5 7 Truy xu t tu n t 2 6 data data head next next NULL Ngăn x p K thu t l p trình - Nguy n Minh Huy 4
  5. T ng quan v ngăn x p Các thao tác trên ngăn x p: p: push: thêm ph n t . pop: l y ph n t . push pop peek: đ c ph n t . 8 5 empty: ki m tra r ng. ng. peek 5 full: ki m tra đ y. y. 7 2 6 Ngăn x p K thu t l p trình - Nguy n Minh Huy 5
  6. T ng quan v ngăn x p Cài đ t ngăn x p trong C: Khai báo và kh i t o: o: // Dùng m ng đ ng. ng. // Dùng danh sách liên k t đơn. đơn. struct Stack struct Stack { { int *data; SNode *head; int top; }; int size; }; void stack_init(Stack &s, int initSize) stack_init(Stack initSize) void stack_init(Stack &s) stack_init(Stack { { s.size = initSize; initSize; head = NULL; s.data = new int[initSize]; int[initSize] } s.top = 0; } K thu t l p trình - Nguy n Minh Huy 6
  7. T ng quan v ngăn x p Cài đ t ngăn x p trong C: Ki m tra r ng và đ y: y: // Dùng m ng đ ng. ng. // Dùng danh sách liên k t đơn. đơn. bool stack_empty(Stack s) stack_empty(Stack bool stack_empty(Stack s) stack_empty(Stack { { return s.top == 0; return s.head == NULL; } } bool stack_full(Stack s) stack_full(Stack { return s.top == size; } K thu t l p trình - Nguy n Minh Huy 7
  8. T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: Thêm ph n t : stack_push. stack_push. Dùng m ng đ ng Dùng danh sách liên k t đơn Thêm đ u x data x next data 5 7 data data head next next NULL top K thu t l p trình - Nguy n Minh Huy 8
  9. T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: L y ph n t : stack_pop. stack_pop. Dùng m ng đ ng Dùng danh sách liên k t đơn data 5 7 2 data data head next next NULL top K thu t l p trình - Nguy n Minh Huy 9
  10. T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: Đ c ph n t : stack_peek. stack_peek. Dùng m ng đ ng Dùng danh sách liên k t đơn data 5 7 2 data data head next next NULL top K thu t l p trình - Nguy n Minh Huy 10
  11. T ng quan v ngăn x p ng d ng ngăn x p: p: Th c hi n thao tác ngư c: c: Đ i 1 s nguyên sang h nh phân. phân. x = 10 x%2 printf() printf() 1 0 1 0 Ngăn x p K thu t l p trình - Nguy n Minh Huy 11
  12. T ng quan v ngăn x p ng d ng ngăn x p: p: Cài đ t đ quy: quy: long fibo(int n) fibo( { Dùng ngăn x p h th ng.ng. stack_push(1); stack_push(1); L i stack-overflow. stack- stack_push(1); stack_push(1); Dùng ngăn x p t t o for (int i = 2; i
  13. N i dung T ng quan v ngăn x p. p. T ng quan v hàng đ i.i. K thu t l p trình - Nguy n Minh Huy 13
  14. T ng quan v hàng đ i Khái ni m hàng đ i: i: Dãy ph n t ho t đ ng theo cơ ch FIFO. Cơ ch FIFO (First In First Out). (F First Come First Serve. Vào sau ra sau Th t vào trư c ra trư c.c. 5 7 Hàng đ i 2 6 Vào trư c ra trư c K thu t l p trình - Nguy n Minh Huy 14
  15. T ng quan v hàng đ i Các thao tác trên hàng đ i: i: push: thêm ph n t . pop: l y ph n t . push peek: đ c ph n t . 8 empty: ki m tra r ng. ng. 5 full: ki m tra đ y. y. 7 Hàng đ i 2 peek 6 pop 6 K thu t l p trình - Nguy n Minh Huy 15
  16. T ng quan v hàng đ i Cài đ t hàng đ i trong C: Khai báo và kh i t o: o: // Dùng m ng đ ng. ng. // Dùng danh sách liên k t đơn. đơn. struct Queue struct Queue { { int *data; CNode *head; int in; CNode *tail; int out; }; int size; }; void queue_init(Queue &s, int initSize) queue_init(Queue initSize) void queue_init(Queue &s) queue_init(Queue { { s.size = initSize; initSize; s.head = NULL; s.data = new int[initSize]; int[initSize] s.tail = NULL; s.in = 0; } s.out = 0; } K thu t l p trình - Nguy n Minh Huy 16
  17. T ng quan v hàng đ i Cài đ t hàng đ i trong C: Ki m tra r ng và đ y: y: // Dùng m ng đ ng. ng. // Dùng danh sách vòng. vòng. bool queue_empty(Queue s) queue_empty(Queue bool queue_empty(Stack s) queue_empty(Stack { { return s.in == s.out; s.out; return s.head == NULL; } } bool queue_full(Queue s) queue_full(Queue { return s.in == s.size; s.size; } K thu t l p trình - Nguy n Minh Huy 17
  18. T ng quan v hàng đ i Cài đ t hàng đ i trong C: Các thao tác: tác: Thêm ph n t : queue_push. queue_push. Dùng m ng đ ng Dùng danh sách liên k t đơn Thêm đ u x data x next data 5 7 data data head next next out in data data tail next next K thu t l p trình - Nguy n Minh Huy 18
  19. T ng quan v hàng đ i Cài đ t hàng đ i trong C: Các thao tác: tác: L y ph n t : queue_pop. queue_pop. Dùng m ng đ ng Dùng danh sách kép data data head next next data 5 7 data data tail next next out in K thu t l p trình - Nguy n Minh Huy 19
  20. T ng quan v hàng đ i Cài đ t hàng đ i trong C: Các thao tác: tác: Đ c ph n t : queue_peek. queue_peek. Dùng m ng đ ng Dùng danh sách kép data data head next next data 5 7 data data tail next next out in K thu t l p trình - Nguy n Minh Huy 20
ADSENSE

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.

 

Đồng bộ tài khoản
2=>2