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

Ngăn xếp

Chia sẻ: Kieu Quang Vinh | Ngày: | Loại File: PPT | Số trang:36

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

Phép toán bổ sung một phần tử vào ngăn xếp hoặc lấy một phần tử ra khỏi ngăn xếp chỉ thực hiện ở một đầu gọi là đỉnh ngăn xếp...

Chủ đề:

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

Lưu

Nội dung Text: Ngăn xếp

  1. NGĂN XẾP STACK
  2. 3.4 CẤU TRÚC NGĂN XẾP  Khái niệm, đặc điểm  Lưu trữ kế tiếp của ngăn xếp  Ngăn xếp móc nối  Ứng dụng của ngăn xếp 2/36
  3. 3.4.1 Khái niệm, đặc điểm ngăn xếp Khái niệm Là một danh sách tuyến tính  Phép toán bổ sung một phần  Đỉnh D tử vào ngăn xếp hoặc lấy một C phần tử ra khỏi ngăn xếp chỉ B A thực hiện ở một đầu gọi là Đáy đỉnh ngăn xếp Hình ảnh ngăn xếp 3/36
  4. 3.4.1 Khái niệm, đặc điểm ngăn xếp Phần tử đưa vào ngăn xếp sau sẽ được lấy ra xử lí  trước, phần tử đưa vào ngăn xếp trước sẽ được lấy ra xử lí sau. Được gọi là danh sách LIFO (Last - In - First - Out)  4/36
  5. 3.4.2 Lưu trữ kế tiếp của ngăn xếp Định nghĩa và khai báo cấu trúc dữ liệu  Định nghĩa các phép toán và chương trình th ực hiện  các phép toán cơ bản 5/36
  6. Định nghĩa và khai báo cấu trúc dữ liệu Ngăn xếp mảng là một bản ghi gồm có hai trường  Trường 1 : là một số nguyên biểu diễn số phần  tử có trong ngăn xếp Trường 2 : Là mảng một chiều có kích thước đủ  lớn để lưu các phần tử của ngăn xếp 6/36
  7. Định nghĩa và khai báo cấu trúc dữ liệu Khai báo cấu trúc :  const max= ; struct stack { int top ; ptu[max] ; }s; 7/36
  8. Định nghĩa và khai báo cấu trúc dữ liệu max -1 Chưa có phần tử … D 3 C 2 Ngăn xếp B 1 A 0 Mảng lưu trữ ngăn xếp s 8/36
  9. Các phép toán cơ bản Khởi tạo danh sách rỗng : creat(s)  Kiểm tra danh sách rỗng : empty(s)  Kiểm tra danh sách đầy : full(s)  Chèn phần tử x vào đỉnh của ngăn xếp : push(x,s)  Loại phần tử đỉnh của ngăn xếp gán cho x : pop(s,x)  9/36
  10. Các phép toán cơ bản Khởi tạo ngăn xếp rỗng  max -1 void creat(stack &s) … { s.top = 0; 4 } 3 2 Kiểm tra ngăn xếp rỗng  1 int empty(stack s) 0 { top = 0 return s.top == 0 ; Ngăn xếp rỗng } 10/36
  11. Các phép toán cơ bản G max -1 top = max F Kiểm tra ngăn xếp đầy  … 3 D int full(stack s) C 2 { B 1 A 0 return s.top == max ; s } Ngăn xếp đầy 11/36
  12. Các phép toán cơ bản Bổ sung phần tử x vào đỉnh ngăn xếp s  max=7 6 6 6 5 5 5 X X 4 4 4 D D 3 3 D 3 C C 2 C 2 2 B B B top =4 1 1 1 top = 5 top = 4 A A A 0 0 0 s s s 12/36
  13. Các phép toán cơ bản Bổ sung phần tử x vào đỉnh ngăn xếp s  void push( x, stack &s) { if (!full(s)) s.ptu[s.top++]=x; } 13/36
  14. Các phép toán cơ bản Loại phần tử ở đỉnh ngăn xếp s gán cho x  max=7 6 6 5 5 x x D 4 4 D 3 3 C 2 C 2 B B 1 1 top = 4 top = 3 A A 0 0 s s 14/36
  15. Các phép toán cơ bản Loại phần tử ở đỉnh ngăn xếp s gán cho x  void pop(stack &s, &x) { if (s.top>0) x=s.ptu[--s.top]; } 15/36
  16. 3.4.3 Lưu trữ móc nối của ngăn xếp Định nghĩa và khai báo cấu trúc dữ liệu  Định nghĩa các phép toán và chương trình th ực hiện  các phép toán cơ bản 16/36
  17. Định nghĩa và khai báo CTDL  Mỗi phần tử của ngăn xếp móc nối là một bản ghi gồm có 2 trường data next data chứa thông tin của phần tử  next là một con trỏ,trỏ vào nút đứng sau trong  ngăn xếp 17/36
  18. Định nghĩa và khai báo CTDL  Ngăn xếp được định nghĩa là một con trỏ tr ỏ vào ph ần tử đỉnh của ngăn xếp NULL an … a2 a1 s Con trỏ next của phần tử đáy ngăn xếp nhận giá trị  NULL báo hiệu kết thúc ngăn xếp 18/36
  19. Định nghĩa và khai báo CTDL  Khai báo cấu trúc ngăn xếp móc nối : struct node { ptu; node *next; } *s ; 19/36
  20. Các phép toán cơ bản  Khởi tạo ngăn xếp rỗng : creat(s)  Kiểm tra ngăn xếp rỗng : empty(s)  Chèn phần tử x vào đỉnh ngăn xếp : push(x,s)  Loại bỏ một phần tử khỏi danh sách : pop(s,x) 20/36
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