Bài 1: Ngăn xếp (Stack)

Chia sẻ: Nguyenvan Tung | Ngày: | Loại File: PPT | Số trang:11

Thêm vào BST

Báo xấu

175
lượt xem 42
download

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

Sau bài học này, sinh viên có khả năng: .Trình bày được định nghĩa ngăn xếp (Stack) .Cài đặt được ngăn xếp . Vận dụng ngăn xếp vào các bài toán (đổi cơ số nhị phân, khử đệ qui,...)

Chủ đề:

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

Lưu

Nội dung Text: Bài 1: Ngăn xếp (Stack)

Câu hỏi kiểm tra Trình bày cách khai báo một cấu trúc ? Trả lời typedef struct { ……………… ……………… } tên_cấu_trúc;
Bai 1. NGĂN XẾP (STACK) ̀ CBGD: Trần Việt Khánh
• Sau bài học này, sinh viên có khả năng:  Trình bày được định nghĩa ngăn xếp (Stack) MỤC TIÊU  Cài đặt được ngăn xếp  Vận dụng ngăn xếp vào các bài toán (đổi cơ số nhị phân, khử đệ qui,...)
I/ Định nghĩa II/ Cài đặt Stack (ngăn xếp) NỘI DUNG 1. Khai báo cấu trúc của một ngăn xếp 2. Các tác vụ trên ngăn xếp
I/ Định nghĩa Stack (ngăn xếp) là một cấu trúc trừu tượng, được thực hiện theo cơ chế LIFO (Last In First Out): phần tử được đưa vào ngăn xếp sau cùng sẽ được lấy ra trước tiên. - Stack được cài đặt trên cơ sở mảng (bao gồm nhiều phần tử. - Chỉ số top để chỉ định các phần tử trong danh sách. Hình vẽ minh họa ngăn xếp (Stack)
II/ Cài đặt Stack (ngăn xếp) 1. Khai báo cấu trúc ngăn xếp Sử dụng mảng S để chứa các phần tử và 1 biến chỉ số top để chỉ định các phần tử trong mảng S. // Khai báo cấu trúc của một Stack typedef struct { int top; int nodes[MAXSIZE]; } stack;
2. Các tác vụ trên Stack (ngăn xếp) • Khởi tạo ngăn xếp rỗng void CreateStack(stack &s) { s.top=-1; } • Kiểm tra ngăn xếp có bị rỗng không bool EmptyStack(stack s) { return ( s.top == -1); }
Đưa một phần tử vào ngăn xếp (Stack) void Push(stack &s, int x) { s.top++; s.nodes[s.top]=x; }
Lấy một phần tử ra khỏi ngăn xếp (Stack) int Pop(stack &s) { int x; x=s.nodes[s.top]; s.top --; return x; }
BÀI TẬP 1. Viết chương trình áp dụng Stack ngăn xếp để đổi một số nguyên n ra dạng nhị phân. 2. Có thể áp dụng Stack (ngăn xếp) để khử đệ qui.