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

CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - NGĂN XẾP

Chia sẻ: Lê Ngọc Hoàng | Ngày: | Loại File: PPT | Số trang:13

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

Là một danh sách tuyến tính 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 N là độ dài của ngăn xếp Item là kiểu dữ liệu của các phần tử Ngăn xếp là một cấu trúc gồm 2 thành phần Biến top lưu chỉ số của phần tử mảng lưu phần tử ở đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp

Chủ đề:
Lưu

Nội dung Text: CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - NGĂN XẾP

  1. NGĂN XẾP STACK
  2. KHÁI NIỆM NGĂN XẾP Là một danh sách tuyến tính  Bổ sung một phần tử vào ngăn  Đỉnh D xếp hoặc lấy một phần tử ra C khỏi ngăn xếp chỉ thực hiện ở B một đầu gọi là đỉnh ngăn xếp Item A Đáy Hình ảnh ngăn xếp
  3. BIỂU DIỄN CẤU TRÚC DỮ LIỆU #define Max N //Định nghĩa kiểu Item struct Stack{ Item E[Max] ; int top ; }; Stack S ; //Khai báo ngăn xếp S N là độ dài của ngăn xếp  Item là kiểu dữ liệu của các phần tử  Ngăn xếp là một cấu trúc gồm 2 thành phần  Biến top lưu chỉ số của phần tử mảng lưu phần tử ở  đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp 
  4. BIỂU DIỄN CẤU TRÚC DỮ LIỆU Max=7 6 Chưa có D top=3 C 2 Ngăn xếp B 1 A 0 E Mảng lưu trữ ngăn xếp
  5. BIỂU DIỄN CẤU TRÚC DỮ LIỆU Const Max = N ; Type Stack = Record E : Array[1..Max] Of Item ; top : 0..Max ; End ; Var S : Stack ; {Khai báo ngăn xếp S} N là độ dài của ngăn xếp  Item là kiểu dữ liệu của các phần tử  Ngăn xếp là một bản ghi gồm hai trường  Biến top lưu chỉ số của phần tử mảng lưu phần tử ở  đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp 
  6. BIỂU DIỄN CẤU TRÚC DỮ LIỆU Ví dụ: Ngăn xếp chứa thông tin học sinh #define Max 100 struct Hoc_sinh{ char ho_ten[25]; int tuoi; float dtb; }; struct Stack{ Hoc_sinh E[Max]; int top; }; Stack S;
  7. CÁC PHÉP TOÁN TRÊN NX Max=7 Khởi tạo ngăn xếp rỗng  6 5 void Initialize (Stack &S) { 4 S.top = -1; } 3 2 Kiểm tra ngăn xếp rỗng  1 0 int Empty (Stack S) { E top = -1 return (S.top == -1); } Ngăn xếp rỗng
  8. CÁC PHÉP TOÁN TRÊN NX Max=7 G 6 top = Max-1 F 5 E Kiểm tra ngăn xếp đầy 4  3 D int Full (Stack S) { C 2 return (S.top == Max-1); B } 1 A 0 E Ngăn xếp đầy
  9. CÁC PHÉP TOÁN TRÊN NX Bổ sung một phần tử X vào đỉnh ngăn xếp S  Max=7 Max=7 Max=7 6 6 6 5 5 5 X 4 X top = 4 top = 4 D 3 3 D D top 3 C 2 C C 2 2 B B B 1 1 1 A A A 0 0 0 E E E
  10. CÁC PHÉP TOÁN TRÊN NX Bổ sung một phần tử vào đỉnh ngăn xếp S  int PUSH (Stack &S, Item X) { if ( Full(S)) return 0; else { S.top++; S.E[S.top] = X; return 1; } }
  11. CÁC PHÉP TOÁN TRÊN NX Lấy một phần tử ở đỉnh ngăn xếp S  Max=7 Max=7 6 6 5 5 D 4 4 D 3 top = 3 C 2 C top = 2 B B 1 1 A A 0 0 E E
  12. CÁC PHÉP TOÁN TRÊN NX Lấy một phần tử ở đỉnh ngăn xếp S  Int POP (Stack &S, Item &Y) { if (Empty(S)) return 0; else { Y = S.E[S.top]; S.top--; return 1; } }
  13. CÁC PHÉP TOÁN TRÊN NX Ví dụ ứng dụng  Viết chương trình: - Nhập số nguyên dương N - Đổi số N sang dạng mã nhị phân tương ứng của nó. - In kết quả ra màn hình
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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