Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - ĐH Bách khoa TP. HCM
lượt xem 7
download
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Stack" cung cấp cho sinh viên các kiến thức về mô tả stack, ứng dụng - Đảo ngược danh sách, stack trừu tượng, thiết kế stack, hiện thực stack liên tục, đẩy một phần tử vào stack, lấy giá trị trên đỉnh stack, Reverse Polish Calculator, giải thuật tính toán với toán tử,... Mời các bạn cùng tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - ĐH Bách khoa TP. HCM
- A C B CẤU TRÚC DỮ LIỆU VÀ F GIẢI THUẬT (501040) D E G Chương 2: Stack K H
- Mô tả stack Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack). Là một dạng vào sau ra trước – LIFO (Last In First Out) ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 2
- Ví dụ về stack Stack rỗng: Q Đẩy (push) Q vào: A Q Đẩy A vào: A Lấy (pop) ra một => được A: Q Lấy ra một => được Q và stack rỗng: Q ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 3
- Ứng dụng: Đảo ngược danh sách Yêu cầu: Đảo ngược một danh sách nhập vào Giải thuật: 1. Lặp lại n lần 1.1. Nhập vào một giá trị 1.2. Đẩy nó vào stack 2. Lặp khi stack chưa rỗng 2.1. Lấy một giá trị từ stack 2.2. In ra ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 4
- Đảo ngược danh sách – Ví dụ Cần nhập 4 số vào Ban đầu Nhập 1 Nhập 5 Nhập 7 Nhập 3 3 7 7 5 5 5 1 1 1 1 Stack đã rỗng Lấy ra => 3 Lấy ra => 7 Lấy ra => 5 Lấy ra => 1 Ngừng 3 7 7 5 5 5 1 1 1 1 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 5
- Đảo ngược danh sách – Mã C++ #include sử dụng STL using namespace std; (Standard Template Library) int main( ) { khai báo một stack có kiểu dữ liệu int n; của các phân tử bên trong là double double item; stack numbers; cout > n; đẩy một số vào trong stack for (int i = 0; i < n; i++) { cin >> item; kiểm tra xem stack có khác rỗng không numbers.push(item); } lấy giá trị trên đỉnh của stack ra, while (!numbers.empty( )) { stack không đổi cout
- Kiểu trừu tượng (abstract data type) ĐN1: Một kiểu (type) một tập hợp mỗi thành phần của tập hợp này là các giá trị (value) Ví dụ: int, float, char là các kiểu cơ bản ĐN2: Một dãy của kiểu T có chiều dài bằng 0 là rỗng có chiều dài n (n>=1): bộ thứ tự (Sn-1, t) Sn-1: dãy có chiều dài n-1 thuộc kiểu T t là một giá trị thuộc kiểu T. ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 7
- Stack trừu tượng Một stack kiểu T: Một dãy hữu hạn kiểu T Một số tác vụ: 1. Khởi tạo stack rỗng (create) 2. Kiểm tra rỗng (empty) 3. Đẩy một giá trị vào trên đỉnh của stack (push) 4. Bỏ giá trị đang có trên đỉnh của stack (pop) 5. Lấy giá trị trên đỉnh của stack, stack không đổi (top) ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 8
- Thiết kế stack enum Error_code {fail, success, overflow, underflow}; template class Stack { public: Stack(); //constructor bool empty() const; //kiểm tra rỗng Error_code push(const Entry &item); //đẩy item vào Error_code pop(); //bỏ phần tử trên đỉnh Error_code top(Entry &item); //lấy giá trị trên đỉnh //khai báo một số phương thức cần thiết khác private: //khai báo dữ liệu và hàm phụ trợ chỗ này }; ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 9
- Thiết kế các phương thức template bool Stack::empty() const; Pre: Không có Post: Trả về giá trị true nếu stack hiện tại là rỗng, ngược lại thì trả về false template Error_code Stack::push(const Entry &item); Pre: Không có Post: Nếu stack hiện tại không đầy, item sẽ được thêm vào đỉnh của stack. Ngược lại trả về giá trị overflow của kiểu Error_code và stack không đổi. template Error_code Stack::pop() const; Pre: Không có Post: Nếu stack hiện tại không rỗng, đỉnh của stack hiện tại sẽ bị hủy bỏ. Ngược lại trả về giá trị underflow của kiểu Error_code và stack không đổi. template Error_code Stack::top(Entry &item) const; Pre: Không có Post: Nếu stack hiện tại không rỗng, đỉnh của stack hiện tại sẽ được chép vào tham biến item. Ngược lại trả về giá trị fail của kiểu Error_code. ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 10
- Hiện thực stack liên tục ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 11
- Khai báo stack liên tục const int maxstack = 10; //small number for testing template class Stack { public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item); private: int count; Entry entry[maxstack]; }; ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 12
- Đẩy một phần tử vào stack Giải thuật: 1. Nếu còn chỗ trống trong stack 1.1. Tăng vị trí đỉnh lên 1 1.2. Chứa giá trị vào vị trí đỉnh của stack 1.3. Tăng số phần tử lên 1 7 top 5 1 count=3 count=2 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 13
- Bỏ phần tử trên đỉnh stack Giải thuật: 1. Nếu còn phần tử trong stack 1.1. Giảm vị trí đỉnh đi 1 1.2. Giảm số phần tử đi 1 top 7 5 1 count=2 count=3 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 14
- Thêm/Bỏ phần tử - Mã C++ template Error_code Stack:: push(const Entry &item) { if (count >= maxstack) return overflow; else entry[count++] = item; return success; } template Error_code Stack:: pop() { if (count == 0) return underflow; else count--; return success; } ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 15
- Lấy giá trị trên đỉnh stack Giải thuật: 1. Nếu còn phần tử trong stack 1.1. Trả về giá trị tại vị trí đỉnh Mã C++: template Error_code Stack:: top(Entry &item) { if (count == 0) return underflow; else item = entry[count - 1]; return success; } ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 16
- Reverse Polish Calculator Mô tả bài toán: Các toán hạng được đọc vào trước và đẩy vào stack Khi đọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán với toán tử này, rồi đẩy kết quả vào stack Thiết kế phần mềm: Cần một stack để chứa toán hạng Cần hàm get_command để nhận lệnh từ người dùng Cần hàm do_command để thực hiện lệnh ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 17
- Reverse Polish Calculator – Thiết kế chức năng Tập lệnh: ‘?’: đọc một giá trị rồi đẩy vào stack Toán tử ‘+’, ‘-’, ‘*’, ‘/’: lấy 2 giá trị trong stack, tính toán và đẩy kết quả vào stack Toán tử ‘=’: in đỉnh của stack ra ‘q’: kết thúc chương trình ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 18
- Reverse Polish Calculator – Ví dụ Tính toán biểu thức: 3 5 + 2 * = 5 5 3 3 3 8 Ban đầu Toán tử ? Toán tử ? Toán tử + Đẩy 8 vào Nhập vào 3 Nhập vào 5 Lấy ra 5 và 3 Tính 3 + 5 => 8 2 2 8 8 16 16 Toán tử ? Toán tử * Đẩy vào 16 Toán tử = Nhập vào 2 Lấy ra 2 và 8 In ra 16 Tính 8 * 2 => 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack 19
- Reverse Polish Calculator – Hàm get_command char get command( ) { char command; bool waiting = true; cout > command; command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || command == ‘−’|| command == ‘*’ || command == ‘/’ || command == ‘q’) waiting = false; else { cout
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 174 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 79 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 57 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 158 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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