Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 – Trần Minh Thái (2017)

Chia sẻ: Nguoibakhong01 Nguoibakhong01 | Ngày: | Loại File: PPTX | Số trang:65

Thêm vào BST

Báo xấu

57
lượt xem 3
download

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

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Tổ chức ngăn xếp (Stack) & hàng đợi (Queue) trên mảng một chiều" trình bày các nội dung: Trình bày khái niệm ngăn xếp (Stack) và hàng đợi (Queue), các thao tác trên ngăn xếp và hàng đợi, minh họa các ứng dụng. 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 Cấu trúc dữ liệu và giải thuật: Chương 3 – Trần Minh Thái (2017)

Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1
Nội dung • Trình bày khái niệm Ngăn xếp (Stack) và Hàng đợi (Queue) • Các thao tác trên Ngăn xếp và Hàng đợi • Minh họa các ứng dụng 2
Ngăn xếp • Ngăn xếp là gì? • Cách khai báo cấu trúc ngăn xếp dùng mảng một chiều? • Các ứng dụng • Cài đặt 3
Ví dụ về Ngăn xếp Thành phần được lấy ra đầu tiên? 4
Khái niệm Stack • Gồm nhiều phần tử lưu trữ theo thứ tự • Hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out) Đỉnh ngăn xếp 5
Thao tác cơ bản trên Stack • InitStack: khởi tạo Stack rỗng • IsEmpty: kiểm tra Stack rỗng? • IsFull: kiểm tra Stack đầy? Push Pop • Push: thêm 1 phần tử vào Stack • Pop: lấy ra 1 phần tử khỏi Stack 6
Thao tác Push vào Stack PUSH Top 7
Thao tác Pop khỏi stack Top P OP 8
Stack – Sử dụng mảng Top C B A Stack A B C 0 1 2 3 4 5 6 7 8 9 Top 9
Ngăn xếp – Sử dụng mảng Top Top Top E D D D C Top C C C B B B B B Top A A A A A A Top 10
Ví dụ, Ngăn xếp chứa số nguyên – Sử dụng mảng struct ttStack { int* StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack }; typedef struct ttStack STACK; 11
Ngăn xếp số nguyên – Sử dụng mảng int InitStack(STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; s.StkMax = MaxItems; s.StkTop = -1; return 1; //Khởi tạo thành công } 12
Ngăn xếp số nguyên – Sử dụng mảng int IsEmpty(const STACK &s) { if (s.StkTop==-1) return 1; return 0; } 13
Stack số nguyên – Sử dụng mảng int IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return 1; return 0; } 14
Stack số nguyên – Sử dụng mảng int Push (STACK &s, int newitem) { if (IsFull(s)==1) return 0; s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1; } 15
Stack số nguyên – Sử dụng mảng int Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return 0; outitem = s.StkArray[s.StkTop]; s.StkTop--; return 1; } 16
Bài tập Viết hàm nhập, xuất Stack số nguyên dương sao cho: • Cho phép người dùng lần lượt nhập vào Stack các số nguyên dương • Nếu nhập vào giá trị
Stack – Ứng dụng • Kiểm tra sự tương ứng của các cặp ngoặc đơn trong một biểu thức • ((A+B)/C ( A + B ) / C) ? ? • Đảo ngược một chuỗi ký tự • Cá Ăn Kiến  nếiK nĂ áC 18
Stack – Ứng dụng • Lưu vết trong thuật toán “back-tracking” (theo dõi dấu vết) • Tính giá trị biểu thức toán học • Khử đệ quy • … 19
Bài toán tháp HaNoi