zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 9: Ngăn xếp - Stacks

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:24

Báo xấu

33
lượt xem 4
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 – Bài 9: Ngăn xếp - Stacks" thông tin đến các bạn kiến thức về khái niệm về stacks, các thao tác chính của stacks, các thao tác khác của stacks.

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 – Bài 9: Ngăn xếp - Stacks

Cấu trúc dữ liệu và giải thuật Bài 9: Ngăn xếp - Stacks Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 PhD Ngo Huu Phuc, Le Quy Don Technical University
Bài 9. Ngăn xếp Nội dung: 9.1. Khái niệm về stacks (7) 9.2. Các thao tác chính của stacks (9) 9.3. Các thao tác khác của stacks (9) Tham khảo: 1. Data structures and Algorithms Stacks.htm 2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues 3. Elliz Horowitz – Fundamentals of Data Structures, Chapter 3 Stacks and Queues 4. Deshpande Kakle – C and Data Structures, Chapter 19. Stacks and Queues 5. Bài giảng TS Nguyễn Nam Hồng 2 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (1/7)  Có thể hình dung stack như một chồng đĩa. Với chồng đĩa này, có thể nhìn thấy chiếc đĩa ở trên cùng, các đĩa còn lại chưa nhìn thấy được.  Khi thêm một đĩa vào chồng đĩa (pushed), chiếc đĩa này ở đỉnh của stack, có thể nhìn thấy.  Khi lấy di một đĩa từ stack (popped), có thể sử dụng đĩa này, chiếc đĩa kế tiếp trở thành đỉnh của stack. 3 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (2/7) 4 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (3/7)  Nguyên lý cơ bản của stack là Last In First Out (LIFO), có nghĩa vào sau ra trước.  Với nguyên lý đó, chỉ có chiếc đĩa trên cùng stack mới có thể nhìn thấy. Muốn nhìn thấy chiếc đĩa thứ 3, cần lấy ra khỏi stack các đĩa thứ nhất và thứ 2. 5 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (3/7) 6 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (4/7) Có 3 thao tác chính của stack: Push Pop  Push  Đưa một phần tử vào đỉnh của stack.  Pop  Lấy từ đỉnh của stack một phần tử.  Peek  Xem đỉnh của stack chứa nội dung là gì? 7 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (5/7) Một số ứng dụng của stack:  Ứng dụng trực tiếp:  Ứng dụng nổi bật của stack là stack cho chương trình, chương trình sử dụng stack để gọi hàm.  Trong trình duyệt WEB, các trang đã xem được lưu trong stack.  Trong trình soạn thảo văn bản, thao tác Undo được lưu trong stack.  Ứng dụng gián tiếp:  Cấu trúc dữ liệu bổ trợ cho thuật toán khác.  Một thành phần của cấu trúc dữ liệu khác. 8 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (6/7) Thực thi và giới hạn của stack.  Thực thi.  Gọi n là số ô nhớ cho stack.  Không gian có thể sử dụng đối với stack là O(n).  Với mỗi thao tác, độ phức tạp là O(1)  Giới hạn.  Kích thước tối đa của stack được định nghĩa trước, không thể thay đổi (nếu dùng mảng).  Nếu stack đã đầy, không PUSH được phần tử mới vào stack. Nếu stack rỗng, thao tác POP cho kết quả rỗng. 9 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.1. Khái niệm về stacks (7/7) Đối với stack cần:  Định nghĩa stack:  MAXSIZE: Số phần tử tối đa của stack (nếu dùng mảng).  ItemType: Kiểu dữ liệu cho stack.  Thao tác chính:  Push  Pop  Peek  Thao tác khác:  IsEmpty  IsFull  MakeEmpty 10 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (1/9)  Trước hết, định nghĩa kích thước cho stack: Ví dụ: #define MAXSIZE 100  Có thể sử dụng stack để lưu bất kỳ kiểu dữ liệu nào, do đó cần định nghĩa kiểu dữ liệu cho stack: Ví dụ: int stack[MAXSIZE];  Có thể dùng một con trỏ để xác định đỉnh của stack hoặc đơn giản hơn, dùng phần tử mảng đầu tiên của stack để lưu số phần đã có trong stack: Ví dụ: stack[0] = 0; 11 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (2/9) Thao tác Push (newItem: ItemType)  Chức năng: Thêm một phần tử vào đỉnh của Stack.  Điều kiện thực hiện: Stack đã được khởi tạo và chưa đầy.  Kết quả: Nếu thêm thành công, newItem sẽ ở đỉnh của Stack. 12 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (3/9) Ví dụ về hàm push: void push(int stack[], int value) { if(stack[0] < MAXSIZE-1 ) { stack[0] = stack[0] + 1; stack[stack[0]] = value; } else { printf("Khong the them vao STACK\n"); getch(); } } 13 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (4/9) Thao tác Pop (item: ItemType)  Chức năng: Lấy phần tử ở đỉnh của Stack và trả lại cho lời gọi hàm.  Điều kiện: Stack đã được khởi tạo và không rỗng.  Kết quả: Phần tử ở đỉnh của Stack được trả lại cho lời gọi hàm và số phần tử trong Stack giảm đi 1. 14 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (5/9) Ví dụ về hàm pop: int pop(int stack[]) { int value; if(stack[0] > 0 ) { value = stack[stack[0]]; stack[0] = stack[0] - 1; } else { printf("STACK rong\n"); value = -32768; } return value; } 15 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (7/9) Thao tác Peek:  Chức năng: Lấy giá trị tại đỉnh của Stack nhưng không loại phần tử ở đỉnh của Stack.  Điều kiện: Stack đã được khởi tạo và không rỗng.  Kết quả: Giá trị tại đỉnh của Stack được trả về cho lời gọi hàm, Stack không thay đổi. 16 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.2. Thao tác cơ bản của stack (8/9) Ví dụ về hàm Peek int peek(int stack[]) { if(stack[0]>0) return stack[stack[0]]; else { printf("STACK rong\n"); return -32768; } } 17 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.3. Các thao tác khác của stacks (1/9)  Thao tác isEmpty:  Kiểm tra xem Stack có rỗng không?  Thao tác isFull:  Kiểm tra xem Stack đã đầy chưa?  Thao tác makeEmpty:  Làm rỗng Stack.  Xây dựng hàm Push sử dụng thao tác isFull.  Xây dựng hàm Pop sử dụng thao tác isEmpty.  Xây dựng hàm Peek sử dụng thao tác isEmpty. 18 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.3. Các thao tác khác của stacks (2/9) Thao tác isEmpty:  Kiểm tra xem Stack có rỗng không?  Nếu rỗng hàm trả về 1, nếu không hàm trả về 0. int isEmpty(int stack[]) { if(stack[0]==0) return 1; else return 0; } 19 PhD Ngo Huu Phuc, Le Quy Don Technical University
9.3. Các thao tác khác của stacks (3/9) Thao tác isFull:  Kiểm tra xem Stack đã đầy chưa?  Nếu đã đầy, hàm trả về 1; nếu chưa đầy, hàm trả về 0. int isFull(int stack[]) { if(stack[0]==MAXSIZE-1) return 1; else return 0; } 20 PhD Ngo Huu Phuc, Le Quy Don Technical University

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.